Convergence analysis and novel algorithms in multi-objective optimization

Analyse de convergence et nouveaux algorithmes en optimisation multi-objectif 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.