Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube

DOI10.1287/moor.2018.0983zbMath1442.90141arXiv1804.05524OpenAlexW2964069080WikidataQ126865380 ScholiaQ126865380MaRDI QIDQ5108258

Etienne de Klerk, Monique Laurent

Publication date: 30 April 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

Jacobi polynomialssemidefinite optimizationprogrammingpolynomial optimizationLasserre hierarchyextremal roots of orthogonal polynomialsnonlinear (theory)

Mathematics Subject Classification ID

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

Related Items

Algebraic Perspectives on Signomial Optimization, Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel, Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere, Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets, Distributionally robust optimization with polynomial densities: theory, models and algorithms, Sum of Squares Bounds for the Empty Integral Hull Problem, Quadrature-based polynomial optimization, Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022, An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials, An effective version of Schmüdgen's Positivstellensatz for the hypercube, The impact of noise on evaluation complexity: the deterministic trust-region case, Connecting optimization with spectral analysis of tri-diagonal matrices, Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures, Sum-of-squares hierarchies for binary polynomial optimization, Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization, Sum-of-squares hierarchies for binary polynomial optimization, Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives

Cites Work

• Unnamed Item
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• Sharp bounds for the extreme zeros of classical orthogonal polynomials
• A note on total degree polynomial optimization by Chebyshev grids
• Bounds for extreme zeros of some classical orthogonal polynomials
• Interlacing eigenvalues and graphs
• Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies
• Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization
• Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube
• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• Toeplitz and Circulant Matrices: A Review
• Bound on the Extreme Zeros of Orthogonal Polynomials
• Comparison of Lasserre’s Measure-Based Bounds for Polynomial Optimization to Bounds Obtained by Simulated Annealing
• Bound-Constrained Polynomial Optimization Using Only Elementary Calculations