Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures

2024/04/15 by Lucas Slot, Slot, Lucas, Manuel Wiedmer +1
Computer Science · Mathematics · #90C22 #90C23 #90C26 #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2404.09710

openalex publication_date 2024/04/15 · openalex created_date 2024/04/18 · openalex updated_date 2026/08/03

Abstract

Let X ⊆ ℝⁿ be a closed set, and consider the problem of computing the minimum f_min of a polynomial f on X. Given a measure μ supported on X, Lasserre (SIAM J. Optim. 21(3), 2011) proposes a decreasing sequence of upper bounds on f_min, each of which may be computed by solving a semidefinite program. When X is compact, these bounds converge to f_min under minor assumptions on μ. Later, Lasserre (Math. Program. 190, 2020) introduces a related, but far more economical sequence of upper bounds which rely on the push-forward measure of μ by f. While these new bounds are weaker a priori, they actually achieve similar asymptotic convergence rates on compact sets. In this work, we show that no such free lunch exists in the non-compact setting. While convergence of the standard bounds to f_min is guaranteed when X = ℝⁿ and μ is a Gaussian distribution, we prove that the bounds relying on the push-forward measure fail to converge to f_min in that setting already for polynomials of degree 6.

Related

• Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization
• An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization
• Bound-constrained polynomial optimization using only elementary calculations
• Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
• Sum-of-squares relaxations for polynomial min-max problems over simple sets