Making Non-Negative Polynomials into Sums of Squares

Abstract

We study linear operators $T:\mathbb{R}[x_1,\dots ,x_n]\to \mathbb{R}[x_1,\dots ,x_n]$, especially for the purpose to move sets $S\subseteq \mathbb{R}[x_1,\dots ,x_n]$ into cones $C\subseteq \mathbb{R}[x_1,\dots ,x_n]$: $TS\subseteq C$. We develop the theory of (semi-)groups of operators $(e^{tA}{)}_{t\in \mathbb{R}}$ on $\mathbb{R}[x_1,\dots ,x_n]$, which requires techniques from regular Fréchet Lie groups. We study the special case of making non-negative polynomials $\mathrm{Pos}(K{)}_{\le 2d}$ with $K\subseteq {\mathbb{R}}^n$ and $\mathrm{int}K\ne \varnothing$ into sums of squares: $\tilde{T}\mathrm{Pos}(K{)}_{\le 2d}\subseteq \sum \mathbb{R}[x_1,\dots ,x_n{]}_{\le d}^2$. With $N:=\dim \mathbb{R}[x_1,\dots ,x_n{]}_{\le 2d}=(\genfrac{}{}{0ex}{}{n+2d}{n})$, for $\tilde{T}$, a memory of at most $2N+1$ is required. Matrix multiplications $\tilde{T}M$, $M\tilde{T}$, ${\tilde{T}}^{-1}M$, and $M{\tilde{T}}^{-1}$ of $\tilde{T}$ with any $M\in {\mathbb{R}}^{N\times N}$ require at most $4N^2+1$ operations. Transformations $\tilde{T}v$ and ${\tilde{T}}^{-1}v$ of vectors $v\in {\mathbb{R}}^N$ require at most $4N+1$ operations. Calculating ${\tilde{T}}^{-1}$ of $\tilde{T}$ requires only one (!) operation.