Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization

DOI10.1137/16M1065264zbMATH Open1357.90177arXiv1603.03329OpenAlexW2296530532MaRDI QIDQ2968176FDOQ2968176

Monique Laurent, E. de Klerk, Roxana Heß

Publication date: 10 March 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1{]}^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1{]}^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $in{t}_{[-1,1{]}^n}f(x)h(x)dmu(x)$, where $dmu(x)$ is a fixed, finite Borel measure supported on $[-1,1{]}^n$. It is known that, for the Lebesgue measure $dmu(x)=dx$, one may show an error bound $O(1/sqrtr)$ if $h$ is a sum-of-squares density, and an $O(1/r)$ error bound if $h$ is the density of a beta distribution. In this paper, we show an error bound of $O(1/r^2)$, if $dmu(x)=left(pro{d}_{i=1}^{n}sqrt1-x_i^{2}ight{)}^{-1}dx$ (the well-known measure in the study of orthogonal polynomials), and $h$ has a Schm"udgen-type representation with respect to $[-1,1{]}^n$, which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels, and in particular on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities.

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

zbMATH Keywords

polynomial optimizationsemidefinite programminggeneralized eigenvalue problemJackson kernelsum-of-squares polynomialbox-constrained global optimization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60) Derivative-free methods and methods using generalized derivatives (90C56)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Global optimization with polynomials and the problem of moments
• The \(K\)-moment problem for compact semi-algebraic sets
• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• Polynomials that are positive on an interval
• A New Active Set Algorithm for Box Constrained Optimization
• A Feasible Active Set Method for Strictly Convex Quadratic Problems with Simple Bounds
• The kernel polynomial method
• Rank of Handelman hierarchy for Max-Cut
• Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

Cited In (14)

• Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures
• Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
• Comparison of Lasserre’s Measure-Based Bounds for Polynomial Optimization to Bounds Obtained by Simulated Annealing
• Connecting optimization with spectral analysis of tri-diagonal matrices
• Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming
• Algebraic Perspectives on Signomial Optimization
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• An effective version of Schmüdgen's Positivstellensatz for the hypercube
• Quadrature-based polynomial optimization
• A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
• Convergence rates of moment-sum-of-squares hierarchies for optimal control problems
• (Global) optimization: historical notes and recent developments
• A boosted-DCA with power-sum-DC decomposition for linearly constrained polynomial programs
• Tight relaxations for polynomial optimization and Lagrange multiplier expressions

This page was built for publication: Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization

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