The Effective Lasserre's Perturbative Positivstellensatz

Abstract

We study sum-of-squares (SOS) certificates for nonnegative polynomials $p$ on ${\mathbb{R}}^d$ and their implications for polynomial optimization over unbounded domains. Building on Lasserre's perturbation approach, we consider SOS representations of $p$ augmented by weighted polynomial tails of the form ${\sum }_{n=0}^N(x\cdot x{)}^n/(n!{)}^t$ for $0<t<1$. Our main result provides an explicit quantitative bound on the truncation order $N$ required to achieve an $\epsilon$-accurate certificate. Using positivity properties of the Mehler kernel and techniques inspired by polynomial kernel methods, we show that $N$ grows polynomially in $1/\epsilon$, with rate $N=O((\Vert p\Vert /\epsilon {)}^{1/(1-t)})$.

arXiv comment32 pages