Sum-of-Squares hierachies for polynomial optimization and the Christoffel-Darboux kernel
SIAM Journal on Optimization , Volume 32 - Issue 4 p. 2612- 2635
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|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Slot, L.F.H. (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