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

María López Quijorna ()
Additional contact information
María López Quijorna: Universitat Konstanz

Journal of Global Optimization, 2021, vol. 81, issue 3, No 1, 559-598

Abstract: Abstract A basic closed semialgebraic subset of $${\mathbb {R}}^{n}$$ R n is defined by simultaneous polynomial inequalities $$p_{1}\ge 0,\ldots ,p_{m}\ge 0$$ p 1 ≥ 0 , … , p m ≥ 0 . 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 to be the optimal value of the polynomial optimization problem. This certificate is to check if a certain matrix has a generalized Hankel form. This certificate is more general than the already known certificate of an optimal solution being flat. In case we have detected optimality 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 enable us to prove, with the use of the GNS truncated construction, 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 . At the end, we provide a numerical linear algebraic algorithm for detecting optimality and extracting solutions of a polynomial optimization problem.

Keywords: Moment relaxation; Lassere relaxation; Polynomial optimization; Semidefinite programming; Quadrature; Truncated moment problem; GNS construction; Primary: 90C22; 90C26; Secondary: 44A60; 65D32 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00987-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:3:d:10.1007_s10898-020-00987-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00987-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().