Please use this identifier to cite or link to this item:
Files in This Item:
File SizeFormat 
OWP2011_28.pdf491.44 kBAdobe PDFView/Open
Title: Infeasibility certificates for linear matrix inequalities
Authors: Klep, IgorSchweighofer, Markus
Publishers Version:
Issue Date: 2011
Published in: Oberwolfach Preprints (OWP), Volume 2011-28, ISSN 1864-7596
Publisher: Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
Abstract: Farkas' lemma is a fundamental result from linear programming providing linear certi cates 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. More precisely, we show that a linear matrix inequality L(x)⪰0 is infeasible if and only if −1 lies in the quadratic module associated to L. We prove exponential degree bounds for the corresponding algebraic certificate. In order to get a polynomial size certi cate, we use a more involved algebraic certificate motivated by the real radical and Prestel's theory of semiorderings. Completely different methods, namely complete positivity from operator algebras, are employed to consider linear matrix inequality domination.
Keywords: Linear matrix inequality; LMI; spectrahedron; semidenite program; quadratic module; infeasibility; duality; complete positivity; Farkas' lemma
DDC: 510
License: This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties.
Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
Appears in Collections:Mathematik

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.