PolynomialSOS

PolynomialSOS
Bounds the optimal value of a homogeneous polynomial on the unit sphere via the Sum-Of-Squares hierarchy
Other toolboxes required	CVX
Related functions	CopositivePolynomial PolynomialAsMatrix PolynomialOptimize
Function category	Polynomial optimization
Usable within CVX?	yes

PolynomialSOS is a function that computes upper and lower bounds on the optimum (i.e., maximum or minimum) value of an even-degree homogeneous polynomial on the unit sphere. That is, given an even-degree n-variable homogeneous polynomial p, this function bounds the (very difficult to compute in general) quantity

\( \max\big\{ p(x_1,x_2,\ldots,x_n) : x_1^2 + x_2^2 + \cdots + x_n^2 = 1 \big\}, \)

or the corresponding minimization problem. This function makes use of the sum-of-squares hierarchy, which requires semidefinite programming and thus, for a given level of the hierarchy, is slower but more accurate than the PolynomialOptimize function.

Syntax

• OB = PolynomialSOS(P,N,D,K)
• OB = PolynomialSOS(P,N,D,K,OPTTYPE)
• [OB,IB] = PolynomialSOS(P,N,D,K)
• [OB,IB] = PolynomialSOS(P,N,D,K,OPTTYPE)

Argument descriptions

Input arguments

• P: The polynomial, represented as a vector of coefficients of its monomials in lexicographic order.
• N: The number of variables in the polynomial.
• D: Half the degree of the polynomial.
• K: A non-negative integer that specifies the level of the hierarchy that is used to compute the bound(s) on the optimal value. Larger values of K result in better bounds at the expense of increases memory usage and longer computation times.
• OPTTYPE (optional, default 'max'): Either 'max' or 'min', indicating whether the polynomial should be maximized or minimized.

Output arguments

• OB: An "outer" bound on the optimal value. If maximizing, this is an upper bound on the maximum; if minimizing, this is a lower bound on the minimum.
• IB: An "inner" bound on the optimal value. If maximizing, this is a lower bound on the maximum; if minimizing, this is an upper bound on the minimum.

Examples

The Motzkin polynomial

The Motzkin polynomial is the following degree-6 homogeneous polynomial\[p(x,y,z) = x^4y^2 + x^2y^4 - 3x^2y^2z^2 + z^6\]. We can load this polynomial into a list-of-coefficients form that PolynomialOptimize understands via the exp2ind helper function:

>> n = 3;% number of variables
>> d = 3;% half the degree of the polynomial
>> p = zeros(nchoosek(n+2*d-1,2*d),1);% initialize p to have the correct size
>> p(exp2ind([4 2 0])) = 1;% the "4 2 0" here are the exponents in the term x^4y^2z^0, while the "1" is the coefficient of this term
>> p(exp2ind([2 4 0])) = 1;
>> p(exp2ind([2 2 2])) = -3;
>> p(exp2ind([0 0 6])) = 1;% now p represents the Motzkin polynomial

The Motzkin polynomial, despite the fact that it cannot be written as a sum of squares, is non-negative. The K = 0 level of this function verifies that p cannot be written as a sum of squares (if it could, the following code would return a non-negative answer):

>> PolynomialSOS(p,n,d,0,'min')

ans =

   -0.0046

We can verify that the Motzkin polynomial is non-negative by increasing the value of K (i.e., the level of the hierarchy):

>> PolynomialSOS(p,n,d,1,'min')

ans =

   6.1270e-12

Since the true minimum value of this polynomial on the unit sphere is 0, for this polynomial higher levels of K will not improve the lower bound (we already got the exact answer, within numerical precision). However, we can get better and better upper bounds by increasing K:

>> [ob,ib] = PolynomialSOS(p,n,d,2,'min')

ob =

   5.9776e-12


ib =

    7.0050e-09

>> [ob,ib] = PolynomialSOS(p,n,d,3,'min')

ob =

   1.2217e-11


ib =

    3.8579e-09

Note that the inner bounds are computed by an algorithm that includes some randomness, so when you run the code above you might get different inner bounds.

Usable within CVX

This function is CVX-friendly, meaning that when running in 'min' mode you can use it in CVX as you would any other concave function, and when running in 'max' mode you can use it in CVX as you would any other convex function. For example, the following semidefinite program in CVX shows that, for 3-variable degree-6 homogeneous polynomials p that can be written as a sum of squares and have their \(x^6\), \(y^6\), \(z^6\), \(x^4y^2\), \(x^2y^4\), \(x^4z^2\), \(x^2z^4\), \(y^4z^2\) and \(y^2z^4\) coefficients equal to 1, the minimal coefficient of the \(x^2y^2z^2\) term is -9:

>> n = 3;% number of variables
>> d = 3;% half the degree of the polynomial
>> cvx_begin sdp quiet
>>     cvx_precision best;
>>     variable p(nchoosek(n+2*d-1,2*d),1)
>>     minimize p(exp2ind([2 2 2]))
>>     subject to
>>         PolynomialSOS(p,n,d,0,'min') >= 0;
>>         p(exp2ind([6 0 0])) == 1;
>>         p(exp2ind([0 6 0])) == 1;
>>         p(exp2ind([0 0 6])) == 1;
>>         p(exp2ind([4 2 0])) == 1;
>>         p(exp2ind([2 4 0])) == 1;
>>         p(exp2ind([4 0 2])) == 1;
>>         p(exp2ind([2 0 4])) == 1;
>>         p(exp2ind([0 4 2])) == 1;
>>         p(exp2ind([0 2 4])) == 1;
>> cvx_end
>> cvx_optval

cvx_optval =

   -9.0000

Source code

Click here to view this function's source code on github.

Notes

• The inner bounds, even though they are somewhat random, do (deterministically) converge to the true optimal value of the polynomial as K approaches infinity.
• If K = 0 and OPTTYPE = 'min' then the output of this function is non-negative if and only if P can be written as a sum of squares of polynomials.

References

Coming soon.