Skip to Main content Skip to Navigation
Accreditation to supervise research

The quest of modeling, certification and efficiency in polynomial optimization

Victor Magron 1 
1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : 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.
Document type :
Accreditation to supervise research
Complete list of metadata

https://hal.laas.fr/tel-03246038
Contributor : LAAS HAL-LAAS Connect in order to contact the contributor
Submitted on : Wednesday, June 2, 2021 - 10:50:38 AM
Last modification on : Monday, July 4, 2022 - 8:49:07 AM
Long-term archiving on: : Friday, September 3, 2021 - 6:44:19 PM

File

MAGRON Victor HDR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03246038, version 1

Citation

Victor Magron. The quest of modeling, certification and efficiency in polynomial optimization. Automatic Control Engineering. Université Toulouse 3 Paul Sabatier, 2021. ⟨tel-03246038⟩

Share

Metrics

Record views

49

Files downloads

2