Optimality conditions and finite convergence of Lasserre's hierarchy

• 成果类型: Article
• 署名作者: Nie, Jiawang
• 署名单位: University of California System; University of California San Diego
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0680-x
• 发表日期: 2014
• 页码: 97-121
• 关键词: global optimization; degree bounds; POLYNOMIALS; REPRESENTATIONS; squares; sums

摘要

Lasserre's hierarchy is a sequence of semidefinite relaxations for solving polynomial optimization problems globally. This paper studies the relationship between optimality conditions in nonlinear programming theory and finite convergence of Lasserre's hierarchy. Our main results are: (i) Lasserre's hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean condition; the proof uses a result of Marshall on boundary hessian conditions. (ii) These optimality conditions are all satisfied at every local minimizer if a finite set of polynomials, which are in the coefficients of input polynomials, do not vanish at the input data (i.e., they hold in a Zariski open set). This implies that, under archimedeanness, Lasserre's hierarchy has finite convergence generically.