Session II.3 - Real-Number Complexity
Friday, June 16, 16:30 ~ 17:00
Complexity in Polynomial Optimization: Asymptotic Convergence, Flat Trucation and Semidefinite Programming
Lorenzo Baldi
Sorbonne University, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
In polynomial optimization, the Lasserre-Parrilo hierarchies are used to compute lower approximations of the global minimum of a polynomial objective funciton f over a basic closed semialgebraic set S. In this talk, we investigate three aspects of the complexity of such problems:
- we present asymptotic convergence rates for the lower approximations of the global minimum, using Lojasiewicz inequalities associated to f and to the description of S;
- we characterize flat truncation, that is used to certify finite convergence, and we describe the relationship with the interpolation degree and the support of finitely generated quadratic modules;
- we propose open research directions connecting polynomial optimization with the complexity of semidefinite programming problems.
Joint work with Bernard Mourrain (INRIA d'Universite Cote d'Azur) and Adam Parusinski (Universite Cote d'Azur).