Consider the following quartic form in
and suppose we would like to decide if is globally nonnegative. In other words, we want to know whether the proposition
is true. A sufficient condition for to be globally nonnegative is the existence of a sum of squares decomposition [1, 2]
where . If such a decomposition does indeed exist, how do we compute it? How do we find the polynomials?
Note that is a quartic form, i.e., a polynomial whose monomials all have total degree 4. Using Parrilo’s method [1, 2], let us try to write as a quadratic form in all the monomials of total degree equal to 2, as follows
where the real matrix
is symmetric. Hence, we obtain
and, matching coefficients, we get the equality constraints
, , , , .
Let us make , where , so that . Hence, we obtain a family of symmetric matrices parameterized by
For each choice of , we get a matrix . We then conclude that the representation , where , is not unique. Since there are infinitely many admissible matrices, if we are able to find a positive semidefinite one, then for all , and global nonnegativity of the given polynomial is guaranteed!
For instance, let us try . We then get
which is positive semidefinite. Computing a Cholesky factorization of , i.e., finding a matrix such that , we get
and, thus, , which finally yields a sum of squares (SOS) decomposition
To make sure that this SOS decomposition is correct, we can use a little Python / SymPy script:
from sympy import * # symbolic variables x = Symbol('x') y = Symbol('y') # define polynomial F = 2*(x**4) + 2*(x**3)*y - (x**2)*(y**2) + 5*(y**4) # define SOS polynomials f1 = (sqrt(2)/2) * (2*(x**2) - 3*(y**2) + x*y) f2 = (sqrt(2)/2) * (y**2 + 3*x*y) # construct residual polynomial R = F - (f1**2 + f2**2) print "Residual polynomial: %s" % R.expand()
The residual polynomial is . The SOS decomposition is correct! We can then conclude that the given polynomial is globally nonnegative.
Remark: this post is based on example 4.1 of Parrilo’s doctoral dissertation  and also on example 3.5 of Parrilo’s paper .
 Pablo Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Dissertation (Ph.D.), California Institute of Technology, 2000.
 Pablo Parrilo, Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming, 2003.