On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2018
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
SIAM Journal on Optimization. 2018, 28(2), pp. 1796-1816. ISSN 1052-6234. eISSN 1095-7189. Available under: doi: 10.1137/17M1128290
Zusammenfassung

Consider a finite system of nonstrict real polynomial inequalities and suppose its solution set $S\subseteq\mathbb R^n$ is convex, has nonempty interior, and is compact. Suppose that the system satisfies the Archimedean condition, which is slightly stronger than the compactness of $S$. Suppose that each defining polynomial satisfies a second order strict quasiconcavity condition where it vanishes on $S$ (which is very natural because of the convexity of $S$) or its Hessian has a certain matrix sums of squares certificate for negative-semidefiniteness on $S$ (fulfilled trivially by linear polynomials). Then we show that the system possesses an exact Lasserre relaxation. In their seminal work of 2009, Helton and Nie showed under the same conditions that $S$ is the projection of a spectrahedron, i.e., it has a semidefinite representation. The semidefinite representation used by Helton and Nie arises from glueing together Lasserre relaxations of many small pieces obtained in a nonconstructive way. By refining and varying their approach, we show that we can simply take a Lasserre relaxation of the original system itself. Such a result was provided by Helton and Nie with much more machinery only under very technical conditions and after changing the description of $S$.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
510 Mathematik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690KRIEL, Tom-Lukas, Markus SCHWEIGHOFER, 2018. On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets. In: SIAM Journal on Optimization. 2018, 28(2), pp. 1796-1816. ISSN 1052-6234. eISSN 1095-7189. Available under: doi: 10.1137/17M1128290
BibTex
@article{Kriel2018Exact-38753.2,
  year={2018},
  doi={10.1137/17M1128290},
  title={On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets},
  number={2},
  volume={28},
  issn={1052-6234},
  journal={SIAM Journal on Optimization},
  pages={1796--1816},
  author={Kriel, Tom-Lukas 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/38753.2">
    <dcterms:abstract xml:lang="eng">Consider a finite system of nonstrict real polynomial inequalities and suppose its solution set $S\subseteq\mathbb R^n$ is convex, has nonempty interior, and is compact. Suppose that the system satisfies the Archimedean condition, which is slightly stronger than the compactness of $S$. Suppose that each defining polynomial satisfies a second order strict quasiconcavity condition where it vanishes on $S$ (which is very natural because of the convexity of $S$) or its Hessian has a certain matrix sums of squares certificate for negative-semidefiniteness on $S$ (fulfilled trivially by linear polynomials). Then we show that the system possesses an exact Lasserre relaxation. In their seminal work of 2009, Helton and Nie showed under the same conditions that $S$ is the projection of a spectrahedron, i.e., it has a semidefinite representation. The semidefinite representation used by Helton and Nie arises from glueing together Lasserre relaxations of many small pieces obtained in a nonconstructive way. By refining and varying their approach, we show that we can simply take a Lasserre relaxation of the original system itself. Such a result was provided by Helton and Nie with much more machinery only under very technical conditions and after changing the description of $S$.</dcterms:abstract>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-07-18T07:17:29Z</dc:date>
    <dc:creator>Kriel, Tom-Lukas</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Schweighofer, Markus</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:language>eng</dc:language>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-07-18T07:17:29Z</dcterms:available>
    <dc:contributor>Kriel, Tom-Lukas</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:issued>2018</dcterms:issued>
    <dcterms:title>On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets</dcterms:title>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/38753.2"/>
    <dc:contributor>Schweighofer, Markus</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Ja
Diese Publikation teilen

Versionsgeschichte

Gerade angezeigt 1 - 2 von 2
VersionDatumZusammenfassung
2*
2018-07-18 07:15:17
2017-05-05 13:33:43
* Ausgewählte Version