Certifying Convergence of Lasserre's Hierarchy via Flat Truncation
arXiv:1106.2384
Abstract
This paper studies how to certify the convergence of Lasserre's hierarchy of semidefinite programming relaxations for solving multivariate polynomial optimization. We propose flat truncation as a general certificate for this purpose. Assume the set of global minimizers is nonempty and finite. Our main results are: i) Putinar type Lasserre's hierarchy has finite convergence if and only if flat truncation holds, under some general assumptions, and this is also true for the Schmudgen type one; ii) under the archimedean condition, flat truncation is asymptotically satisfied for Putinar type Lasserre's hierarchy, and similar is true for the Schmudgen type one; iii) for the hierarchy of Jacobian SDP relaxations, flat truncation is always satisfied. The case of unconstrained polynomial optimization is also discussed.
18 pages