Tight relaxations for polynomial optimization and Lagrange multiplier expressionsy

• 成果类型: Article
• 署名作者: Nie, Jiawang
• 署名单位: University of California System; University of California San Diego
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1276-2
• 发表日期: 2019
• 页码: 1-37
• 关键词: global optimization; positive polynomials; rational functions; hierarchy; sums; squares; REPRESENTATIONS; CONVERGENCE; bounds; sets

摘要

This paper proposes tight semidefinite relaxations for polynomial optimization. The optimality conditions are investigated. We show that generally Lagrange multipliers can be expressed as polynomial functions in decision variables over the set of critical points. The polynomial expressions are determined by linear equations. Based on these expressions, new Lasserre type semidefinite relaxations are constructed for solving the polynomial optimization. We show that the hierarchy of new relaxations has finite convergence, or equivalently, the new relaxations are tight for a finite relaxation order.