The quest of modeling, certification and efficiency in polynomial optimization
Résumé
Certified optimization techniques have successfully tackled challenging verification problems in various fundamental and industrial applications. The formal verification of thousands of nonlinear inequalities arising in the famous proof of Kepler conjecture was achieved in August 2014. In energy networks, it is now possible to compute the solution of large-scale power flow problems with up to thousand variables. This success follows from growing research efforts in polynomial optimization, an emerging field extensively developed in the last two decades. One key advantage of these techniques is the ability to model a wide range of problems using optimization formulations, which can be in turn solved with efficient numerical tools.
My methodology heavily relies on such methods, including the moment-sums of squares (moment-SOS) hierarchy by Lasserre which provides numerical certificates for positive polynomials as well as recently developed alternative methods. However, such optimization methods still encompass many major issues on both practical and theoretical sides: scalability, unknown complexity bounds, ill-conditioning of numericalsolvers, lack of exact certification, convergence guarantees. This manuscript presents results along these research tracks with the long-term perspective of obtaining scientific breakthroughs to handlecertification of nonlinear systems arising in real-world applications. In the first part, I focus on modeling aspects. One relies on the moment-SOS hierarchy to analyze dynamical polynomial systems, either in the discrete-time or continuous-time setting, and problems involving noncommuting variables, for example matrices of finite or infinite size, to model quantum physics operators. In the second part, I describe how to design and analyze algorithms which output exact positivity certificates for either unconstrained or constrained optimization problems. In the last part, I explain how to improve the scalability of the hierarchy by exploiting the specific sparsity structure of the polynomial data coming from real-world problems. Important applications arise from various fields, including computer arithmetic (roundoff error bounds), quantum information (noncommutative optimization), and optimal power-flow.
Les techniques d'optimisation garantie ont permis de résoudre plusieurs problèmes de vérification notoirement difficiles, dans des domaines académiques et industriels. La vérification formelle des dizaines de milliers d'inégalités non-linéaires apparaissant dans la preuve célèbre de la conjecture de Kepler a été achevée en Août 2014. Il est aujourd'hui possible de calculer la solution de problèmes d'optimisation de réseaux électriques faisant intervenir plusieurs milliers de variables. Ces succès sont la conséquence d'efforts croissants de recherche en optimisation polynomiale, un domaine émergent qui s'est rapidement développé au cours des vingt dernières années. L'avantage clé de ces techniques est leur capacité de modéliser une large classe de problèmes à l'aide de reformulations dans le paradigme de l'optimisation, afin de permettre leur résolution avec des outils numériques efficaces. Ma méthodologie repose sur l'utilisation de telles méthodes, en particulier la hiérarchie moments-sommes de carrés (moment-SOS) développée par Lasserre, qui fournit des certificats numériques pour les polynômes positifs, ainsi que des méthodes alternatives récemment développées. Néanmoins, certains problèmes freinent l'utilisation de ces méthodes d'optimisation : passage à l'échelle, bornes de complexité inconnues, conditionnement des solveurs numériques, absence de certification rigoureuse, absence de garanties de convergence. Ce manuscrit présente plusieurs résultats pour pallier à certains de ces problèmes, avec la perspective à long terme d'obtenir des avancées scientifiques pour certifier des systèmes non-linéaires provenant d'applications du monde réel. Dans la première partie du manuscrit, je m'intéresse à des aspects de modélisation. La hiérarchie moment-SOS est utilisée pour analyser des systèmes à dynamique polynomiale, dans un cadre discret ou continu, ainsi que des problèmes faisant intervenir des variables non-commutatives, par exemple des matrices de taille finie ou infinie, afin de modéliser des opérateurs de physique quantique.
Dans la seconde partie du manuscrit, je décris comment mettre au point et analyser des algorithmes qui calculent des certificats exacts de positivité, pour des problèmes d'optimisation avec ou sans contraintes. Dans la dernière partie du manuscrit, j'explique comment améliorer le passage à l'échelle de la hiérarchie, en exploitant la structure spécifique des données polynomiales provenant d'applications réelles, telles que l'arithmétique des ordinateurs (bornes d'erreur flottante), l'information quantique (optimisation non-commutative) et les réseaux électriques.
Origine : Fichiers produits par l'(les) auteur(s)