Convert Semidefinite program forms

How do I convert the following SDP problem (written in the standard inequality form):

$$\min c^T x$$ $$\text{s.t. }F(x)\succeq0$$

When $F(x)\equiv F_{0}+\sum_{i=1}^{m}x_{i}F_{i}$ when $F_{i}\in S^{n}$, $i=0,\ldots,m$

To the following conic form:

$$\min_{X\in S^{n}} \langle C,X \rangle$$ $$\text{s.t. }\langle A_{i},X \rangle=b_{i} , i=1,\ldots,m$$ $$X\succeq0$$

I mean, how do i show that they are equivalent?

Solution 1:

I'm going to get you part of the way there in one direction. First, write it as follows: $$\begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & \sum_i F_i x_i - \bar{X} = - F_0 \\ & \bar{X} \succeq 0 \end{array}$$ Split each free variable into the difference of nonnegatives: $$x_i=x_{+,i}-x_{-,i} \quad x_{+,i},x_{-,i}\geq 0 \quad 1,2,\dots,m$$ So this gets you to here: $$\begin{array}{ll} \text{minimize} & c^T x_+ - c^T x_- \\ \text{subject to} & \sum_i F_i x_{+,i} - \sum_i F_i x_{-,i} - \bar{X} = -F_0 \\ & x_{+,i},x_{-,i} \geq 0, ~i=1,2,\dots, m\\ & \bar{X} \succeq 0 \end{array}$$ Now define a block diagonal matrix $X$: $$ X = \begin{bmatrix} \mathop{\textrm{diag}}(x_+) \\ & \mathop{\textrm{diag}}(x_-) \\ & & \bar{X} \end{bmatrix} $$ This is the matrix for your conic form. Now you need to come up with the equality constraints and the objective vector. The objective matrix is pretty easy: $$ C = \begin{bmatrix} \mathop{\textrm{diag}}(c) \\ & -\mathop{\textrm{diag}}(c) \\ & & 0 \end{bmatrix} $$ There are $n(n+1)/2$ unique equality constraints above. The vector $b_i$ isn't difficult to come up with---it is composed of the $n(n+1)/2$ elements of $-F_0$. The matrices $A_i$ are the tedious part.

Now, you might wonder how you will enforce the block diagonal structure of $X$. One option is to create $(n+2m)(n+2m+1)/2-2m-n(n+1)/2$ equality constraints to fix those off-block-diagonal elements to zero. However, if you're really clever, you can actually show that you don't need those. They will either be zero already at the optimum; or you can show that you can zero out those parts of the solution and it will remain optimal and feasible.

Solution 2:

To build on Michael's answer, I believe the LMI on SDP standard form is:

$$\begin{array}{ll} \text{minimize} & \text{tr}(C\bar{X}) \\ \text{subject to} & \text{tr}(A_{ij}\bar{X}) = - F_{0,ij}, \quad i,j=1,\ldots,n \\ & \bar{X} \succeq 0 \end{array}$$

where $M_{ij}$ is the $(i,j)$th element of any matrix $M$, and

$$A_{ij}=\text{diag}(F_{1,ij},\ldots,F_{m,ij},-F_{1,ij},\ldots,-F_{m,ij},-1).$$