1
$\begingroup$

I have a graph with edge-set E and the following SDP (page 8 here)

I'm trying to use CVXOPT to solve this problem, which asks for SDP to be expressed in vectorized form as below:

How do I go about turning my SDP into this form?

Update From suggestion of Joachim Dahl it's easier to figure out values from the dual form. We need to set $G_1,h_1$ and $c$ as follows

$G_1=\left(\begin{array}{c} \text{vec}(I)\\\\ \text{vec}(U_{e1})\\\\ \text{vec}(U_{e2})\\\\ \cdots\\\\ \text{vec}(U_{em}) \end{array}\right)$

here $I$ is $n\times n$ identity matrix, $\text{vec}(A)$ is matrix $A$ taken as vector in row-major vector form, $U_{ek}$ is a $0,1$-valued matrix where entry $i,j$ is 1 iff $i,j$ is in the edge $ek$.

$c = (-1,0,0,0,0,\ldots,0)$

$h_1=- \left(\begin{array}{ccc} 1&1&\ldots\\\\ 1&1&\ldots\\\\ \ldots&\ldots&\ldots \end{array} \right)$

Note that for a graph with $n$ nodes and $m$ edges, $G_1$ is an $m+1\times n^2$ matrix, $c$ is a vector of length $m+1$ and $h_1$ is an $n\times n$ matrix. Matrix $X$ from original formulation is the $z_1$ parameter, an $n^2$ vector representing the matrix in row-major form

2 Answers 2

1

$x$= vec_c(X)

$c$= vec_c( $e e^T$ )

vec_c(A) here is a column-major vectorization.

Set of constraints can be expressed in the form Ax=b, where A is matrix $G_1$ in the question update, and vector b= (1, 0, ..., 0 ). First row takes care of trace constraint, and all the next take care of edge constraints.

positive semi-definite constraint can be set via $G_1 x + s_1= h_1$, in particular $G_1$ is minus identity matrix of size $n^2 \times n^2$, and $h_1=0$.

It is computationally more efficient to implement it in a functional form. There is corresponding interface in python, I do not know about other implementations. You also need to take care of matrix representation, CVXOPT assumes it is symmetric, and access only lower triangular part of it, see manual you linked for details.

  • 0
    Let me know if you find any example where sdp relaxation and QP give different results.2011-03-04
2

You can put $h_1 = 0$ and put $ G_1 = -\frac{1}{2} \sum_{i \leq j} (e_{ij}+e_{ji}) x_{ij}. $ This way you have that $x_{ij}$ are the entries of a PSD. You can add your constraints using $Ax=b$. Finally, notice that your objective function is linear in the entries of the matrix.

  • 0
    Yaroslav, look at the example there. $G_1$ is linear combination of symmetric matrices, the coefficients being the $x$'s.2011-03-02