Dissertation:
Detecting optimality and extracting optimal solutions in polynomial optimization based on the Lasserre relaxation

No Thumbnail Available
Date
2018
relationships.isEditorOf
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
Project
EU project number
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Dissertation
Publication status
Published
Abstract
We consider Lasserre’s relaxation hierarchy to solve the problem of minimizing a polynomial over a basic closed semialgebraic set, that is a polynomial optimization problem. These relaxations give an increasing sequence of lower bounds of the infimum. In this work we provide a new certificate for the optimal value of a Lasserre relaxation to be the optimal value of the polynomial optimization problem. This certificate is that a modified version of an optimal solution of the Lasserre relaxation is a generalized Hankel matrix. This certificate is more general than the already known certificate of an optimal solution being flat. In case that this modified matrix has a generalized Hankel form we will extract the potential minimizers with a truncated version of the Gelfand-Naimark-Segal construction on the optimal solution of the Lasserre relaxation. We prove also that the operators of this truncated construction commute if and only if the matrix of this modified optimal solution is a generalized Hankel matrix. This generalization of flatness will bring us to prove a result of Curto and Fialkow on the existence of quadrature rule if the optimal solution is flat and a result of Xu and Mysovskikh on the existence of a Gaussian quadrature rule if the modified optimal solution is a generalized Hankel matrix. We give a numerical linear algebraic algorithm for detecting optimality and extracting solutions of a polynomial optimization problem. Finally, we provide an experimental algorithm that in many cases gives us an upper bound of the global infimum of a real polynomial on R n . The algorithm that we present involves to solve a series of semidefinite programs whose feasible set is included in the feasible set of a moment relaxation. Our additional constraint try to provoke a flatness condition, like used by Curto and Fialkow, for the computed moments. At the end we present numerical results of the application of the algorithm to nonnegative polynomials which are not sums of squares. We also provide numerical results for the application of a version of this algorithm based on the method proposed by Nie, Demmel and Sturmfels.
Summary in another language
Subject (DDC)
510 Mathematics
Keywords
Polynomial optimization, truncated moment problem
Published in
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690LOPEZ QUIJORNA, Maria, 2018. Detecting optimality and extracting optimal solutions in polynomial optimization based on the Lasserre relaxation [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{LopezQuijorna2018Detec-42505,
  year={2018},
  title={Detecting optimality and extracting optimal solutions in polynomial optimization based on the Lasserre relaxation},
  author={Lopez Quijorna, Maria},
  address={Konstanz},
  school={Universität Konstanz}
}
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/42505">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:contributor>Lopez Quijorna, Maria</dc:contributor>
    <dc:creator>Lopez Quijorna, Maria</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/42505/3/LopezQuijorna_2-1x895ec44tgst0.pdf"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-06-07T08:34:39Z</dcterms:available>
    <dc:language>eng</dc:language>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/42505"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-06-07T08:34:39Z</dc:date>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:title>Detecting optimality and extracting optimal solutions in polynomial optimization based on the Lasserre relaxation</dcterms:title>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/42505/3/LopezQuijorna_2-1x895ec44tgst0.pdf"/>
    <dcterms:abstract xml:lang="eng">We consider Lasserre’s relaxation hierarchy to solve the problem of minimizing a polynomial over a basic closed semialgebraic set, that is a polynomial optimization problem. These relaxations give an increasing sequence of lower bounds of the infimum. In this work we provide a new certificate for the optimal value of a Lasserre relaxation to be the optimal value of the polynomial optimization problem. This certificate is that a modified version of an optimal solution of the Lasserre relaxation is a generalized Hankel matrix. This certificate is more general than the already known certificate of an optimal solution being flat. In case that this modified matrix has a generalized Hankel form we will extract the potential minimizers with a truncated version of the Gelfand-Naimark-Segal construction on the optimal solution of the Lasserre relaxation. We prove also that the operators of this truncated construction commute if and only if the matrix of this modified optimal solution is a generalized Hankel matrix. This generalization of flatness will bring us to prove a result of Curto and Fialkow on the existence of quadrature rule if the optimal solution is flat and a result of Xu and Mysovskikh on the existence of a Gaussian quadrature rule if the modified optimal solution is a generalized Hankel matrix. We give a numerical linear algebraic algorithm for detecting optimality and extracting solutions of a polynomial optimization problem. Finally, we provide an experimental algorithm that in many cases gives us an upper bound of the global infimum of a real polynomial on R n . The algorithm that we present involves to solve a series of semidefinite programs whose feasible set is included in the feasible set of a moment relaxation. Our additional constraint try to provoke a flatness condition, like used by Curto and Fialkow, for the computed moments. At the end we present numerical results of the application of the algorithm to nonnegative polynomials which are not sums of squares. We also provide numerical results for the application of a version of this algorithm based on the method proposed by Nie, Demmel and Sturmfels.</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:issued>2018</dcterms:issued>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
Test date of URL
Examination date of dissertation
February 8, 2018
University note
Konstanz, Univ., Doctoral dissertation, 2018
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes
Refereed
Link to research data
Description of supplementary data