Infeasibility certificates for linear matrix inequalities

Cite This

Files in this item

Checksum: MD5:d5b9cfd7950e3e2824bb870c8e77a47a

KLEP, Igor, Markus SCHWEIGHOFER, 2011. Infeasibility certificates for linear matrix inequalities

@techreport{Klep2011Infea-15287, series={Konstanzer Schriften in Mathematik}, title={Infeasibility certificates for linear matrix inequalities}, year={2011}, number={282}, author={Klep, Igor and Schweighofer, Markus} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:language>eng</dc:language> <dcterms:hasPart rdf:resource=""/> <dc:contributor>Klep, Igor</dc:contributor> <dcterms:title>Infeasibility certificates for linear matrix inequalities</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:rights>terms-of-use</dc:rights> <dc:creator>Schweighofer, Markus</dc:creator> <dc:date rdf:datatype="">2011-09-01T10:07:50Z</dc:date> <dspace:hasBitstream rdf:resource=""/> <dcterms:available rdf:datatype="">2011-09-01T10:07:50Z</dcterms:available> <dspace:isPartOfCollection rdf:resource=""/> <dc:contributor>Schweighofer, Markus</dc:contributor> <dcterms:rights rdf:resource=""/> <dcterms:isPartOf rdf:resource=""/> <dc:creator>Klep, Igor</dc:creator> <dcterms:issued>2011</dcterms:issued> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:abstract xml:lang="eng">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. More precisely, we show that a linear matrix inequality is infeasible if and only if -1 lies in the quadratic module associated to it. We prove exponential degree bounds for the corresponding algebraic certificate. In order to get a polynomial size certificate, 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.</dcterms:abstract> <bibo:uri rdf:resource=""/> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

282Klep_infeasible.pdf 140

This item appears in the following Collection(s)

Search KOPS


My Account