PolynomialSOS - Revision history

Nathaniel: /* Examples */ adjusting example values now that function has been updated

2023-08-09T12:14:51Z

Examples: adjusting example values now that function has been updated

← Older revision		Revision as of 12:14, 9 August 2023
Line 61:		Line 61:
	ans =		ans =

	6.~~1270e~~-12		-3.2425e-10
	</syntaxhighlight>		</syntaxhighlight>

Line 71:		Line 71:
	ob =		ob =

	5.~~9776e~~-12		9.8781e-12


	ib =		ib =

	7.~~0050e~~-09		2.4182e-07

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

	1.~~2217e~~-11		1.6065e-11

Nathaniel: /* Usable within CVX */

2023-08-06T00:13:32Z

Usable within CVX

← Older revision		Revision as of 00:13, 6 August 2023
Line 103:		Line 103:
	>> minimize p(exp2ind([2 2 2]))		>> minimize p(exp2ind([2 2 2]))
	>> subject to		>> subject to
	>> PolynomialSOS(p,3,3,0,'min') >= 0;		>> PolynomialSOS(p,n,d,0,'min') >= 0;
	>> p(exp2ind([6 0 0])) == 1;		>> p(exp2ind([6 0 0])) == 1;
	>> p(exp2ind([0 6 0])) == 1;		>> p(exp2ind([0 6 0])) == 1;

Nathaniel: Finished in-CVX example

2023-08-06T00:12:33Z

Finished in-CVX example

← Older revision		Revision as of 00:12, 6 August 2023
Line 93:		Line 93:

	===Usable within CVX===		===Usable within CVX===
	This function is CVX-friendly, meaning that when running in <tt>'min'</tt> mode you can use it in CVX as you would any other concave function, and when running in <tt>'max'</tt> 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 ?? coefficients equal to 1, the minimal coefficient of the <math>x^2y^2z^2</math> term is -9:		This function is CVX-friendly, meaning that when running in <tt>'min'</tt> mode you can use it in CVX as you would any other concave function, and when running in <tt>'max'</tt> 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 <math>x^6</math>, <math>y^6</math>, <math>z^6</math>, <math>x^4y^2</math>, <math>x^2y^4</math>, <math>x^4z^2</math>, <math>x^2z^4</math>, <math>y^4z^2</math> and <math>y^2z^4</math> coefficients equal to 1, the minimal coefficient of the <math>x^2y^2z^2</math> term is -9:

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

Nathaniel: Added in-CVX example

2023-08-06T00:03:46Z

Added in-CVX example

@@ Line 91: / Line 91: @@
 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=PolynomialSOS}}
 ==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.
+* 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.

Nathaniel: Can now be used within CVX

2023-08-05T23:24:12Z

Can now be used within CVX

← Older revision		Revision as of 23:24, 5 August 2023
Line 5:		Line 5:
	\|req=[http://cvxr.com/cvx/ CVX]		\|req=[http://cvxr.com/cvx/ CVX]
	\|cat=[[List of functions#Polynomial_optimization\|Polynomial optimization]]		\|cat=[[List of functions#Polynomial_optimization\|Polynomial optimization]]
	\|upd=August 1, 2023		\|upd=August 5, 2023
	\|cvx=no}}		\|cvx=yes}}
	<tt>'''PolynomialSOS'''</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		<tt>'''PolynomialSOS'''</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

Nathaniel: Updated in light of random inner bounds modification to the code

2023-08-03T16:08:12Z

Updated in light of random inner bounds modification to the code

← Older revision		Revision as of 16:08, 3 August 2023
Line 76:		Line 76:
	ib =		ib =

	4.~~0000~~		7.0050e-09

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

	3.~~4286~~		3.8579e-09
	</syntaxhighlight>		</syntaxhighlight>

	~~To get even better upper~~ bounds, ~~we would be better off using higher levels of~~ the ~~<tt>[[PolynomialOptimize]]</tt> hierarchy~~.		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=PolynomialSOS}}		{{SourceCode\|name=PolynomialSOS}}

	==Notes==		==Notes==
	The ~~outer~~ bounds ~~produced by this function~~ are ~~typically much 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 K approaches infinity.

	==References==		==References==
	Coming soon.		Coming soon.

Nathaniel: Requires CVX

2023-08-01T18:54:22Z

Requires CVX

← Older revision		Revision as of 18:54, 1 August 2023
Line 3:		Line 3:
	\|desc=Bounds the optimal value of a homogeneous polynomial on the unit sphere via the Sum-Of-Squares hierarchy		\|desc=Bounds the optimal value of a homogeneous polynomial on the unit sphere via the Sum-Of-Squares hierarchy
	\|rel=[[CopositivePolynomial]]<br />[[PolynomialAsMatrix]]<br />[[PolynomialOptimize]]		\|rel=[[CopositivePolynomial]]<br />[[PolynomialAsMatrix]]<br />[[PolynomialOptimize]]
			\|req=[http://cvxr.com/cvx/ CVX]
	\|cat=[[List of functions#Polynomial_optimization\|Polynomial optimization]]		\|cat=[[List of functions#Polynomial_optimization\|Polynomial optimization]]
	\|upd=August 1, 2023		\|upd=August 1, 2023

Nathaniel at 18:53, 1 August 2023

2023-08-01T18:53:54Z

← Older revision		Revision as of 18:53, 1 August 2023
Line 5:		Line 5:
	\|cat=[[List of functions#Polynomial_optimization\|Polynomial optimization]]		\|cat=[[List of functions#Polynomial_optimization\|Polynomial optimization]]
	\|upd=August 1, 2023		\|upd=August 1, 2023
	\|cvx=~~yes~~}}		\|cvx=no}}
	<tt>'''PolynomialSOS'''</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		<tt>'''PolynomialSOS'''</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

Nathaniel: Started

2023-08-01T18:53:17Z

Started

New page

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

==Syntax==
* <tt>OB = PolynomialSOS(P,N,D,K)</tt>
* <tt>OB = PolynomialSOS(P,N,D,K,OPTTYPE)</tt>
* <tt>[OB,IB] = PolynomialSOS(P,N,D,K)</tt>
* <tt>[OB,IB] = PolynomialSOS(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. The <tt>K = 0</tt> 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):
<syntaxhighlight>
>> PolynomialSOS(p,n,d,0,'min')

ans =

-0.0046
</syntaxhighlight>

We can verify that the Motzkin polynomial is non-negative by increasing the value of <tt>K</tt> (i.e., the level of the hierarchy):
<syntaxhighlight>
>> PolynomialSOS(p,n,d,1,'min')

ans =

6.1270e-12
</syntaxhighlight>

Since the true minimum value of this polynomial on the unit sphere is 0, for this polynomial higher levels of <tt>K</tt> 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 <tt>K</tt>:

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

ob =

5.9776e-12

ib =

4.0000

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

ob =

1.2217e-11

ib =

3.4286
</syntaxhighlight>

To get even better upper bounds, we would be better off using higher levels of the <tt>[[PolynomialOptimize]]</tt> hierarchy.

{{SourceCode|name=PolynomialSOS}}

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

==References==
Coming soon.