Type of Publication:  Journal article 
Author:  Schweighofer, Markus; Klep, Igor 
Year of publication:  2013 
Published in:  Mathematics of Operations Research ; 38 (2013), 3.  pp. 569590.  ISSN 0364765X.  eISSN 15265471 
DOI (citable link):  https://dx.doi.org/10.1287/moor.1120.0584 
Summary: 
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.

Subject (DDC):  510 Mathematics 
Keywords:  linear matrix inequality, LMI, spectrahedron, semidefinite programming, SDP, quadratic module, infeasibility, duality theory, real radical, Farkas' lemma 
Bibliography of Konstanz:  Yes 
Files  Size  Format  View 

There are no files associated with this item. 
SCHWEIGHOFER, Markus, Igor KLEP, 2013. An exact duality theory for semidefinite programming based on sums of squares. In: Mathematics of Operations Research. 38(3), pp. 569590. ISSN 0364765X. eISSN 15265471. Available under: doi: 10.1287/moor.1120.0584
@article{Schweighofer2013exact24805, title={An exact duality theory for semidefinite programming based on sums of squares}, year={2013}, doi={10.1287/moor.1120.0584}, number={3}, volume={38}, issn={0364765X}, journal={Mathematics of Operations Research}, pages={569590}, author={Schweighofer, Markus and Klep, Igor} }