Table des matières
Romain
Contact : romain.vanden-bulcke@polymtl.ca
Directeurs
Projet : réduction de dimension dans MADS
Contexte
Le contexte général du projet est l'optimisation sans dérivées ou optimisation de boîte noire. Comme son nom l'indique, l'optimisation sans dérivées est le domaine des mathématiques appliquées qui cherche à résoudre des problèmes d'optimisation dont les dérivées de la fonction objectif ne sont pas accessibles analytiquement. En optimisation de boîtes noires, seul le résultat d'une évaluation de l'objectif et des contraintes est accessible, sans qu'on puisse connaître les mécanismes internes à la boîtes noires que l'on cherche à minimiser. En général, les boîtes noires sont coûteuses à évaluer. Le nombre total d'évaluations est limité et est considéré comme le goulot d'étranglement de ces méthodes. Dans ce cas, l'approximation des dérivées n'est pas très efficace car cela utilise beaucoup d'évaluations. Plusieurs méthodes ont été développées pour s'attaquer à ce genre de problèmes. Celle qui nous intéresse plus particulièrement est la recherche directe sur treillis adaptatif (MADS).
En général, les méthodes d'optimisation sans dérivées ou d'optimisation de boîtes noires ne s'appliquent qu'à des problèmes de quelques dizaines de variables tout au plus. Si la dimension du problème est grande, les algorithmes ont besoin de beaucoup de temps et d'évaluations pour explorer l'espace de recherche.
L'idée du ce projet est d'identifier des variables et/ou des combinaisons de variables qui ont plus d'influence sur l'objectif que les autres. Cela permet d'explorer un espace de recherche de dimension raisonnable tout en s'approchant de solutions intéressantes. On propose donc un algorithme basé sur MADS qui applique une analyse en composante principale pour identifier des liens entre les variables et l'objectif. Ensuite, l'algorithme alterne entre une recherche en petite dimension et une sonde en grande dimension.
Algorithme PCA-MADS
L'algorithme proposé, que l'on a appelé PCA-MADS, suit la même structure que MADS. Il s'agit donc d'une méthode itérative qui, à chaque itération, évalue un nombre fini de points lors de l'étape de recherche puis applique une étape de sonde si nécessaire. L'idée derrière cet algorithme est d'utiliser l'étape de recherche pour optimiser un problème en plus petite dimension.
Etape de recherche
Lors de l'étape de recherche, on cherche à identifier des sous-espaces qui sembleraient plus intéressants qui l'espace de recherche au complet. Pour ce faire, on veut en apprendre le plus possible sur la boîte noire grâce aux évaluations contenues dans la cache. Pour ce faire, on sélectionne un certain nombre de points dans la cache et on applique une analyse en composante principale sur ce nuage de points. Ensuite, on sélectionne des combinaisons linéaires des variables, les composantes principales, qui semblent avoir le plus d'impact sur l'objectif. Cela permet donc de construire un nouveau problème d'optimisation de dimension p«n. Ensuite ce nouveau problème est optimisé à l'aide d'une nouvelle instance de MADS. Les évaluations d'un point en dimension p se font en reconstruisant un point en dimension n à l'aide des composantes principales, puis en projetant ce point sur le treillis de l'instance de MADS original. Cela permet de conserver les résultats de convergence de l'algorithme.
Tests et résultats
Dans un premier temps, on a testé l'algorithme sur des problèmes simples, comme la fonction de Rosenbrock. On l'a comparé à la même implémentation mais en désactivant l'étape de recherche ainsi qu'à NOMAD.
Lorsque les problèmes sont de petites dimensions (< 20), l'algorithme ne semble pas avoir de performances intéressantes. Par contre, en plus grande dimension, il a de meilleures performances que la version originale de MADS.
Pour avoir une ensemble de problèmes plus variés, on utilise la plate-forme coco et la suite de fonctions bbob (largescale). On cherche également à comparer les performances de plusieurs méthodes sur cette suite de fonctions, dans un premier temps en petite dimension (<40), ensuite en plus grande dimension (entre 80 et 640).
Avancement et suite du projet
Les étapes suivantes du projet consiste à identifier les paramètres qui peuvent influencer les performances de l'algorithme, et trouver des valeurs qui permettent d'avoir les meilleures performances possibles.
Ensuite, l'algorithme sera comparé à d'autres méthodes d'optimisation sans-dérivées, dont certaines font appels à d'autres stratégies de réduction de dimension.
Pour finir, on voudrait appliquer l'algorithme à des boîtes noires réelles.