Last week, we concluded that the quartic form
has the following sum of squares decomposition
and, thus, is globally nonnegative. More generally, we saw that can be written as follows
where is a parameter. Let us define and
so that we can write polynomial in the more compressed form . A sufficient condition for the existence of a SOS decomposition is that is positive semidefinite, i.e., . Why? If is positive semidefinite, then it has a Cholesky factorization and, thus, , which finally yields the SOS decomposition
where is the entry of matrix . One can also think of the Cholesky factorization as , where , so that we obtain . However, let us not lose sight of where we are going. The question to be answered is: how do we find a such that ?
Admissible values of
Saying that is positive semidefinite is equivalent to saying that the principal minors of are nonnegative. If , then the three 1st degree principal minors (which are the diagonal entries of ) lead to the three inequalities
, , .
The first two inequalities are redundant, and the third yields . The three 2nd degree principal minors (determinants of submatrices of ) and the 3rd degree principal minor (determinant of ) can be computed with the following Python / SymPy script:
from sympy import * # symbolic variable Lambda = Symbol('Lambda') # build matrix Q Q = Matrix([[2,-Lambda,1], [-Lambda,5,0], [1,0,2*Lambda-1]]) print "\n2nd degree principal minors:" print Q.extract([0,1],[0,1]).det() print Q.extract([0,2],[0,2]).det() print Q.extract([1,2],[1,2]).det() print "\n3rd degree principal minor:" print Q.det().factor()
which produces the following output:
2nd degree principal minors: -Lambda**2 + 10 4*Lambda - 3 10*Lambda - 5 3rd degree principal minor: -(Lambda - 3)*(2*Lambda**2 + 5*Lambda - 5)
From the three 2nd degree principal minors, we then obtain the three inequalities
which are equivalent to
which yields . From the 3rd degree principal minor, we obtain the inequality
Hence, we have that admissible values of must satisfy
The roots of polynomial are . Unfortunately is in . Hence, let us partition the interval into two intervals:
- for , we have that is negative, and thus implies that , but
- for , we have that polynomial is nonnegative, and thus implies that . Hence,
Finally, we conclude that the set of admissible values of is . Note that .
An ensemble of SOS decompositions
Now that we know for which values of matrix is positive semidefinite, we can compute various SOS decompositions. The following Python / SymPy script computes an SOS decomposition for :
from sympy import * # symbolic variables Lambda = Symbol('Lambda') x = Symbol('x') y = Symbol('y') # define polynomial F = 2*(x**4) + 2*(x**3)*y - (x**2)*(y**2) + 5*(y**4) # build matrix Q Q = Matrix([[2,-Lambda,1], [-Lambda,5,0], [1,0,2*Lambda-1]]) # build vector of monomials z = Matrix(3, 1, [x**2, y**2, x*y]) # compute Cholesky factorization # for a particular value of Lambda B = Q.subs(Lambda, Rational(3,1)).cholesky() # obtain vector of SOS polynomials f = B.T * z print "\nSOS polynomials:" pprint(f) pprint(f) pprint(f) # compute residual polynomial R = F - sum([f[i]**2 for i in [0,1,2]]) print "\nResidual polynomial: %s" % R.expand()
and it produces the SOS decomposition
which is the one we obtained last week. For , we get
and to verify that this is correct, we can run the script:
h0 = Rational(1,2) * (2*x**2 - Rational(3,2)*y**2 + x*y)**2 h1 = 62 * (Rational(3,62)*x*y + Rational(1,4)*y**2)**2 h2 = Rational(1302,961)*x**2*y**2 pprint((F - (h0 + h1 + h2)).expand())
For , we obtain the SOS decomposition
But, Доверяй, но проверяй!
h0 = Rational(1,2) * (2*x**2 - Rational(5,2)*y**2 + x*y)**2 h1 = Rational(30,16) * (Rational(2,3)*x*y + y**2)**2 h2 = Rational(8,3)*x**2*y**2 pprint((F - (h0 + h1 + h2)).expand())
What happens for non-admissible values of ?
We know that if , then . What if ? Then matrix will be negative definite and will, or will not, have a Cholesky factorization, depending on what convention one uses.
One can think of matrices and in the Cholesky factorizations and , respectively, as square roots of matrix . Do negative reals have square roots? They do if you are willing to work with complex numbers. Likewise, a negative definite will have a Cholesky factorization if one is willing to work with complex matrices. For example, for we obtain the SOS decomposition
where the polynomials are:
where . Note that , but . If we square , we get . This term is being subtracted from the sum of squares, which prevents us from concluding global nonnegativity. That is why we impose the condition .