Analyse de sensibilité pour la réduction de dimension en optimisation sans dérivée

A l'heure actuelle, le monde industriel regorge de processus et de calculs complexes et l'optimisation de ceux-ci se retrouve au cœur de la recherche et du développement d'entreprises. Ces problèmes ont souvent des caractéristiques qui nécessitent de faire appel à des méthodes d'optimisation sans dérivée. Il s'agit d'algorithmes d'optimisation qui permettent de gérer des fonctions non linéaires, non différentiables, bruitées ou encore non définies en certains points du domaine. La classe d'algorithme Mads rassemble des méthodes qui permettent de résoudre des problèmes contraints sous forme de boîtes noires correspondant aux résultats d'un code informatique. Par ailleurs, l'exploration d'un espace de recherche dont aucune information n'est disponible nécessite un grand nombre d'évaluations. Néanmoins, l'évaluation d'une boîte noire est souvent coûteuse; ceci constitue la principale difficulté du domaine, la recherche d'un minimum d'une boîte noire en un nombre limité d'évaluations. Cette limite du budget d'évaluations et d'autant plus importante lorsque le problème d'intérêt est de grande dimension. Il s'agit de la principale motivation pour appliquer une méthode de réduction de dimension au cours de l'optimisation du problème. L'algorithme Stats-Mads applique tout d'abord une méthode d'analyse de sensibilité basée sur une analyse de variance pour identifier les variables ayant le plus d'influence sur l'objectif. Ensuite, l'algorithme alterne entre une optimisation en petite dimension, où les variables les moins influentes sont fixées, et une optimisation en grande dimension. Les phases d'optimisation en petite dimension ont un rôle prépondérant dans la diminution de la valeur de l'objectif, et donc dans l'optimisation du problème. Nous proposons un nouvel algorithme de la classe Mads qui permet de s'attaquer à des problèmes de grande dimension. Celui-ci applique une analyse de sensibilité basée sur une analyse en composante principale qui permet d'extraire des combinaisons de variables ayant le plus d'impact sur la fonction objectif. Cet algorithme a donc été nommé Pca-Mads. D'une manière similaire à Stats-Mads, l'algorithme Pca-Mads alterne entre une optimisation en petite et en grande dimension. Toutefois, la structure de l'algorithme permet de poursuivre l'optimisation en petite dimension tant que celle-ci fournit des solutions améliorant la valeur de la fonction objectif. L'algorithme Pca-Mads, principalement basé sur l'instance LTMads, a été implémenté en MATLAB™. A la lumière des résultats obtenus sur des problèmes allant jusqu'à 1500 variables, l'algorithme Pca-Mads est comparé à d'autres algorithmes d'optimisation sans dérivée dont CMA-ES, Mads et principalement Stats-Mads afin de pouvoir conclure de ses performances. Ces tests indiquent clairement l'intérêt de l'approche de Pca-Mads.

Abstract

In today's industry, the look for highest productivity at smallest costs naturally creates optimization problems. Precise models often create complex problems along with the need for derivative free optimization methods. Those are methods which can handle non-linear, non-differentiable or noisy objective functions. Mads algorithms are well-known black box optimization methods which solve this type of problem through calls to a black box, i.e. some kind of computer code. When little is known about the problem, the exploration of the search space requires a large number of black box evaluations. However, in the context of black box optimization, problems take the form of expensive-to-evaluate functions. The total number of evaluations is therefore very limited and this constitutes the main challenge of the field. When considering black box problems in large dimensions, the limited budget of evaluations is even more constraining. Standard black box algorithms need to be adapted, for example through dimension reduction scheme. Stats-Mads is a Mads-based algorithm which applies an analysis of variance to rank most influential input variables. Then the method alternates between optimizing the problem in a smaller dimension, where least influential variables were fixed, and the problem in its original large dimension. Most of the improvement of the objective value was done during the optimization in the small dimension. We propose a new Mads algorithm conceived to handle large-scale black box problems. This method applies a principal component analysis to identify most influential directions in the search space and is called Pca-Mads. Similarly to Stats-Mads, Pca-Mads alternates between an optimization in a smaller dimension, where the input can only evolve in the few most influential directions, and a poll in the large dimension. However, its structure allows to skip the poll in the large dimension as long as the optimization in the smaller dimension generates new improving solutions. A MATLAB™ implementation of the Pca-Mads method, based on the LTMads instance was run on problems of up to 1500 variables. Its performances are compared to other derivative free methods such as CMA-ES, Mads and mainly Stats-Mads. The results of these tests clearly indicate the value of the approach developed for Pca-Mads.