Certifying convergence of Lasserre’s hierarchy via flat truncation |
| |
Authors: | Jiawang Nie |
| |
Institution: | 1. Department of Mathematics, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA, 92093, USA
|
| |
Abstract: | Consider the optimization problem of minimizing a polynomial function subject to polynomial constraints. A typical approach for solving it globally is applying Lasserre’s hierarchy of semidefinite relaxations, based on either Putinar’s or Schmüdgen’s Positivstellensatz. A practical question in applications is: how to certify its convergence and get minimizers? In this paper, we propose flat truncation as a certificate for this purpose. Assume the set of global minimizers is nonempty and finite. Our main results are: (1) Putinar type Lasserre’s hierarchy has finite convergence if and only if flat truncation holds, under some generic assumptions; the same conclusion holds for the Schmüdgen type one under weaker assumptions. (2) Flat truncation is asymptotically satisfied for Putinar type Lasserre’s hierarchy if the archimedean condition holds; the same conclusion holds for the Schmüdgen type one if the feasible set is compact. (3) We show that flat truncation can be used as a certificate to check exactness of standard SOS relaxations and Jacobian SDP relaxations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|