CopositivePolynomial - Revision history

Nathaniel: typo fixes

2023-10-18T13:52:27Z

typo fixes

← Older revision		Revision as of 13:52, 18 October 2023
Line 6:		Line 6:
	\|upd=August 1, 2023		\|upd=August 1, 2023
	\|cvx=no}}		\|cvx=no}}
	<tt>'''CopositivePolynomial'''</tt> is a [[List of functions\|function]] that computes the standard quartic homogeneous polynomial that is associated with a copositive matrix (or any symmetric matrix, in ~~an hopes~~ of ~~determineing~~ whether or not the matrix is copositive). For example, the Horn matrix		<tt>'''CopositivePolynomial'''</tt> is a [[List of functions\|function]] that computes the standard quartic homogeneous polynomial that is associated with a copositive matrix (or any symmetric matrix, in the hope of determining whether or not the matrix is copositive). For example, the Horn matrix

	<math>C = \begin{bmatrix}1 & -1 & 1 & 1 & -1 \\ -1 & 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & 1 & -1 \\ -1 & 1 & 1 & -1 & 1\end{bmatrix}</math>		<math>C = \begin{bmatrix}1 & -1 & 1 & 1 & -1 \\ -1 & 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & 1 & -1 \\ -1 & 1 & 1 & -1 & 1\end{bmatrix}</math>

Nathaniel: fix row versus column

2023-08-01T14:45:35Z

fix row versus column

← Older revision		Revision as of 14:45, 1 August 2023
Line 12:		Line 12:
	is associated with the quartic polynomial		is associated with the quartic polynomial

	<math>\displaystyle p(x) = \begin{bmatrix}x_1^2 \\ x_2^2 \\ x_3^2 \\ x_4^2 \\ x_5^2\end{bmatrix}C\begin{bmatrix}x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2\end{bmatrix} = \sum_{i=1}^5 x_i^4 - 2\sum_{i=1}^5x_i^2x_{i+1}^2 + 2\sum_{i=1}^5x_i^2x_{i+2}^2,</math>		<math>\displaystyle p(x) = \begin{bmatrix}x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2\end{bmatrix}C\begin{bmatrix}x_1^2 \\ x_2^2 \\ x_3^2 \\ x_4^2 \\ x_5^2\end{bmatrix} = \sum_{i=1}^5 x_i^4 - 2\sum_{i=1}^5x_i^2x_{i+1}^2 + 2\sum_{i=1}^5x_i^2x_{i+2}^2,</math>

	where the sums in the subscripts are understood to be modulo 5. Copositivity of <math>C</math> is equivalent to non-negativity of the polynomial <math>p</math>.		where the sums in the subscripts are understood to be modulo 5. Copositivity of <math>C</math> is equivalent to non-negativity of the polynomial <math>p</math>.

Nathaniel: Fix exponents

2023-08-01T14:42:16Z

Fix exponents

← Older revision		Revision as of 14:42, 1 August 2023
Line 12:		Line 12:
	is associated with the quartic polynomial		is associated with the quartic polynomial

	<math>\displaystyle p(x) = \begin{bmatrix}x_1^2 \\ x_2^2 \\ x_3^2 \\ x_4^2 \\ x_5^2\end{bmatrix}C\begin{bmatrix}x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2\end{bmatrix} = \sum_{i=1}^5 x_i^4 - 2\sum_{i=1}^~~5x_ix_~~{i+1} + 2\sum_{i=1}^~~5x_ix_~~{i+2},</math>		<math>\displaystyle p(x) = \begin{bmatrix}x_1^2 \\ x_2^2 \\ x_3^2 \\ x_4^2 \\ x_5^2\end{bmatrix}C\begin{bmatrix}x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2\end{bmatrix} = \sum_{i=1}^5 x_i^4 - 2\sum_{i=1}^5x_i^2x_{i+1}^2 + 2\sum_{i=1}^5x_i^2x_{i+2}^2,</math>

	where the sums in the subscripts are understood to be modulo 5. Copositivity of <math>C</math> is equivalent to non-negativity of the polynomial <math>p</math>.		where the sums in the subscripts are understood to be modulo 5. Copositivity of <math>C</math> is equivalent to non-negativity of the polynomial <math>p</math>.

Nathaniel at 14:35, 1 August 2023

2023-08-01T14:35:07Z

← Older revision		Revision as of 14:35, 1 August 2023
Line 66:		Line 66:

	Regardless of whether or not the above verification is performed, the vector p can now be used in polynomial optimization functions like <tt>[[PolynomialOptimize]]</tt> and <tt>[[PolynomialSOS]]</tt>.		Regardless of whether or not the above verification is performed, the vector p can now be used in polynomial optimization functions like <tt>[[PolynomialOptimize]]</tt> and <tt>[[PolynomialSOS]]</tt>.

			===Clique polynomial===
			To be filled in: an example of using this function to create a polynomial whose maximum value bounds the maximum clique size in a graph.

	{{SourceCode\|name=CopositivePolynomial}}		{{SourceCode\|name=CopositivePolynomial}}

Nathaniel: /* The Horn matrix */

2023-08-01T14:33:52Z

The Horn matrix

← Older revision		Revision as of 14:33, 1 August 2023
Line 28:		Line 28:
	>> C = [1,-1,1,1,-1;-1,1,-1,1,1;1,-1,1,-1,1;1,1,-1,1,-1;-1,1,1,-1,1];% the Horn matrix		>> C = [1,-1,1,1,-1;-1,1,-1,1,1;1,-1,1,-1,1;1,1,-1,1,-1;-1,1,1,-1,1];% the Horn matrix
	>> p = CopositivePolynomial(C);		>> p = CopositivePolynomial(C);
	>> sparse(p)		>> sparse(p)% displays the non-zero coefficients of this polynomial

	ans =		ans =

Nathaniel: /* The Horn matrix */ finished

2023-08-01T14:31:25Z

The Horn matrix: finished

@@ Line 27: / Line 27: @@
 <syntaxhighlight>
 >> C = [1,-1,1,1,-1;-1,1,-1,1,1;1,-1,1,-1,1;1,1,-1,1,-1;-1,1,1,-1,1];% the Horn matrix
->> More coming soon.
+>> p = CopositivePolynomial(C);
 </syntaxhighlight>
 {{SourceCode|name=CopositivePolynomial}}

Nathaniel: Started

2023-08-01T14:23:59Z

Started

New page

{{Function
|name=CopositivePolynomial
|desc=Creates a homogenous polynomial whose non-negativity is equivalent to copositivity of a given matrix
|rel=[[PolynomialAsMatrix]]<br />[[PolynomialOptimize]]<br />[[PolynomialSOS]]
|cat=[[List of functions#Polynomial_optimization|Polynomial optimization]]
|upd=August 1, 2023
|cvx=no}}
<tt>'''CopositivePolynomial'''</tt> is a [[List of functions|function]] that computes the standard quartic homogeneous polynomial that is associated with a copositive matrix (or any symmetric matrix, in an hopes of determineing whether or not the matrix is copositive). For example, the Horn matrix

<math>C = \begin{bmatrix}1 & -1 & 1 & 1 & -1 \\ -1 & 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & 1 & -1 \\ -1 & 1 & 1 & -1 & 1\end{bmatrix}</math>

is associated with the quartic polynomial

<math>\displaystyle p(x) = \begin{bmatrix}x_1^2 \\ x_2^2 \\ x_3^2 \\ x_4^2 \\ x_5^2\end{bmatrix}C\begin{bmatrix}x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2\end{bmatrix} = \sum_{i=1}^5 x_i^4 - 2\sum_{i=1}^5x_ix_{i+1} + 2\sum_{i=1}^5x_ix_{i+2},</math>

where the sums in the subscripts are understood to be modulo 5. Copositivity of <math>C</math> is equivalent to non-negativity of the polynomial <math>p</math>.

==Syntax==
* <tt>P = CopositivePolynomial(C)</tt>

==Argument descriptions==
* <tt>C</tt>: A matrix.

==Examples==
===The Horn matrix===
Let's compute the polynomial (as a vector) representation of the Horn matrix.
<syntaxhighlight>
>> C = [1,-1,1,1,-1;-1,1,-1,1,1;1,-1,1,-1,1;1,1,-1,1,-1;-1,1,1,-1,1];% the Horn matrix
>> More coming soon.
</syntaxhighlight>

{{SourceCode|name=CopositivePolynomial}}

==References==
Coming soon.