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