Article ID: | iaor20135231 |
Volume: | 38 |
Issue: | 3 |
Start Page Number: | 569 |
End Page Number: | 590 |
Publication Date: | Aug 2013 |
Journal: | Mathematics of Operations Research |
Authors: | Klep Igor, Schweighofer Markus |
Keywords: | duality, programming (semidefinite) |
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