Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction

DOI10.1007/S10898-020-00987-9zbMATH Open1484.90070arXiv1704.02034OpenAlexW3135959098MaRDI QIDQ2052380FDOQ2052380

Authors: María López Quijorna 

Publication date: 26 November 2021

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: A basic closed semialgebraic subset of $mathbb{R}^n$ is defined by simultaneous polynomial inequalities $p_{1}geq0,ldots,p_{m}geq0$. We consider Lasserre's relaxation hierarchy to solve the problem of minimizing a polynomial over such a set. These relaxations give an increasing sequence of lower bounds of the infimum. In this paper we provide a new certificate for the optimal value of a Lasserre relaxation 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 we have optimality we will extract the potencial 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 reprove 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 existance of a Gaussian quadrature rule if the modified optimal solution is generalized Hankel matrix. At the end, we provide a numerical linear algebraic algorithm for dectecting optimality and extracting solutions of a polynomial optimization problem.

Full work available at URL: https://arxiv.org/abs/1704.02034

Recommendations

• Certifying convergence of Lasserre's hierarchy via flat truncation
• Convergence of Lasserre's hierarchy: the general case
• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• Optimization of Polynomials on Compact Semialgebraic Sets
• On the exactness of Lasserre relaxations and pure states over real closed fields

zbMATH Keywords

polynomial optimizationsemidefinite programmingquadraturetruncated moment problemGNS constructionmoment relaxationLassere relaxation

Mathematics Subject Classification ID

Numerical quadrature and cubature formulas (65D32) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22) Moment problems (44A60) Polynomial optimization (90C23)

Cites Work

• Ideals, Varieties, and Algorithms
• General tensor decomposition, moment matrices and applications
• Global optimization with polynomials and the problem of moments
• GloptiPoly
• Orthogonal polynomials of several variables
• A collection of test problems for constrained global optimization algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization of Polynomials on Compact Semialgebraic Sets
• The proof of Tchakaloff’s Theorem
• \(C^*\)-algebras by example
• Kubaturformeln mit minimaler Knotenzahl
• A dilation theory approach to cubature formulas
• Title not available (Why is that?)
• Solution of the truncated complex moment problem for flat data
• The truncated complex $K$-moment problem
• Revisiting two theorems of Curto and Fialkow on moment matrices
• Symmetric tensor decomposition
• An exact duality theory for semidefinite programming based on sums of squares
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with application to semidefinite programming
• The moment problem
• Optimization approaches to quadrature: new characterizations of Gaussian quadrature on the line and quadrature with few nodes on plane algebraic curves, on the plane and in higher dimensions

Cited In (4)

• Lasserre hierarchy for large scale polynomial optimization in real and complex variables
• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• Certifying convergence of Lasserre's hierarchy via flat truncation
• Quadrature-based polynomial optimization

Uses Software

• SeDuMi
• GloptiPoly

This page was built for publication: Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052380)