Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel

2021/11/08 by Lucas Slot, Slot, Lucas · 4 citations
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Polynomial and algebraic computation #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2111.04610

Abstract

Consider the problem of minimizing a polynomial f over a compact semialgebraic set X ⊆ ℝⁿ. Lasserre introduces hierarchies of semidefinite programs to approximate this hard optimization problem, based on classical sum-of-squares certificates of positivity of polynomials due to Putinar and Schmüdgen. When X is the unit ball or the standard simplex, we show that the hierarchies based on the Schmüdgen-type certificates converge to the global minimum of f at a rate in O(1/r²), matching recently obtained convergence rates for the hypersphere and hypercube [-1,1]ⁿ. For our proof, we establish a connection between Lasserre's hierarchies and the Christoffel-Darboux kernel, and make use of closed form expressions for this kernel derived by Xu.

Cited by

• Solving Stengle's Example in Rational Arithmetic: Exact Values of the Moment-SOS Relaxations
• Finite Convergence of the Moment-SOS Hierarchy on the Product of Spheres
• On the convergence rates of moment-SOS hierarchies approximation of truncated moment sequences
• Convergence rates for polynomial optimization on set products

Related

• Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
• An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization
• Sum-of-squares hierarchies for binary polynomial optimization
• Leveraging Christoffel-Darboux Kernels to Strengthen Moment-SOS Relaxations
• Convergence rates for sums-of-squares hierarchies with correlative sparsity