Optimization Online


An exact duality theory for semidefinite programming based on sums of squares

Igor Klep (igor.klep***at***auckland.ac.nz)
Markus Schweighofer (markus.schweighofer***at***uni-konstanz.de)

Abstract: 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 is infeasible if and only if -1 lies in the quadratic module associated to it. 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.

Keywords: linear matrix inequality, LMI, spectrahedron, semidefinite programming, SDP, quadratic module, infeasibility, duality theory, real radical, Farkas' lemma

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 08/29/2011
Entry Accepted: 08/29/2011
Entry Last Modified: 11/10/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society