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

DOI10.1137/16M1065264zbMath1357.90177arXiv1603.03329OpenAlexW2296530532MaRDI QIDQ2968176

Etienne de Klerk, Roxana Hess, Monique Laurent

Publication date: 10 March 2017

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

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

zbMATH Keywords

semidefinite programminggeneralized eigenvalue problempolynomial optimizationJackson kernelsum-of-squares polynomialbox-constrained global optimization

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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