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.

Abstract

Computational optimization is ubiquitous in many communities and has attracted an unparalleled interest during the last decades due to the growing use of computer simulations when solving complex problems arising in a plethora of fields, especially in engineering. Blackbox optimization (BBO), a major theme in the present thesis, does not assume the existence of derivatives and focuses on problems where the objective and constraint functions are given by a blackbox, typical examples of which are computer simulations. For many of such problems arising in machine learning, signal processing, medicine and biology to name a few, the target deterministic objective function and constraints can only be accessed through a blackbox corrupted by some random noise, thus resulting in stochastic BBO problems. Even though developing provable algorithms for stochastic optimization has recently received renewed interest, most of derivative-free optimization (DFO) methods either use estimated gradient informations, are restricted to unconstrained problems, or assume that the constraints are deterministic. Thus, direct-search methods known to be reliable and robust in practice appear to be the most promising approach for BBO problems. However in stochastic BBO, there is relatively scarce research on developing direct-search methods with full-supported convergence analysis especially when constraints function evaluations are also corrupted by some random noise. This thesis therefore focuses on the development and convergence analysis of direct-search methods for stochastic BBO. The first project of this thesis introduces a stochastic extension of the mesh adaptive direct-search (MADS) algorithm originally designed for deterministic BBO. The proposed method called StoMADS considers the unconstrained optimization of an objective function when only having access to its noisy evaluations available through a blackbox corrupted by some random noise following an unknown distribution. Thus, since the exact deterministic values of the underlying objective function are not available, their estimates obtained from stochastic observations are used. By requiring the accuracy of such estimates to hold with a large but fixed probability and by assuming them to satisfy a variance condition, a Clarke stationarity convergence result of StoMADS is proved by means of martingale theory. Computational studies comparing StoMADS to algorithms available in the NOMAD BBO software revealed that the proposed method is very promising for real-life applications. The second project generalizes the algorithmic framework of StoMADS by introducing a broad class of stochastic directional direct-search (SDDS) algorithms which accept new iterates by imposing a sufficient decrease condition on function estimates required to satisfy the same StoMADS assumptions. By assuming in addition the objective function to be differentiable, the expected complexity of SDDS is analyzed making use of an existing supermartingale-based framework. Despite using no gradient information unlike prior methods such as stochastic line-search and stochastic trust-region methods, the convergence rate of SDDS is shown to be similar to that of both latter methods and to that of the broad class of deterministic directional direct-search methods which accept new iterates using a sufficient decrease condition. By introducing the StoMADS-PB algorithm, the third project of the thesis focuses on the constrained stochastic BBO. The proposed method is a stochastic extension of the MADS method using a progressive barrier (PB) approach for constraints handling, originally developed for deterministic BBO under general constraints. Similarly to the framework of StoMADS, the objective and constraints function values can only be computed through a noisy blackbox. Constraints are treated by StoMADS-PB by aggregating their corresponding violations into a single constraint violation function. Since all the underlying deterministic functions values are not available, estimates are used and so-called probabilistic bounds are introduced for the violation function. By requiring such estimates and bounds to be accurate and reliable with sufficiently high but fixed probabilities, Clarke stationarity results for the objective and the violation function are derived with probability one, making use of the Clarke nonsmooth calculus and martingale theory. Numerical experiments conducted on 126 stochastic variants of 42 constrained problems from literature demonstrated StoMADS-PB to outperform MADS with PB.