Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Multiobjective Hypervolume Based ISOOMOO Algorithms Converge with At Least Sublinear Speed to the Entire Pareto Front

Eugénie Marescaux 1, 2 Anne Auger 2
2 RANDOPT - Randomized Optimisation
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : In multiobjective optimization, one is interested in finding a good approximation of the Pareto set and the Pareto front, i.e the sets of best compromises in the decision and objective spaces, respectively. In this context, we introduce a new algorithm framework, Incremental SingleObjective Optimization for MultiObjective Optimization (ISOOMOO) for approximating the Pareto front with an increasing number of points. We focus on HV-ISOOMOO, its instanciation with the hypervolume indicator, a set-quality indicator which is widely used for algorithms design and performance assessment. HV-ISOOMOO algorithms approximate the Pareto front by greedily maximizing the hypervolume. We study the convergence to the entire Pareto front of HV-ISOOMOO coupled with a perfect singleobjective optimizer. The convergence is defined as the convergence of the hypervolume of the sets of all metaiterations incumbents towards the hypervolume of the Pareto front. We prove tight lower bounds on the convergence-speed for convex and bilipschitz Pareto fronts in O(1/n c) with n being the number of metaiterations and c = 1 and c ≤ 1, respectively. For convex Pareto fronts, the convergence rate is exactly in Θ(1/n), namely the highest convergence rate achievable by a biobjective optimization algorithm. These are the first results on the convergence-speed of multiobjective optimization algorithms towards the entire Pareto front. We also analyze theoretically the asymptotic convergence behavior.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03198414
Contributor : Eugénie Marescaux <>
Submitted on : Tuesday, July 13, 2021 - 2:03:44 PM
Last modification on : Friday, September 17, 2021 - 3:35:54 AM

File

first_hal_version.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03198414, version 1

Citation

Eugénie Marescaux, Anne Auger. Multiobjective Hypervolume Based ISOOMOO Algorithms Converge with At Least Sublinear Speed to the Entire Pareto Front. 2021. ⟨hal-03198414v1⟩

Share

Metrics

Record views

63

Files downloads

17