Multiobjective Hypervolume Based ISOOMOO Algorithms Converge with At Least Sublinear Speed to the Entire Pareto Front - Centre de mathématiques appliquées (CMAP) Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

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

Résumé

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.
Fichier principal
Vignette du fichier
first_hal_version.pdf (453.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03198414 , version 1 (13-07-2021)
hal-03198414 , version 2 (16-09-2021)
hal-03198414 , version 3 (22-04-2022)

Identifiants

  • HAL Id : hal-03198414 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More