Affinement de modèles substituts en optimisation de boîtes noires et en optimisation sans dérivées

Ce mémoire se situe dans un contexte d'optimisation sans dérivées, et plus particulièrement dans un contexte d'optimisation de boîtes noires, où la fonction à minimiser et les fonctions relatives aux contraintes sont de type boîte noire. Celles-ci sont potentiellement bruitées, non différentiables, coûteuses en temps de calcul et leurs dérivées sont inaccessibles, inestimables ou inexistantes. Diverses méthodes permettent de résoudre des problèmes d'optimisation de boîtes noires, dont l'algorithme de recherche par treillis adaptatifs (Mads) qui ne dirige la recherche d'optimums qu'avec les valeurs des fonctions aux points explorés. Cet algorithme itératif sépare sa recherche en deux étapes : une recherche globale qui explore l'espace des solutions et une recherche locale qui sonde autour de la meilleure solution visitée. Afin d'éviter d'évaluer inutilement la boîte noire, la recherche de Mads peut être guidée par des modèles du problème original qu'on nomme substituts. Ces modèles, moins lourds en temps de calcul, sont classés en deux catégories : les modèles statiques et les modèles dynamiques. Un modèle statique est une simplification de la boîte noire qui ne varie pas, tandis qu'un modèle dynamique est une approximation du problème mis à jour tout au long du déploiement de l'algorithme. Toutefois, les travaux précédents employant Mads n'exploitent pas simultanément les deux types de modèles. Ce travail introduit un nouveau modèle substitut, le modèle hybride quadratique (MHQ), qui s'avère être un modèle dynamique quadratique qui corrige l'information du modèle statique. Au lieu d'apporter une correction additive ou multiplicative, le MHQ vient généraliser ces deux types de correction en considérant le modèle statique comme une variable du modèle quadratique. Ce nouveau modèle est accompagné d'une base théorique solide en plus d'une analyse de convergence basée sur le calcul des fonctions non lisses. Mads exploite les valeurs fournies par le MHQ afin d'ordonner les points candidats de la recherche locale du plus prometteur au moins prometteur. Les fonctions de la boîte noire sont par la suite évaluées aux points ordonnés avec une stratégie opportuniste. Cette approche permet généralement de réduire le nombre d'évaluations de la boîte noire afin d'atteindre la convergence. Les tests numériques sont effectués sur trois problèmes analytiques et trois problèmes d'ingénierie sous forme de simulations. Les résultats obtenus montrent que l'apport du MHQ à l'algorithme Mads est de permettre une résolution des problèmes avec une plus grande précision. Le MHQ bénéficie donc du caractère global du modèle statique ainsi que de l'aspect local associé au modèle quadratique. Toutefois, l'approche par le MHQ possède des limitations, puisque son temps d'exécution est corrélé au nombre de contraintes du problème.

Abstract

The present work is in a context of derivative-free optimization, and more particularly in a context of blackbox optimization, where the function to be minimized and the functions related to the constraints are blackboxes. Those are potentially noisy, non-differentiable and computationally expensive. Furthermore, their derivatives are inaccessible or non-existent and they cannot be approximated. Various methods can be used to solve blackbox optimization problems, such as the Mesh Adaptive Direct Search (Mads) algorithm that directs the search only by using the values of the functions at the explored points. This iterative algorithm separates the search into two steps : a global search that explores the solution space and a local poll that explores near the best visited solution. In order to avoid unnecessary blackbox evaluations, the Mads steps can be guided by models of the original problem called surrogates. These models, which are less time-consuming, are classified in two categories : static models and dynamic models. A static model is a simplification of the blackbox that does not vary, while a dynamic model is an approximation of the problem updated throughout the deployment of the algorithm. However, previous work using Mads do not simultaneously exploit both models. This work introduces a new surrogate, the quadratic hybrid model (MHQ), a quadratic dynamic model that corrects information from the static model. Instead of bringing an additive or multiplicative correction, the MHQ generalizes these two types of correction by considering the static model as a variable of the quadratic model. This new model is accompanied by a solid theoretical basis in addition to a convergence analysis based on non-smooth calculus. Mads uses the values provided by the MHQ to order the candidate points of the local search from the most to the least promising. The blackbox functions are then evaluated at the ordered points with an opportunistic strategy. This approach generally reduces the number of blackbox evaluations to achieve convergence. The numerical tests are performed on three analytical problems and three simulation-based engineering problems. The obtained results show that the contribution of the MHQ to the Mads algorithm is to solve problems with a greater precision. The MHQ thus benefits from the global feature of the static model as well as from the local aspect of the quadratic model. However, the MHQ approach has limitations, since its execution time is correlated with the number of problem constraints.