Difference between revisions of "CopositivePolynomial"

	CopositivePolynomial
	Creates a homogenous polynomial whose non-negativity is equivalent to copositivity of a given matrix
Other toolboxes required	none
Related functions	PolynomialAsMatrix; PolynomialOptimize; PolynomialSOS
Function category	Polynomial optimization
Usable within CVX?	no

Revision as of 14:45, 1 August 2023

CopositivePolynomial is a 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

\(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}\)

is associated with the quartic polynomial

\(\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,\)

where the sums in the subscripts are understood to be modulo 5. Copositivity of \(C\) is equivalent to non-negativity of the polynomial \(p\).

Syntax

P = CopositivePolynomial(C)

Argument descriptions

C: A matrix.

Examples

The Horn matrix

Let's compute the polynomial (as a vector) representation of 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);
>> sparse(p)% displays the non-zero coefficients of this polynomial

ans =

   (1,1)        1
   (6,1)       -2
  (10,1)        2
  (13,1)        2
  (15,1)       -2
  (36,1)        1
  (40,1)       -2
  (43,1)        2
  (45,1)        2
  (56,1)        1
  (59,1)       -2
  (61,1)        2
  (66,1)        1
  (68,1)       -2
  (70,1)        1

To verify that the above vector of coefficients really does represent the polynomial associated with the Horn matrix, we can perform the follow computation (which requires MATLAB's symbolic computation package):

>> syms x1 x2 x3 x4 x5
>> x = [x1;x2;x3;x4;x5];
>> n = 5;% number of variables = size of Horn matrix
>> d = 2;% half of the degree of the (quartic) polynomial
>> M = PolynomialAsMatrix(p,n,d);% compute a compact fully symmetric matrix representation of this polynomial
>> P = SymmetricProjection(n,d,1,0);% used to expand M to non-symmetric coordinates
>> MF = P*M*P';% MF is a matrix representation in non-symmetric coordinates
>> expand(kron(x,x).'*MF*kron(x,x))% expand to a polynomial
 
ans =
 
x1^4 - 2*x1^2*x2^2 + 2*x1^2*x3^2 + 2*x1^2*x4^2 - 2*x1^2*x5^2 + x2^4 - 2*x2^2*x3^2 + 2*x2^2*x4^2 + 2*x2^2*x5^2 + x3^4 - 2*x3^2*x4^2 + 2*x3^2*x5^2 + x4^4 - 2*x4^2*x5^2 + x5^4

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

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.

Source code

Click here to view this function's source code on github.

References

Coming soon.

@@ Line 12: / Line 12: @@
 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>.