Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
研究了在紧致半代数集上最小化多项式的问题，证明了基于Schmüdgen型证书的层级以O(1/r^2)速率收敛到全局最小值，匹配了超球面和超立方体的已知结果。
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.