Convergence analysis and novel algorithms in multi-objective optimization
Analyse de convergence et nouveaux algorithmes en optimisation multi-objectif
Résumé
Optimization is the field of applied mathematics concerned with minimizing (or maxi-mizing) one or more objective functions. It has many applications in science and indus-try, from scheduling power outages to designing cars to describing physical phenomena.Multi-objective optimization aims at finding a good approximation of the Pareto set,that is the set of feasible solutions which cannot be improved in all objectives simultane-ously, and the Pareto front, its image in the objective space. In this Ph.D. thesis, we seekto improve the understanding of the convergence speed of multi-objective optimizationalgorithms towards the entire Pareto front. We rely on the hypervolume, a widely usedset quality indicator, to quantify the optimality gap between the Pareto front and itsapproximation provided by an algorithm. The computational cost is measured by thenumber of evaluations of the objective functions.First, we derive a theoretical upper bound on the speed of convergence. We provethat for a wide class of Pareto fronts, the smallest optimality gap associated to a set ofn points is higher than 1/(n + 1) multiplied by a constant. The constant depends onthe Pareto front and the reference point used in the definition of the hypervolume. Thisresult shows that the speed of convergence is sublinear at best, which is worse than theconvergence rates that can be achieved by single-objective optimization algorithms.Then, we introduce an algorithmic framework, HyperVolume-Based IncrementalSingle-Objective Optimization for Multi-Objective Optimization (HV-ISOOMOO). Ameta-iteration of HV-ISOOMOO corresponds to the solving of a single-objective op-timization subproblem. We provide lower bounds on the convergence speed of thePareto front approximation formed by the solutions returned by the single-objectivesolver (which we call the final incumbents Pareto front approximation) under the as-sumption that the solver returns a global optimum with infinite precision. For convexPareto fronts, this ideal algorithm reaches the best achievable convergence rate: θ(1/n).Finally, we provide an implementation of HV-ISOOMOO coupled with CMA-ES,a state-of-the-art single-objective optimization algorithm. We call it Multi-ObjectiveCovariance Matrix Adaptation 2 (MO-CMA-2). The MO-CMA-2 algorithm presentsstate-of-the-art performance. On a simple convex problem, we empirically analyze theevolution of the optimality gap of its final incumbents Pareto front approximation withrespect to the number of meta-iterations of HV-ISOOMOO and iterations of CMA-ES
L’optimisation est le domaine des mathématiques appliquées qui s’intéresse à la minimi-sation (ou la maximisation) d’une ou plusieurs fonctions objectif. Elle a de nombreusesapplications industrielles et scientifiques, de la planification des pannes de courant à laconception de voitures en passant par la description de phénomènes physiques. L’optimisationmultiobjectif s’intéresse à l’approximation de l’ensemble de Pareto, c’est-à-dire l’ensembledes solutions admissibles qui ne peuvent être améliorées suivant tous les objectifs simul-tanément, et du front de Pareto, son image dans l’espace des objectifs. Dans cette thèsede doctorat, nous cherchons à approfondir les connaissances sur la vitesse de convergenced’algorithmes d’optimisation multiobjectif vers la totalité du front de Pareto. Nous nousappuyons sur l’hypervolume, un indicateur de qualité d’ensemble largement utilisé, pourquantifier l’écart entre le front de Pareto et une approximation fournie par un algorithme,autrement dit l’erreur. Le coût est mesuré par le nombre de fois où les fonctions objectifont été évaluées.Tout d’abord, nous prouvons une borne supérieure théorique sur la vitesse de conver-gence. Nous démontrons que pour une vaste catégorie de fronts de Pareto, la plus petiteerreur associée à une approximation composée de n points est supérieure à 1/(n + 1)multiplié par une constante. Cette constante dépend du front de Pareto et du point deréférence utilisé pour définir l’hypervolume. Cela garantit que la vitesse de convergenceest au mieux sous-linéaire, soit plus lente que les vitesses de convergence qui peuventêtre atteintes par des algorithmes d’optimisation mono-objectifs.Ensuite, nous définissons une nouvelle classe d’algorithmes, HV-ISOOMOO. Uneméta-itération de HV-ISOOMOO correspond à la résolution d’un sous-problème d’optimisationmono-objectif. Les solutions renvoyée par le solveur mono-objectif fournissent une ap-proximation du front de Pareto. Nous démontrons des bornes inférieures sur la vitesse deconvergence de cette approximation vers le front de Pareto en supposant que le solveurmono-objectif fournisse toujours un optimum global avec exactitude. Pour les fronts dePareto convexes, cet algorithme idéal a une vitesse de convergence optimale: θ(1/n).Finalement, nous détaillons une implémentation de HV-ISOOMOO qui utilise lesolveur mono-objectif CMA-ES, MO-CMA-2. Les performances de MO-CMA-2 s’avèrentêtre à la pointe. Sur un problème convexe simple, nous analysons empiriquementl’évolution de l’erreur en fonction du nombre de méta-itérations de MO-CMA-2 et dunombre d’itérations de CMA-ES.
Origine : Version validée par le jury (STAR)