Sum-of-Squares hierachies for polynomial optimization and the Christoffel-Darboux kernel

Consider the problem of minimizing a polynomial f over a compact semialgebraic set X \subseteq \BbbR 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\" udgen. When X is the unit ball or the standard simplex, we show that the hierarchies based on the Schm\" udgen-type certificates converge to the global minimum of f at a rate in O(1/r2), 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.

• View at Publisher