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.

, , , ,
SIAM Journal on Optimization
Mixed-Integer Nonlinear Optimization
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Slot, L. (2022). Sum-of-Squares hierachies for polynomial optimization and the Christoffel-Darboux kernel. SIAM Journal on Optimization, 32(4), 2612–2635. doi:10.1137/21M1458338