Certifying convergence of Lasserre's hierarchy via flat truncation

• 成果类型: Article
• 署名作者: Nie, Jiawang
• 署名单位: University of California System; University of California San Diego
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0589-9
• 发表日期: 2013
• 页码: 485-510
• 关键词: Optimization; POLYNOMIALS; squares

摘要

Consider the optimization problem of minimizing a polynomial function subject to polynomial constraints. Atypical approach for solving it globally is applying Lasserre's hierarchy of semidefinite relaxations, based on either Putinar's or Schmudgen'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 Schmudgen 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 Schmudgen 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.