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.

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.

References

Coming soon.