PolynomialOptimize - Revision history

Nathaniel: Fixing numerical example now that this function is working properly

2023-10-17T18:34:42Z

Fixing numerical example now that this function is working properly

Nathaniel: Is now usable inside of CVX

2023-08-06T01:44:17Z

Is now usable inside of CVX

Nathaniel: Updated examples and notes in light of randomized improvement to inner bound

2023-08-03T16:05:07Z

Updated examples and notes in light of randomized improvement to inner bound

Nathaniel at 18:26, 1 August 2023

2023-08-01T18:26:55Z

Nathaniel: Created

2023-08-01T18:26:29Z

Created

New page

{{Function
|name=PolynomialOptimize
|desc=Bounds the optimal value of a homogeneous polynomial on the unit sphere
|rel=[[CopositivePolynomial]]<br />[[PolynomialAsMatrix]]<br />[[PolynomialSOS]]
|cat=[[List of functions#Polynomial_optimization|Polynomial optimization]]
|upd=August 1, 2023
|cvx=no}}
<tt>'''PolynomialOptimize'''</tt> is a [[List of functions|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

<math>
\max\big\{ p(x_1,x_2,\ldots,x_n) : x_1^2 + x_2^2 + \cdots + x_n^2 = 1 \big\},
</math>
or the corresponding minimization problem.

==Syntax==
* <tt>OB = PolynomialOptimize(P,N,D,K)</tt>
* <tt>OB = PolynomialOptimize(P,N,D,K,OPTTYPE)</tt>
* <tt>[OB,IB] = PolynomialOptimize(P,N,D,K)</tt>
* <tt>[OB,IB] = PolynomialOptimize(P,N,D,K,OPTTYPE)</tt>

==Argument descriptions==
===Input arguments===
* <tt>P</tt>: The polynomial, represented as a vector of coefficients of its monomials in lexicographic order.
* <tt>N</tt>: The number of variables in the polynomial.
* <tt>D</tt>: Half the degree of the polynomial.
* <tt>K</tt>: 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.
* <tt>OPTTYPE</tt> (optional, default <tt>'max'</tt>): Either <tt>'max'</tt> or <tt>'min'</tt>, indicating whether the polynomial should be maximized or minimized.

===Output arguments===
* <tt>OB</tt>: 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.
* <tt>IB</tt>: 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: <math>p(x,y,z) = x^4y^2 + x^2y^4 - 3x^2y^2z^2 + z^6</math>. We can load this polynomial into a list-of-coefficients form that <tt>PolynomialOptimize</tt> understands via the <tt>[[exp2ind]]</tt> helper function:
<syntaxhighlight>
>> 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
</syntaxhighlight>

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:
<syntaxhighlight>
>> PolynomialOptimize(p,n,d,0,'min')

ans =

-0.2000

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

ans =

-0.1104

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

ans =

-0.0780
</syntaxhighlight>

We can see above that increasing the value of <tt>K</tt> (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:
<syntaxhighlight>
>> [ob,ib] = PolynomialOptimize(p,n,d,10,'min')

ob =

-0.0158

ib =

1.6985

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

ob =

-0.0017

ib =

0.2291

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

ob =

-3.3898e-04

ib =

0.0473
</syntaxhighlight>

In other words, by the 500-th level of the hierarchy we have learned that the minimum value of the Motzkin polynomial is between <tt>-3.3898e-04</tt> and <tt>0.0473</tt>.

{{SourceCode|name=PolynomialOptimize}}

==Notes==
The outer bounds produced by this function are typically better than the inner bounds.

==References==
Coming soon.

@@ Line 51: / Line 51: @@
 ans =
-    -0.2000
+    -0.5000
 >> PolynomialOptimize(p,n,d,1,'min')
@@ Line 57: / Line 57: @@
 ans =
-    -0.1104
+    -0.2006
 >> PolynomialOptimize(p,n,d,2,'min')
@@ Line 63: / Line 63: @@
 ans =
-    -0.0780
+    -0.1270
 </syntaxhighlight>
@@ Line 72: / Line 72: @@
 ob =
-    -0.0158
+    -0.0189
@@ Line 90: / Line 90: @@
 .5581e-09
->> [ob,ib] = PolynomialOptimize(p,n,d,500,'min')
+>> [ob,ib] = PolynomialOptimize(p,n,d,250,'min')
 ob =
-   -3.3898e-04
+   -6.8094e-04
 ib =
-.6048e-13
+.7534e-13
 </syntaxhighlight>
-In other words, by the 500-th level of the hierarchy we have learned that the minimum value of the Motzkin polynomial is between <tt>-3.3898e-04</tt> and <tt>4.6048e-13</tt>. 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.
+In other words, by the 250-th level of the hierarchy we have learned that the minimum value of the Motzkin polynomial is between <tt>-6.8094e-04</tt> and <tt>7.7534e-13</tt>. Note that the inner bounds are computed by a randomized algorithm, so when you run the code above you might get different inner bounds.
 {{SourceCode|name=PolynomialOptimize}}

@@ Line 4: / Line 4: @@
 |rel=[[CopositivePolynomial]]<br />[[PolynomialAsMatrix]]<br />[[PolynomialSOS]]
 |cat=[[List of functions#Polynomial_optimization|Polynomial optimization]]
-|upd=August 1, 2023
+|upd=August 5, 2023
-|cvx=no}}
+|cvx=yes}}
 <tt>'''PolynomialOptimize'''</tt> is a [[List of functions|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

@@ Line 77: / Line 77: @@
 ib =
-.6985
+.0333e-06
 >> [ob,ib] = PolynomialOptimize(p,n,d,100,'min')
@@ Line 88: / Line 88: @@
 ib =
-.2291
+.5581e-09
 >> [ob,ib] = PolynomialOptimize(p,n,d,500,'min')
@@ Line 99: / Line 99: @@
 ib =
-.0473
+.6048e-13
 </syntaxhighlight>
-In other words, by the 500-th level of the hierarchy we have learned that the minimum value of the Motzkin polynomial is between <tt>-3.3898e-04</tt> and <tt>0.0473</tt>.
+In other words, by the 500-th level of the hierarchy we have learned that the minimum value of the Motzkin polynomial is between <tt>-3.3898e-04</tt> and <tt>4.6048e-13</tt>. 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.
 {{SourceCode|name=PolynomialOptimize}}
 ==Notes==
-The outer bounds produced by this function are typically better than the inner bounds.
+The inner bounds, even though they are somewhat random, do (deterministically) converge to the true optimal value of the polynomial as <tt>K</tt> approaches infinity.
 ==References==
 Coming soon.

@@ Line 11: / Line 11: @@
 \max\big\{ p(x_1,x_2,\ldots,x_n) : x_1^2 + x_2^2 + \cdots + x_n^2 = 1 \big\},
 </math>
 or the corresponding minimization problem.