Optimisation sans dérivées sous contraintes

L'optimisation sans dérivées (Derivative-Free Optimization, DFO) et l'optimisation de boîtes noires (Blackbox Optimization, BBO) est un champ de la recherche opérationnelle en pleine extension, qui correspond à de nouveaux problèmes pour lesquels toutes les fonctions en jeu ou seulement une partie ne sont pas connues analytiquement mais sont le résultat d'expériences ou de simulations numériques, appelées communément boîtes noires. Les contraintes peuvent être de différentes natures. Elles peuvent être connues analytiquement ou bien elles peuvent être, comme la fonction objectif, le résultat de la boîte noire. Elle peuvent même être ignorées de l'utilisateur qui les découvre malgré lui, alors qu'il cherche à évaluer la boîte noire en un point qu'il pensait être réalisable. Elles peuvent être lisses ou non lisses. Cette thèse s'intéresse plus particulièrement aux traitements des contraintes dans le cadre de l'optimisation sans dérivées et de l'optimisation de boîtes noires. Il s'agit donc de proposer de nouvelles techniques pour résoudre des problèmes sous contraintes. Tout d'abord, une méthode générique de traitement des égalités linéaires est proposée. Différents convertisseurs sont utilisés afin de reformuler le problème initial en un problème réduit dans le sous-espace affine défini par les égalités linéaires. Différentes stratégies combinant en plusieurs étapes ces convertisseurs sont proposées. Une implémentation de cette technique dans un algorithme de recherche directe, MADS, utilisant le logiciel NOMAD, est réalisée. À partir de tests numériques, une stratégie est retenue. Elle surpasse sur les problèmes testés un autre logiciel de recherche directe, HOPSPACK, qui proposait déjà un traitement spécifique des contraintes d'égalités linéaires. De plus, notre méthode est adaptable à tous les algorithmes existants. Ensuite, un algorithme hybride, combinant des outils issus de l'optimisation sans dérivées, basée sur les modèles, et ceux de l'optimisation de boîtes noires, basée sur des méthodes de recherche directe, est proposé à travers un algorithme de région de confiance sans dérivées (Derivative-Free Trust-Region, DFTR) qui revisite la barrière progressive déjà proposée dans MADS, et qui permet de traiter certains types de contraintes d'inégalités. L'algorithme obtenu offre des résultats compétitifs avec un représentant de l'optimisation sans dérivées, COBYLA, et un représentant de l'optimisation de boîtes noires, MADS, à partir de tests réalisés sur un panel de problèmes académiques mais aussi sur deux boîtes noires issues de l'optimisation multidisciplinaire. Enfin, un dernier algorithme sans dérivées a été développé, afin de pouvoir résoudre des problèmes avec des contraintes générales d'égalités ou d'inégalités, et qui utilise une méthode classique de Lagrangien augmenté. L'algorithme utilisant le Lagrangien augmenté sert à résoudre le sous-problème de la région de confiance mais aussi à définir les règles de mise à jour de l'algorithme. Des résultats sur des problèmes académiques permettent de conclure quant à la validité de la méthode.

Abstract

Derivative-Free Optimization (DFO) and Blackbox Optimization (BBO) are growing optimization fields. The goal is to handle new problems involving functions for which analytical expressions are not explicit, but which are the results of simulations or experiments, called blackboxes. Different kind of constraints can be encountered. Their analytical expressions can be given, or they can be the result of the blackbox. They can even be hidden, and not known by the user. They can be smooth or nonsmooth. This thesis focuses more specificaly on the contraints in DFO and BBO, and its goal is to develop new techniques to solve constrained problems. First, a generic method for linear equalities is proposed. Different converters are used to reformulate the initial problem into a reduced one, in the subspace defined by the linear equalities. Different strategies combining these converters in multi-step algorithms are proposed. Theses techniques are implemented in a direct-search algorithm, MADS, by using the solver NOMAD. Computational tests allow to choose the best strategy with the best results. On a benchmark of analytical problems our algorithm outperforms a direct-search algorithm implemented in the solver HOPSPACK, which also handles directly linear equalities. The proposed method is transposable to any other DFO or BBO algorithm. hen, a derivative-free trust-region (DFTR) algorithm combining DFO tools, based on models, and BBO tools, based on direct-search techniques, is proposed through a (DFTR) algorithm. The progressive barrier first designed for MADS is revisited and allows to solve general inequalities in this new DFTR algorithm. The new algorithm offers competitive results with COBYLA, a DFO software and NOMAD, a BBO software. Computational experiments are conducted on a set of analytical problems and two blackboxes from multidisciplinary design optimization. Finally, a third DFO algorithm is proposed, allowing to solve equality and inequality constrained problems, by using an augmented Lagrangian method. This one is used to solve the trust-region subproblem but also to design simple update rules for the DFTR algorithm. Computational results on analytical problems validate our method.