Exposed Faces of Semidefinitely Representable Sets

Netzer, Tim; Plaumann, Daniel; Schweighofer, Markus

Exposed Faces of Semidefinitely Representable Sets

Dateien

Netzer_exposed.pdfGröße: 358.12 KBDownloads: 231

Datum

2010

Autor:innen

Netzer, Tim

Plaumann, Daniel

Schweighofer, Markus

Open Access-Veröffentlichung

Open Access Green

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

SIAM Journal on Optimization. 2010, 20(4), pp. 1944-1955. ISSN 1052-6234. Available under: doi: 10.1137/090750196

Zusammenfassung

A linear matrix inequality (LMI) is a condition stating that a symmetric matrix whose entries are affine-linear combinations of variables is positive semidefinite. Motivated by the fact that diagonal LMIs define polyhedra, the solution set of an LMI is called a spectrahedron. Linear images of spectrahedra are called semidefinitely representable sets. Part of the interest in spectrahedra and semidefinitely representable sets arises from the fact that one can efficiently optimize linear functions on them by semidefinite programming, such as one can do on polyhedra by linear programming. It is known that every face of a spectrahedron is exposed. This is also true in the general context of rigidly convex sets. We study the same question for semidefinitely representable sets. Lasserre proposed a moment matrix method to construct semidefinite representations for certain sets. Our main result is that this method can work only if all faces of the considered set are exposed. This necessary condition complements sufficient conditions recently proved by Lasserre, Helton, and Nie.

Fachgebiet (DDC)

510 Mathematik

Schlagwörter

convex set, semialgebraic set, linear matrix inequality, spectrahedron, semidefinite programming, Lasserre relaxation, sums of squares, quadrat

Zitieren

ISO 690

NETZER, Tim, Daniel PLAUMANN, Markus SCHWEIGHOFER, 2010. Exposed Faces of Semidefinitely Representable Sets. In: SIAM Journal on Optimization. 2010, 20(4), pp. 1944-1955. ISSN 1052-6234. Available under: doi: 10.1137/090750196

BibTex

@article{Netzer2010Expos-12347,
  year={2010},
  doi={10.1137/090750196},
  title={Exposed Faces of Semidefinitely Representable Sets},
  number={4},
  volume={20},
  issn={1052-6234},
  journal={SIAM Journal on Optimization},
  pages={1944--1955},
  author={Netzer, Tim and Plaumann, Daniel 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/12347">
    <dc:contributor>Netzer, Tim</dc:contributor>
    <dc:creator>Plaumann, Daniel</dc:creator>
    <dcterms:title>Exposed Faces of Semidefinitely Representable Sets</dcterms:title>
    <dc:contributor>Plaumann, Daniel</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:format>application/pdf</dc:format>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/12347/1/Netzer_exposed.pdf"/>
    <dc:language>eng</dc:language>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-25T15:19:32Z</dcterms:available>
    <dcterms:bibliographicCitation>SIAM journal on optimization ; 20 (2010), 4. - S. 1944-1955</dcterms:bibliographicCitation>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="eng">A linear matrix inequality (LMI) is a condition stating that a symmetric matrix whose entries are affine-linear combinations of variables is positive semidefinite. Motivated by the fact that diagonal LMIs define polyhedra, the solution set of an LMI is called a spectrahedron. Linear images of spectrahedra are called semidefinitely representable sets. Part of the interest in spectrahedra and semidefinitely representable sets arises from the fact that one can efficiently optimize linear functions on them by semidefinite programming, such as one can do on polyhedra by linear programming. It is known that every face of a spectrahedron is exposed. This is also true in the general context of rigidly convex sets. We study the same question for semidefinitely representable sets. Lasserre proposed a moment matrix method to construct semidefinite representations for certain sets. Our main result is that this method can work only if all faces of the considered set are exposed. This necessary condition complements sufficient conditions recently proved by Lasserre, Helton, and Nie.</dcterms:abstract>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Schweighofer, Markus</dc:contributor>
    <dcterms:issued>2010</dcterms:issued>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/12347"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/12347/1/Netzer_exposed.pdf"/>
    <dc:creator>Netzer, Tim</dc:creator>
    <dc:creator>Schweighofer, Markus</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-25T15:19:32Z</dc:date>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja