PolynomialOptimize

	PolynomialOptimize
	Bounds the optimal value of a homogeneous polynomial on the unit sphere
Other toolboxes required	none
Related functions	CopositivePolynomial; PolynomialAsMatrix; PolynomialSOS
Function category	Polynomial optimization
Usable within CVX?	yes

PolynomialOptimize 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.

Syntax

OB = PolynomialOptimize(P,N,D,K)
OB = PolynomialOptimize(P,N,D,K,OPTTYPE)
[OB,IB] = PolynomialOptimize(P,N,D,K)
[OB,IB] = PolynomialOptimize(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. In fact, the minimum value of this polynomial over the unit sphere is exactly 0. We can get lower bounds for the optimal value as follows:

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

ans =

   -0.5000

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

ans =

   -0.2006

>> PolynomialOptimize(p,n,d,2,'min')

ans =

   -0.1270

We can see above that increasing the value of K (i.e., the level of the hierarchy) results in a better lower bound (i.e., a bound that is closer to the true minimum value of 0). This function is fast enough that we can go to a much higher level of the hierarchy, and we can also get upper bounds on this minimum value:

>> [ob,ib] = PolynomialOptimize(p,n,d,10,'min')

ob =

   -0.0189


ib =

    1.0333e-06

>> [ob,ib] = PolynomialOptimize(p,n,d,100,'min')

ob =

   -0.0017


ib =

    1.5581e-09

>> [ob,ib] = PolynomialOptimize(p,n,d,250,'min')

ob =

  -6.8094e-04


ib =

    7.7534e-13

In other words, by the 250-th level of the hierarchy we have learned that the minimum value of the Motzkin polynomial is between -6.8094e-04 and 7.7534e-13. Note that the inner bounds are computed by a randomized algorithm, 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.