Zur Kurzanzeige

dc.contributor.authorKlep, Igor
dc.contributor.authorSchweighofer, Markus
dc.date.accessioned2011-03-20T12:01:20Z
dc.date.accessioned2016-10-05T14:14:21Z
dc.date.available2011-03-20T12:01:20Z
dc.date.available2016-10-05T14:14:21Z
dc.date.issued2011-05-25
dc.identifier.urihttp://publications.mfo.de/handle/mfo/1198
dc.descriptionResearch in Pairs 2010en_US
dc.description.abstractFarkas' 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) \succeq 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.en_US
dc.language.isoenen_US
dc.publisherMathematisches Forschungsinstitut Oberwolfachen_US
dc.relation.ispartofseriesOberwolfach Preprints;2011,28
dc.subjectlinear matrix inequality LMI spectrahedron semidefinite program quadratic module infeasibility duality complete positivity Farkas' lemmaen_US
dc.titleInfeasibility certificates for linear matrix inequalitiesen_US
dc.typePreprinten_US
dc.rights.licenseDieses 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.de
dc.rights.licenseThis 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.en
dc.identifier.doi10.14760/OWP-2011-28
local.scientificprogramResearch in Pairs 2010
local.series.idOWP-2011-28
local.subject.msc13
local.subject.msc15
local.subject.msc46
local.subject.msc90
local.subject.msc14
dc.identifier.urnurn:nbn:de:101:1-201109305109
dc.identifier.ppn1651043477


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige