A No Free Lunch theorem for multi-objective optimization

The No Free Lunch theorem (Schumacher et al., 2001; Wolpert and Macready, 1997 [8,10]) is a foundational impossibility result in black-box optimization stating that no optimization technique has performance superior to any other over any set of functions closed under permutation.This paper considers situations in which there is some form of structure on the set of objective values other than the typical total ordering (e.g., Pareto dominance in multi-objective optimization). It is shown that in such cases, when attention is restricted to natural measures of performance and optimization algorithms that measure performance and optimize with respect to this structure, that a No Free Lunch result holds for any class of problems which is structurally closed under permutation. This generalizes the Sharpened No Free Lunch theorem of Schumacher et al. (2001) [8] to non-totally ordered objective spaces.