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

Publikationstyp: Zeitschriftenartikel
Autor/innen: Schweighofer, Markus; Klep, Igor
Erscheinungsjahr: 2013
Erschienen in: Mathematics of Operations Research ; 38 (2013), 3. - S. 569-590. - ISSN 0364-765X. - eISSN 1526-5471
DOI (zitierfähiger Link): https://dx.doi.org/10.1287/moor.1120.0584
Zusammenfassung:
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.
Fachgebiet (DDC): 510 Mathematik
Schlagwörter: linear matrix inequality, LMI, spectrahedron, semidefinite programming, SDP, quadratic module, infeasibility, duality theory, real radical, Farkas' lemma
Universitätsbibliographie: Ja

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

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. 569-590. ISSN 0364-765X. eISSN 1526-5471. Available under: doi: 10.1287/moor.1120.0584

@article{Schweighofer2013exact-24805, 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={0364-765X}, journal={Mathematics of Operations Research}, pages={569--590}, author={Schweighofer, Markus and Klep, Igor} }

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. Schweighofer, Markus An exact duality theory for semidefinite programming based on sums of squares 2013 eng Mathematics of Operations Research ; 38 (2013), 3. - S. 569-590 2013-10-11T14:29:51Z terms-of-use Klep, Igor Klep, Igor 2013-10-11T14:29:51Z Schweighofer, Markus

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto