Peregrination Through Blackbox Optimization: Multimodality, Stochasticity and Risk Aversion

L’optimisation de boite noire porte sur le développement et l’analyse d’algorithmes conçus pour des problèmes dont la fonction objectif et/ou les contraintes ont une structure inconnue, inexploitable voire même inexistante. Ces problèmes surviennent usuellement lorsque les valeurs de la fonction objectif et des contraintes proviennent de simulations informatiques ou d’expériences menées en laboratoire. Ces situations sont courantes en ingénierie et dans certaines branches de l’apprentissage automatique. En raison de l’absence de structure des fonctions sous-jacentes aux problèmes, les approches traditionnelles les plus efficaces, fondées sur le gradient, ne peuvent être directement utilisées en optimisation de boite noire. Des stratégies doivent également être instaurées afin d’éviter aux algorithmes de converger prématurément vers une solution locale. En outre, il est fréquent que les valeurs retournées par la boite noire soient soumises à des incertitudes. Les causes à l’origine de celles-ci sont variées et peuvent être dues par exemple à la prise en compte de paramètres aléatoires, à des imprécisions sur des mesures ou encore à l’estimation de certaines quantités par la méthode de Monte-Carlo. Par conséquent, les algorithmes développés doivent avoir la capacité de gérer les fluctuations induites par les incertitudes sur la fonction objectif et les contraintes, notamment en diminuant le risque que ces dernières prennent des valeurs aberrantes. Ces différents enjeux constituent les problématiques majeures de cette thèse: l’absence de gradient, la multimodalité, la stochasticité et l’aversion au risque. Pour aborder ces problématiques, ce projet doctoral comporte trois contributions, dont la conception est agencée autour d’une unique notion: l’exploration Gaussienne de l’espace. Cette exploration consiste à échantillonner des points à partir d’une moyenne et d’un écart-type donnés. Dans une approche directe, l’algorithme se déplace directement vers un point minimisant une certaine quantité d’intérêt dépendant de la fonction objectif et/ou des contraintes. Dans une approche indirecte, les points échantillonnés sont utilisés pour estimer le gradient d’une approximation lisse de la boite noire. Ces deux approches ont pour avantage de ne pas dépendre de la dimension de la boite noire et de ne se fonder que sur les valeurs des fonctions retournées par celle-ci. Elles s’adaptent donc parfaitement au contexte de l’optimisation de boite noire. L’objectif de cette thèse est donc de développer des algorithmes autour de ces approches et d’étudier leurs propriétés de convergence ainsi que leurs efficacités en pratique. Le premier projet de la thèse traite de la problématique de la multimodalité dans un cadre de boite noire déterministe. La méthode de l’entropie croisée (CE) est intégrée dans l’algorithme de recherche directe par treillis adaptatif en tant qu’étape de recherche. Cette étape a pour but d’explorer l’espace des variables de conception et d’éviter de converger prématurément vers un minimum local. La particularité de cette étape de recherche est qu’elle n’est pas effectuée à chaque itération de l’algorithme de recherche directe par treillis adaptatifs (MADS) mais seulement lorsque la norme de l’écart-type entre les meilleurs points trouvés jusqu’alors est inférieure à un certain seuil, qui est mis à jour au fur et à mesure du processus d’optimisation. L’algorithme résultant bénéficie des propriétés de convergence de l’algorithme MADS. Des comparaisons numériques ont été menées avec d’autres algorithmes sur un ensemble de problèmes multimodaux et sur des problèmes d’ingénierie. Les résultats permettent de démontrer la compétitivité de l’algorithme sur ces types de problèmes. Le second projet de thèse aborde les problèmes d’optimisation stochastique de boite noire sans contrainte. Dans ce projet, un algorithme séquentiel (SSO) est développé afin de résoudre une suite d’approximations lisses de plus en plus fines du problème original. Chaque sous problème est résolu grâce à un algorithme de descente de gradient stochastique, appelé ZO-Signum, où les gradients sont estimés à partir d’évaluations de la boite noire seulement et dont la direction de descente est déterminée par le signe d’un vecteur moment. La particularité de cet algorithme est qu’il bénéficie d’un critère d’arrêt fondé sur la norme du vecteur moment, ce qui permet de passer d’un sous problème à l’autre. Les propriétés de convergence des deux algorithmes ont été étudiées. Lorsque la boite noire est Lipschitz continue, le taux de convergence en moyenne de l’algorithme ZO-Signum vers un point stationnaire d’une approximation lisse du problème original a été calculé. Si la boite noire est supposée C1 et est localement convexe autour de ses minima locaux, alors nous avons démontré le taux de convergence d’une sous suite d’itérés de l’algorithme SSO vers un point stationnaire du problème. Finalement, des tests numériques ont été réalisés sur une simulation de centrale solaire et pour la génération d’images adverses. Ils montrent l’efficacité de l’algorithme comparé à d’autres algorithmes de la littérature. Le troisième projet de thèse traite des problèmes d’optimisation de boite noire sous contraintes et soumis à des incertitudes aléatoires et épistémiques. La valeur conditionnelle au risque (CVaR) est utilisée pour gérer les incertitudes dans la fonction objectif et les contraintes. Cette formulation a l’avantage de pouvoir choisir le degré de fiabilité α et de traiter les incertitudes épistémiques avec une approche du pire cas lorsque α est pris suffisamment proche de 1. Pour résoudre la relaxation Lagrangienne du problème CVaR-contraint, un algorithme d’approximation stochastique à multi-échelle de temps (RAMSA) est développé. Comme dans le travail précédent, le gradient de la fonction Lagrangienne lissée est estimé à partir de valeurs retournées par la boite noire. Nous avons prouvé que l’algorithme RAMSA converge presque-sûrement vers un point réalisable du problème CVaR-contraint dont la valeur de la fonction objectif est arbitrairement proche de celle d’une solution locale. Enfin, des tests numériques ont été réalisés avec les buts suivants : établir des stratégies permettant de déterminer la valeur des hyperparamètres de l’algorithme, comparer différents estimateurs du gradient et montrer l’efficacité de l’algorithme sur des problèmes soumis à des incertitudes aléatoires et epistémiques.