Un environnement pour l'optimisation sans dérivées

L'optimisation sans dérivées (DFO) est une branche particulière de l'optimisation qui étudie les problèmes pour lesquels les dérivées de l'objectif et/ou des contraintes ne sont pas disponibles. Généralement issues des simulations, les fonctions traitées peuvent être coûteuses à évaluer que ce soit en temps d'exécution ou en mémoire, bruitées, non dérivables ou simplement pas accessibles pour des raisons de confidentialité. La DFO spécifie des algorithmes qui se basent sur divers concepts dont certains ont été spécialement conçus pour traiter ce type de fonctions. On parle aussi parfois de boîtes grises ou noires pour souligner le peu d'information disponible sur la fonction objectif et/ou les contraintes. Il existe plusieurs solveurs et boîtes à outils qui permettent de traiter les problèmes de DFO. Le but de ce mémoire est de présenter un environnement entièrement développé en Python qui regroupe quelques outils et modules utiles dans un contexte de DFO, ainsi que quelques solveurs. Cet environnement a la particularité d'être écrit de façon modulaire. Cela permet une liberté à l'utilisateur en termes de manipulation, personnalisation et développement d'algorithmes de DFO. Dans ce mémoire, on présente la structure générale de la bibliothèque fournie, nommée DFO.py, ainsi que les détails des solveurs implémentés, en précisant les parties qui peuvent être modifiées et les différentes options disponibles. Une étude comparative est aussi présentée, le cas échéant, afin de mettre en évidence l'effet des choix des options utilisées sur l'efficacité de chaque solveur. Ces comparaisons sont visualisées à l'aide de profils de performance et de données que nous avons aussi implémentés dans un module indépendant nommé Profiles.py. Mots clés : Optimisation sans dérivées, optimisation de boîte noire, Python, profils de performance, profils de données.

Abstract

Derivative free optimization (DFO) is a branch of optimization that aims to study problems for which the derivatives of the objective function and/or constraints are not available. These functions generally come from simulation problems, therefore calling a function to evaluate a certain point can be expensive in terms of execution time or memory. The functions can be noisy, non diffrentiable or simply not accessible. DFO algorithms use different concepts and tools to adjust to these special circumstances in order to provide the best solution possible. Sometimes, the terms grey box or black box optimisation can also be used to emphasize the lack of information given about the objective function. There is a rich literature of solvers and toolboxes specialized in DFO problems. Our goal is to provide a Python environment called DFO.py, that regroups certain tools and modules that can be used in a DFO framework. The modular implementation of this environment is meant to allow a certain freedom in terms of modifying and customizing solvers. In this document, we present the general structure of DFO.py as well as the implementation details of each solver provided. These solvers can be modified by changing certain options that are mentioned in their respective sections. We also provide a benchmark study to compare the results obtained with each version of the same solver. This benchmark is done using performance and data profiles, which are part of an independent module called Profiles.py also presented in this document. Key words: Derivative free optimization, black box optimization, performance profile, data profile, Python.