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

Abstract

Consider the problem of minimizing a polynomial $f$ over a compact semialgebraic set $\mathbf{X}\subseteq {\mathbb{R}}^n$. 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 $\mathbf{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^2)$, matching recently obtained convergence rates for the hypersphere and hypercube $[-1,1{]}^n$. 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.

arXiv commentv3: Fixed a technical error in the (proof of) Lemma 18. This has a (minor) impact on the constants appearing in Theorems 3, 4