Linear Inequality Constraints in Blackbox Optimization

L’optimisation de boîtes noires est une branche de l’optimisation permettant de traiter des problèmes où aucune information n’est disponible sur la fonction objectif à minimiser ni sur les contraintes à respecter. Le Mesh Adaptive Direct Search (MADS) est un cadre algorithmique permettant de traiter des problèmes d’optimisation de boîtes noires. Celui-ci possède de fortes propriétés de convergence comparativement à des heuristiques populaires. À ce jour aucune stratégie dédiée n’existe dans MADS ni dans NOMAD, son implémentation C++, pour le traitement de contraintes d’inégalité linéaires connues. Ce mémoire s’intéresse au traitement efficace de ce type de contraintes pour des problèmes d’optimisation de boîtes noires, plus précisément, au cas où ces contraintes sont non relax-ables. Quatre stratégies sont proposées: la barrière extrême à priori (APEB), la projection de norme euclidienne (L2), le préconditionnement de bornes (VBP) et l’accrochage aux con-traintes (SC). Les trois premières modifient MADS de manière à projeter ou rejeter des points d’évaluation qui sont hors de l’ensemble défini par le système d’inégalités linéaires. Une version préliminaire de ces stratégies est intégrée au logiciel NOMAD, une implémentation C++de MADS. Les domaines d’intérêts de l’optimisation de boîtes noires sont nombreux. Pour certaines applications, l’évaluation de la fonction objectif et des contraintes représente un coût temporel ou monétaire non négligeable. L’approche proposée permettra éventuellement à NOMAD d’offrir de meilleures solutions pour un nombre réduit d’appel à la boîte noire en exploitant les cas où des contraintes d’inégalité linéaires connues sont présentes. D’une part, l’efficacité des différentes approches proposées est évaluée à l’aide d’expériences sur une simulation de centrale solaire et, d’autre part, de problèmes analytiques de la littérature. Les résultats montrent que la stratégie L2 à base de projection de norme euclidienne performe mieux globalement sur les problèmes considérés tout en conservant les propriétés de convergence de MADS.

Abstract

Blackbox optimization is an optimization branch that deals with problems where information about the objective function and constraints is unavailable. Each time the blackbox is called with a given input, it provides an output that consists of the values of the objective function and the constraints, if they exist. In practice, blackbox calls can have a computationally or a monetary expensive cost. This cost is generally monetary or temporal. Partial information can be available for a given problem, such as the explicit form of some constraints or structural properties. While blackbox methods must be employed, the inherent structure of the problem should be exploited to reduce the cost due to the blackbox calls. This work proposes strategies to handle efficiently explicit unrelaxable linear inequality con-straints within the Mesh Adaptive Direct Search (MADS) method. MADS is an algorithmic framework designed to solve blackbox optimization problems. A dedicated strategy com-patible with this framework is developed to handle the aforementioned type of constraints efficiently. This work proposes four strategies: the A Priori Extreme Barrier (APEB), the Snap-To-Constraints (SC), the L2 Norm Projection (L2), and the variable bounds preconditioning (VBP), to handle them. Their compatibility with MADS ensures they inherit its strong convergence properties. The strategies are developed in NOMAD, a C++MADS implementation. Numerical exper-iments are run on a set of problems related to both a solar power plant simulation and analytical problems from the literature. Results demonstrate that L2, a strategy that uses a euclidian norm projection on the set formed by the linear inequalities, performs best. The proof of concept presented in this work implies that future versions of the NOMAD software could be able to handle linear inequality constraints to provide better solutions to its users in fewer blackbox evaluations.