Comparison-based complexity of multiobjective optimization
Olivier Teytaud · 2011
Several comparison-based complexity results have been published recently, including multi-objective optimization. However, these results are, in the multiobjective case, quite pessimistic, due to the huge family of fitness functions considered. Combining assumptions on fitness functions and traditional comparison-based assumptions, we get more realistic bounds emphasizing the importance of reducing the number of conflicting objectives for reducing the runtime of multiobjective optimization. The approach can in particular predict lower bounds on the computation time, depending on the type of requested convergence: pointwise, or to the whole Pareto set. Also, a new (untested yet) algorithm is proposed for approximating the whole Pareto set.