Méthodes de recherche directe pour l'optimisation stochastique de boîtes noires

L'optimisation informatique est omniprésente dans de nombreuses communautés et a suscité un intérêt sans précédent au cours des dernières décennies en raison de l'utilisation croissante des simulations informatiques pour la résolution de problèmes complexes survenant dans une multitude de domaines et plus particulièrement en ingénierie. “L'optimisation de boîtes noires”, thème majeur de cette thèse, n'émet aucune hypothèse sur l'existence de dérivées des fonctions ciblées et se concentre sur des problèmes où la fonction objectif ainsi que les contraintes sont données par une boîte noire dont les simulations informatiques constituent un exemple typique. Les valeurs exactes de ces fonctions déterministes au moyen desquelles sont modélisés les problèmes couramment rencontrés dans le domaine de l'apprentissage automatique, du traitement du signal, de la médecine ainsi que la biologie etc., ne sont en général pas toujours accessibles numériquement. En effet, elles ne peuvent parfois être obtenues que par le biais d'une boîte noire dont les évaluations sont corrompues par un bruit aléatoire, engendrant ainsi des problèmes d'optimisation stochastique de boîtes noires. Par ailleurs, même si la conception d'algorithmes performants d'optimisation stochastique a suscité un regain d'intérêt ces dernières années, il est à noter que la plupart des méthodes d'optimisation dites sans dérivée utilisent des approximations de gradient, se limitent à des problèmes sans contraintes ou sinon, supposent que ces dernières sont déterministes. Ainsi, les méthodes de recherche directe connues pour leur fiabilité et leur robustesse en pratique s'avèrent plus prometteuses pour les problèmes d'optimisation de boîtes noires. Cependant, force est de constater qu'assez rares sont les travaux portant sur la conception d'algorithmes de recherche directe pour l'optimisation stochastique de boîtes noires, dotés d'une preuve de convergence et surtout en présence de contraintes bruitées aléatoirement. Cette thèse se concentre alors sur la conception ainsi que l'analyse de convergence d'algorithmes de recherche directe pour l'optimisation stochastique de boîtes noires. Le premier projet de la présente thèse introduit une variante stochastique de l'algorithme de recherche directe par treillis adaptatif (MADS) initialement conçu pour l'optimisation de boîtes noires déterministes. La méthode proposée nommée StoMADS considère l'optimisation sans contrainte d'une fonction objectif dont les valeurs ne peuvent être obtenues que via une boîte noire corrompue par un bruit aléatoire de distribution inconnue. Étant donné que les valeurs déterministes exactes de ladite fonction sous-jacente ne sont pas accessibles numériquement, StoMADS fait usage de leurs estimés obtenus à partir d'observations aléatoires. En supposant ces estimés précis avec une probabilité suffisamment grande mais fixe, et de variance satisfaisant une certaine condition, un résultat de convergence de StoMADS a été obtenu grâce au calcul non lisse de Clarke et la théorie des martingales. Des études numériques comparant StoMADS à certains algorithmes disponibles dans le logiciel NOMAD d'op-timisation de boîtes noires, ont révélé la méthode proposée très prometteuse pour des applications concrètes. Le second projet généralise le cadre algorithmique de StoMADS en introduisant une large classe d'algorithmes de recherche directe dits de type directionnel, pour l'optimisation stochastique de boîtes noires (SDDS), et qui acceptent de nouveaux itérés en imposant une condition de décroissance suffisante à des estimés satisfaisant les mêmes hypothèses du premier projet. Sous une hypothèse supplémentaire de différentiabilité de la fonction objectif déterministe numériquement inaccessible, le taux de convergence de la méthode proposée a été étudié à l'aide des supermartingales. Quoique ne faisant usage d'aucune information de gradient contrairement à des méthodes existantes telles que la recherche linéaire stochastique ainsi que les algorithmes de région de confiance stochastiques, le taux de convergence de SDDS est similaire à celui des deux dernières méthodes et à celui de la large classe d'algorithmes de recherche directe déterministes de type directionnel qui acceptent également de nouveaux itérés en imposant une condition de décroissance suffisante. Le troisième projet de cette thèse introduit StoMADS-PB, un algorithme d'optimisation stochastique de boîtes noires sous contraintes. StoMADS-PB est une variante stochastique de l'algorithme MADS utilisant une approche de barrière progressive (PB) pour la gestion des contraintes, initialement conçu pour l'optimisation de boîtes noires déterministes sous contraintes générales. Similairement à StoMADS, les valeurs de la fonction objectif et des contraintes sont accessibles uniquement via une boîte noire bruitée aléatoirement. Ainsi, StoMADS-PB utilise également des estimés et par ailleurs, traite les contraintes en regroupant leurs violations en une seule fonction de violation de contrainte. Sous l'hypothèse que ces estimés sont précis et fiables avec des probabilités suffisamment grandes mais fixes, des résultats de convergence de la méthode vers des points stationnaires au sens de la dérivée généralisée de Clarke des fonctions objectif et de violation, ont été obtenus grâce à la théorie des martingales. Enfin, des expériences numériques menées sur 126 variantes stochastiques de 42 problèmes sous contraintes tirés de la littérature ont démontré l'efficacité de StoMADS-PB par rapport à MADS avec PB pour l'optimisation stochastique de boîtes noires.