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.

Abstract

Blackbox optimization is concerned with the development and analysis of algorithms designed for problems where the objective function and/or constraints have an unknown, non-exploitable or even non-existent structure. These problems usually arise when the values of the objective function and constraints are obtained using computer simulations. Such situations are common in engineering and in some branches of machine learning. Due to the lack of structure of the functions underlying the problems, the most efficient traditional gradient-based approaches cannot be used directly in blackbox optimization. Strategies must also be introduced to prevent algorithms from converging prematurely to a local solution. In addition, the values returned by the blackbox are often subject to uncertainties. These uncertainties are caused by a variety of factors, such as random parameters, inaccuracies in measurements, or the estimation of certain quantities using the Monte Carlo method. Consequently, the algorithms developed must be capable of handling the perturbations induced by uncertainties in the objective function and constraints, in particular by minimizing the risk of outlier values. These issues are the main concerns of this thesis: gradient absence, multimodality, stochasticity and risk aversion. To address these issues, this thesis consists of three contributions, designed around a single notion: Gaussian exploration of space. This exploration consists of sampling points from a given mean and standard deviation. In a direct approach, the algorithm moves directly to a point minimizing a certain quantity of interest, depending on the objective function and/or constraints. In an indirect approach, the sampled points are used to estimate the gradient of a smooth blackbox approximation. The advantage of both approaches is that they do not depend on the size of the blackbox, and are based only on the output values returned by the blackbox. Therefore, they are perfectly suited to the context of blackbox optimization. Thus, the aim of this thesis is to develop algorithms based on these approaches and to study their convergence properties as well as their effectiveness in practice. The first contribution deals with the problem of multimodality in a deterministic blackbox framework. The Cross Entropy (CE) method is integrated into the Mesh Adaptive Direct Search (MADS) algorithm as a search step. The aim of this step is to explore the space of design variables and avoid converging prematurely to a local minimum. Its peculiarity is that it is not performed at each iter-ation of the MADS algorithm, but only when the norm of the standard deviation is below a certain threshold, which is updated as the optimization process progresses. The resulting algorithm benefits from the convergent properties of the MADS algorithm. Numerical comparisons with other algorithms have been performed on a set of multimodal and engineering problems. The results demonstrate the competitiveness of the algorithm on these types of problems. The second contribution deals with unconstrained stochastic blackbox optimization problems. A Sequential Stochastic Optimization (SSO) algorithm is developed to solve a sequence of increasingly finer smooth approximations of the original problem. Each subproblem is solved using a stochastic gradient descent algorithm called ZO-Signum, where gradients are estimated only from blackbox evaluations and the descent direction is determined by the sign of a momentum vector. The particularity of this algorithm is that it benefits from a stopping criterion based on the norm of the momentum vector, which allows to switch from one subproblem to another. The convergence properties of both algorithms have been studied. When the blackbox is assumed Lipschitz continuous, the convergence rate in mean of the ZO-Signum algorithm to a stationary point of a smooth approximation of the original problem has been calculated. If the blackbox is assumed C1 and is locally convex around its local minima, then a subsequence of iterates of the SSO algorithm is proved to converge to a stationary point. The convergence rate is also analyzed. Finally, numerical tests have been conducted on a simulation of a solar power plant and for the generation of adversarial images. They show the efficiency of the algorithm compared to other state-of-the-art algorithms. The third contribution deals with blackbox constrained optimization problems subject to aleatory and epistemic uncertainties. Conditional value at risk is used to manage uncertainties in the objective function and constraints. This formulation has the advantage of being able to choose the degree of reliability α and to handle epistemic uncertainties with a worst case approach when α is taken sufficiently close to 1. To solve the Lagrangian relaxation of the Conditional Value-at-Risk (CVaR)-constrained problem, a Risk-Averse Multi-timescale Stochastic Approximation (RAMSA) algorithm is introduced. As in the previous contribution, the gradient of the smoothed Lagrangian function is estimated from values returned by the blackbox. Under mild assumptions, the RAMSA algorithm almost surely converges to a feasible point of the CVaR-constrained problem whose objective function value is arbitrarily close to that of a local solution. Finally, numerical tests have been performed with the following goals: to establish strategies for determining the value of the hyperparameters; to compare different gradient estimators and to demonstrate the effectiveness of the algorithm on problems subject to aleatory and epistemic uncertainties.