Contributions to Multiobjective Blackbox Optimization

L'optimisation de boîtes noires et l'optimisation sans dérivées sont deux disciplines mathématiques qui traitent des problèmes ne possédant pas de formulation analytique exploitable, rendant caduques les techniques d'optimisation usuelles fondées sur la dérivation. Ces types de problèmes découlent souvent de simulations numériques de systèmes complexes dont la structure ne peut être exploitée, appelées communément des boîtes noires. En outre, la complexification de ces systèmes a mis en évidence les limites d'un modèle d'optimisation unique ne prenant en compte qu'un seul objectif. En effet, de nombreux problèmes d'ingénierie mettent en jeu plusieurs critères, souvent contradictoires, que l'on cherche à optimiser en même temps. L'optimisation multiobjectif intègre ce cadre. La résolution ne donne pas une solution unique, mais un ensemble de points reflétant les différents compromis qui existent entre les objectifs. Les algorithmes qui s'attaquent à des problèmes de boîtes noires multiobjectif ne sont pas aussi développés que leurs homologues mono-objectif. Des heuristiques stochastiques et coûteuses, pouvant poser des problèmes de robustesse, ont longtemps dominé le champ de recherche. L'extension de solveurs mono-objectif déterministes et efficaces pour des boîtes noires possédant des preuves de convergence à l'optimisation multicritères n'a démarré que depuis une dizaine d'années et en est encore à ses débuts. Cette thèse propose donc de nouvelles contributions théoriques et pratiques pour l'optimisation multiobjectif déterministe de boîtes noires. La multiplication de nouveaux algorithmes multiobjectif nécessite d'autant plus le développement d'outils d'analyse afin de pouvoir valider leurs performances et les comparer entre eux, dans le but de guider l'utilisateur vers la ou les méthodes les plus adaptées à son application. La première contribution de cette thèse est une étude sur les indicateurs de performance pour l'optimisation multiobjectif, publiée dans European Journal of Operational Research. Ces derniers évaluent la qualité de l'ensemble des solutions retournées par une méthode multiobjectif sur un problème donné. Cette étude synthétise les propriétés de 63 indicateurs issus de la littérature scientifique, les classifie selon leurs propriétés et liste leurs principaux usages. La deuxième contribution est une nouvelle extension de la méthode de recherche directe par treillis adaptatifs (MADS) à l'optimisation multiobjectif de boîtes noires. Ce nouvel algorithme, DMulti-MADS, s'inspire des algorithmes DMS et BiMADS, créés pour résoudre ce type de problèmes. Nous démontrons que DMulti-MADS garantit la convergence vers un ensemble de points localement non dominés en se basant sur le calcul non lisse de Clarke sous des hypothèses classiques d'algorithmes de recherche directe. Afin de pouvoir valider sa performance, une extension des profils de données à l'optimisation multiobjectif est introduite, basée sur les recommandations de l'étude précédente. Des tests numériques montrent que Dmulti-MADS est compétitif par rapport à des algorithmes de l'état de l'art. Il est également plus performant pour des budgets d'évaluation de taille faible ou moyenne que BiMADS. Cet algorithme a fait l'objet d'une publication parue dans Computational Optimization and Applications. La dernière contribution propose deux nouvelles stratégies appliquées à DMulti-MADS pour gérer des contraintes d'inégalité de type boîtes noires. Les deux stratégies utilisent une fonction de violation des contraintes, que l'on cherche à minimiser en même temps que les objectifs. Ces deux nouvelles méthodes, nommées DMulti-MADS-PB et DMulti-MADSTEB, conservent les propriétés de convergence de DMulti-MADS. Elles sont comparées par rapport à une méthode de pénalité ainsi que les algorithmes de l'état de l'art BiMADS, DFMO et NSGA-II pouvant gérer ce type de contraintes. Les tests numériques montrent qu'elles affichent des performances supérieures aux autres algorithmes sur un ensemble de problèmes analytiques issus de la littérature. Elles surpassent également les autres méthodes sur deux des trois problèmes d'ingénierie réels considérés.

Abstract

Blackbox optimization and derivative-free optimization are two subdisciplines of numerical optimization. They address problems which do not have an exploitable analytical formulation of objective and/or constraint functions. This absence of structure makes the deployment of usual derivative-based solvers impossible. Such problems commonly arise from numerical simulations modelling complex systems. Besides, real engineering situations have highlighted the limits of single-objective modelling. Indeed, many engineering problems involve several and often contradictory criteria, which one wants to optimize at the same time. Multiobjective optimization takes this framework into account. The resolution of such problems does not give a single optimal solution, but a set of points which represent the (potential) best trade-offs between the different objectives. Algorithms which tackle multiobjective blackbox problems are not as developed as their single-objective counterparts. For a very long time, stochastic and costly heuristics, with questionable reliability, have dominated the field of research. The generalization of deterministic and efficient single-objective methods to multiobjective blackbox optimization has only started about ten years ago and is still at its beginnings. This thesis therefore aims to explore further this research area by bringing new theoretical and practical contributions in deterministic multiobjective blackbox optimization. The increase in the development of new multiobjective methods requires all the more the conception of pertinent benchmarking tools to assess their performance and compare them. When done well, such analysis can be of great value to guide the user in the selection of the most suited algorithm to solve his/her applications. The first contribution of this thesis is a review on performance indicators for multiobjective optimization, published in European Journal of Operational Research. These performance indicators evaluate the quality of all trade-off solutions generated by a multiobjective solver on a problem. This review summarizes the properties of 63 indicators from the scientific literature, classifies them and presents main applications of these quality metrics. The second contribution is a new extension of the Mesh Adaptive Direct Search (MADS) method to multiobjective blackbox optimization. This new algorithm, denoted as DMultiMADS, is inspired by the two multiobjective blackbox solvers DMS and BiMADS. We prove that DMulti-MADS is guaranteed to converge towards a set of locally non-dominated points based on the Clarke calculus, under common directional search assumptions. To validate its performance, new data profiles for multiobjective optimization are introduced by following the recommendations of the previous survey. Numerical experiments show that Dmulti-MADS is competitive with state-of-the-art algorithms. It surpasses BiMADS when considering a small to medium budget of function evaluations. It has been published in Computational Optimization and Applications. The last contribution proposes two new strategies applied to DMulti-MADS to handle blackbox inequality constraints. Both strategies use a single constraint violation function which aggregates constraints. The goal is to minimize the constraint violation function and at the same time the objectives. We prove that these two approaches retain the convergence properties of DMulti-MADS. These two methods are compared with a penalty-based approach and the state-of-the-art solvers BiMADS, NSGA-II and DFMO, which can handle these constraints. Numerical experiments show that these two approaches are more efficient than the other algorithms on a set of analytical problems taken from the literature. They also outperform the other solvers on two of the three real engineering problems considered.