An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares

• 成果类型: Article
• 署名作者: Klep, Igor; Schweighofer, Markus
• 署名单位: University of Auckland; University of Konstanz
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1120.0584
• 发表日期: 2013
• 页码: 569-590
• 关键词: positive polynomials; moment problem; optimization; relaxations; complexity; matrices

摘要

Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality A(x)>= 0 is infeasible if and only if -1 lies in the quadratic module associated to A. We also present a new exact duality theory for semidefinite programming, motivated by the real radical and sums of squares certificates from real algebraic geometry.