8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Would you mind if I ask why you would want to? Is this homework? The reason I ask is that while you can convert from one form to the other, it's a rather tedious thing to do. And frankly, it's not that illuminating. More interesting is that the two forms are duals of each other. That is, the dual of your standard inequality form can be written quite easily in the equality-constrained conic form---and vice versa. To me, that's the more interesting result. $\endgroup$ – Michael Grant Mar 30 '14 at 17:36
  • $\begingroup$ Yes, it is more interesting - and this I've manage to show. the thing is, i need to lecture on it, as a part of my homework, but i don't want to say that the two forms are equivalent (not dual), as long as I don't see how they could be. $\endgroup$ – Noa Haas Mar 30 '14 at 17:39
  • $\begingroup$ I mean, the dual problem I construct from the primal problem has the conic form, but also strong links to the primal's constrain and target function - which makes it easy to see why are related (but not equivalent, to my understanding.) $\endgroup$ – Noa Haas Mar 30 '14 at 17:44
  • $\begingroup$ The primal and dual problems are not equivalent, that's correct. $\endgroup$ – Michael Grant Mar 30 '14 at 21:07
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How can one know whether there exists a positive semidefinite $\bar{X}$ to begin with? If I'm not mistaken, not all SDP:s will have a solution. $\endgroup$ – index Aug 9 '17 at 16:38
  • $\begingroup$ Sorry to ask about such an old answer, but would you mind expanding on the last part - how to show that zeroing out the elements does not affect optimality? $\endgroup$ – sps Oct 22 '17 at 19:50
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.