On the exactness of Lasserre relaxations and pure states over real closed fields

Abstract

Consider a finite system of non-strict polynomial inequalities with solution set $S\subseteq {\mathbb{R}}^n$. Its Lasserre relaxation of degree $d$ is a certain natural linear matrix inequality in the original variables and one additional variable for each nonlinear monomial of degree at most $d$. It defines a spectrahedron that projects down to a convex semialgebraic set containing $S$. In the best case, the projection equals the convex hull of $S$. We show that this is very often the case for sufficiently high $d$ if $S$ is compact and "bulges outwards" on the boundary of its convex hull. Now let additionally a polynomial objective function $f$ be given, i.e., consider a polynomial optimization problem. Its Lasserre relaxation of degree $d$ is now a semidefinite program. In the best case, the optimal values of the polynomial optimization problem and its relaxation agree. We prove that this often happens if $S$ is compact and $d$ exceeds some bound that depends on the description of $S$ and certain characteristicae of $f$ like the mutual distance of its global minimizers on $S$.

36 pages, to appear in Foundations of Computational Mathematics