Polynomial SOS

A sum of squares polynomial is a real polynomial expressible as $p={\sum }_i{q}_i^2$ for real polynomials $q_i$. In the homogeneous degree-$2m$ case the summands may be taken homogeneous of degree $m$. Every such polynomial is nonnegative on real inputs; the converse fails for multivariate polynomials in general.

A real polynomial $p$ is a sum of squares polynomial if $p={\sum }_{\ell }{q}_{\ell }^2$ for real polynomials $q_{\ell }$. Such a representation certifies global nonnegativity. If $m(z)$ is the vector of relevant monomials, the identity $p(z)=m(z{)}^{T}Gm(z)$ with a positive semidefinite matrix $G$ encodes a sum of squares through a Gram matrix. Equating coefficients is linear in $G$, so finding a certificate is a semidefinite program.