Publikation:

Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares

Lade...
Vorschaubild

Dateien

tentacle.pdf
tentacle.pdfGröße: 1.57 MBDownloads: 442

Datum

2006

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

SIAM Journal on Optimization. 2006, 17(3), pp. 920-942. ISSN 1052-6234. Available under: doi: 10.1137/050647098

Zusammenfassung

In this work, the combine the theory of generalized critical values with the theory of iterated rings of bounded elements (real holomorphy rings). We consider the problem of computing the global infimum of a real polynomial in several variables. Every global minimizer lies on the gradient variety. If the polynomial attains minimum, it is therefore equivalent to look for the greatest lower bound on its gradient variety. Nie, Demmel and Sturmfels proved recently a theorem about the existence of sums of squares certificates for such lower bounds. Based on these certificates, they find arbitrarily tight relaxations of the original problem that can be formulated as semidefinite programs and thus be solved efficiently. We deal here with the more general case when the polynomial is bounded from below but does not necessarily attain a minimum. In this case, the method of Nie, Demmel and Sturmfels might yield completely wrong results. In order to overcome this problem, we replace the gradient variety by larger semialgebraic sets which we call gradient tentacles. It now gets substantially harder to prove the existence of the necessary sums of squares certificates.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
510 Mathematik

Schlagwörter

global optimization, polynomial, preorder, sum of squares, semidefinite programming

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690SCHWEIGHOFER, Markus, 2006. Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares. In: SIAM Journal on Optimization. 2006, 17(3), pp. 920-942. ISSN 1052-6234. Available under: doi: 10.1137/050647098
BibTex
@article{Schweighofer2006Globa-15644,
  year={2006},
  doi={10.1137/050647098},
  title={Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares},
  number={3},
  volume={17},
  issn={1052-6234},
  journal={SIAM Journal on Optimization},
  pages={920--942},
  author={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/15644">
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-10-31T09:57:00Z</dcterms:available>
    <dcterms:issued>2006</dcterms:issued>
    <dcterms:title>Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares</dcterms:title>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-10-31T09:57:00Z</dc:date>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/15644/2/tentacle.pdf"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Schweighofer, Markus</dc:contributor>
    <dcterms:bibliographicCitation>SIAM Journal of Optimization 17 (2006), 3. - S. 920-942</dcterms:bibliographicCitation>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="eng">In this work, the combine the theory of generalized critical values with the theory of iterated rings of bounded elements (real holomorphy rings). We consider the problem of computing the global infimum of a real polynomial in several variables. Every global minimizer lies on the gradient variety. If the polynomial attains minimum, it is therefore equivalent to look for the greatest lower bound on its gradient variety. Nie, Demmel and Sturmfels proved recently a theorem about the existence of sums of squares certificates for such lower bounds. Based on these certificates, they find arbitrarily tight relaxations of the original problem that can be formulated as semidefinite programs and thus be solved efficiently. We deal here with the more general case when the polynomial is bounded from below but does not necessarily attain a minimum. In this case, the method of Nie, Demmel and Sturmfels might yield completely wrong results. In order to overcome this problem, we replace the gradient variety by larger semialgebraic sets which we call gradient tentacles. It now gets substantially harder to prove the existence of the necessary sums of squares certificates.</dcterms:abstract>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/15644"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/15644/2/tentacle.pdf"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:creator>Schweighofer, Markus</dc:creator>
  </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
Diese Publikation teilen