Publikation: Infeasibility certificates for linear matrix inequalities
Lade...
Dateien
Datum
2011
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Working Paper/Technical Report
Publikationsstatus
Published
Erschienen in
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
510 Mathematik
Schlagwörter
linear matrix inequality, LMI, spectrahedron, semide nite program, quadratic module, infeasibility, duality, complete positivity, Farkas' lemma.
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
KLEP, Igor, Markus SCHWEIGHOFER, 2011. Infeasibility certificates for linear matrix inequalitiesBibTex
@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>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
