Infeasibility certificates for linear matrix inequalities

Klep, Igor; Schweighofer, Markus

Infeasibility certificates for linear matrix inequalities

Dateien

282Klep_infeasible.pdfGröße: 883.65 KBDownloads: 116

Datum

2011

URI (zitierfähiger Link)

http://nbn-resolving.de/urn:nbn:de:bsz:352-152877

Open Access-Veröffentlichung

Open Access Green

Publikationstyp

Working Paper/Technical Report

Publikationsstatus

Published

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. 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.

Fachgebiet (DDC)

510 Mathematik

Schlagwörter

linear matrix inequality, LMI, spectrahedron, semide nite program, quadratic module, infeasibility, duality, complete positivity, Farkas' lemma.

Zitieren

ISO 690

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

BibTex

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

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/15287">
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/15287/2/282Klep_infeasible.pdf"/>
    <dcterms:title>Infeasibility certificates for linear matrix inequalities</dcterms:title>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-09-01T10:07:50Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Klep, Igor</dc:creator>
    <dc:contributor>Klep, Igor</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:creator>Schweighofer, Markus</dc:creator>
    <dc:language>eng</dc:language>
    <dc:contributor>Schweighofer, Markus</dc:contributor>
    <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>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/15287/2/282Klep_infeasible.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/15287"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-09-01T10:07:50Z</dc:date>
    <dcterms:issued>2011</dcterms:issued>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja