View abstract

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).

View abstract PDF