Jean-Bernard Lasserre, ERC Advanced Grant 2014
Jean-Bernard Lasserre, chercheur CNRS au sein du Laboratoire d’Analyse et d’Architecture des Systèmes (LAAS-CNRS), est un provocateur. Pour le titre de son ERC Advanced Grant TAMING, il a choisi « Domestiquer la non-convexité ? » pour mettre en avant un objectif qui semble au premier abord inatteignable : résoudre des problèmes d’optimisation considérés comme trop complexes pour une résolution « efficace ». Sa solution ? Une méthode qui remplace le problème initial difficile par une suite de problèmes de taille croissante que l’on sait résoudre. Un objectif ambitieux car l’optimisation est partout : ses travaux s’appliquent déjà entre autres aux réseaux d’énergie de grande taille.
En optimisation, la classe des problèmes dits « convexes » (lorsque certaines propriétés mathématiques sont satisfaites) est très importante car on sait résoudre ces problèmes de façon « efficace » (au sens de la complexité algorithmique). À l’inverse, on conjecture qu’il n’y a pas d’algorithme efficace (du moins dans tous les cas) pour résoudre les problèmes non convexes. L’ambition de l’ERC TAMING « Domestiquer la non-convexité ? » est précisément de résoudre une (grande) classe de problèmes non convexes, grâce à une nouvelle approche : la méthodologie « moments-sommes de carrés » dont Jean-Bernard Lasserre est l’un des pionniers. L’idée est de remplacer le problème initial qu’on ne sait pas résoudre de façon efficace par une suite de problèmes convexes (ou « hiérarchie de relaxations »), en principe « faciles » à résoudre, mais de taille croissante : une version relâchée (mais convexe) du problème initial est d’abord résolue, puis une version un peu plus complexe (mais toujours convexe), etc. La taille du problème convexe croît avec son rang dans la hiérarchie (et donc sa résolution devient aussi de plus en plus difficile). Dans la plupart des cas on a résolu le problème initial à une certaine étape de la hiérarchie mais malheureusement, pour un problème initial donné, il n’est pas possible de savoir à l’avance à quelle étape de la hiérarchie on peut s’arrêter. Cette méthodologie a constitué un apport important non seulement dans la communauté « optimisation » mais aussi dans la communauté des chercheurs en « complexité algorithmique » qui ont qualifié cet algorithme de « méta-algorithme » car il est devenu un outil privilégié pour confirmer ou infirmer la conjecture « Unique Games » de S. Khot sur la difficulté d’approximation de tout une classe importante de problèmes d’optimisation combinatoire, un défi scientifique majeur dans cette communauté. Cette problématique pour aborder la résolution de problèmes non convexes a d’ailleurs été mise en avant dans les derniers rapports de prospective du conseil scientifique de l’INS2I et de l’INSMI.
TAMING a donc pour objectif de fournir une méthodologie systématique pour la résolution des problèmes d’optimisation décrits par des polynômes (ou des fonctions semi-algébriques) que l’on retrouve dans pratiquement tous les domaines et applications des sciences. Cette méthodologie peut aussi s’appliquer à des problèmes au-delà de l’optimisation, et notamment au « Problème Généralisé des Moments » (PGM) dont la liste des applications importantes est sans fin et dont l’optimisation polynomiale n’est qu’une instance particulière (et même en fait la plus simple !).
Outre son utilisation théorique en complexité algorithmique, et calcul et information quantiques, la méthodologie « moments-sommes de carrés » est déjà utilisée dans de nombreuses applications pratiques (notamment en optimisation, contrôle, vision par ordinateur, etc.). Plus récemment, elle semble devenir une méthode prometteuse pour l’optimisation des réseaux d’énergie de grande taille, qu’ils soient électriques ou hydrauliques. Même si ces problèmes sont de grande taille (car modélisés avec énormément de variables), ils ont une propriété importante dont on peut tirer partie. En effet, bien que nombreuses dans la description du problème global, les variables apparaissent avec « parcimonie » c’est-à-dire que chaque contrainte du problème ne fait apparaître que peu de variables dans sa description. On peut donc faire de nombreux mais petits sous-groupes de variables qui peuvent ensuite être exploités efficacement dans la résolution des problèmes de la hiérarchie.
Mais les promesses de cette méthodologie nouvelle seront tenues à condition de faire sauter un verrou scientifique décisif. En effet, de par son coût de calcul important (du moins dans sa forme standard actuelle) du à la taille croissante des problèmes convexes dans cette hiérarchie, cette méthodologie est limitée à la résolution de problèmes de taille relativement modeste (sauf quand, comme dans le cas des réseaux d’énergie, une certaine parcimonie dans la description du problème peut être exploitée). Un premier défi est donc de faire évoluer ou peut-être même changer cette méthodologie pour pouvoir attaquer des problèmes de grande taille. Un deuxième défi est de valider cette méthodologie sur de nouvelles applications modélisées comme une instance du problème généralisé des moments.