# Are these two formulations of semidefinite programming problems equivalent?

From Wikipedia

Denote by $\mathbb{S}^n$ the space of all $n \times n$ real symmetric matrices. The space is equipped with the inner product (where ${\rm tr}$ denotes the trace) $$\langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n A_{ij}B_{ij}.$$ We can rewrite the mathematical program given in the previous section equivalently as $$\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject to} & \langle A_k, X \rangle_{\mathbb{S}^n} \leq b_k, \quad k = 1,\ldots,m \\ & X \succeq 0 \end{array}$$

From Boyd's paper, a semidefinite programming problem is

$$\min_{x \in\mathbb R^m} c^T x$$ subject to $$F_0 + \sum_{i=1}^m x_i F_i ⪰ 0$$ where $c \in \mathbb R^m$ and $m + 1$ symmetric matrices $F_0, ..., F_m \in \mathbb R^{n\times n}$.

I was wondering if the two formulations are equivalent? I am not able to see how they are related. Thanks and regards!

-
Do you mean $\succeq$ instead of $\geq$ in the last constraint? –  Max Hutchinson Mar 15 '13 at 22:18
@MaxHutchinson: Yes. corrected. Thanks! –  Tim Mar 15 '13 at 22:35

As Brian says, if you change the inequality in the first model to an equality constraint (which I would say is much more common than the Wikipedia format), you get a model whose dual is given by $\text{maximize} ~b^Ty$ subject to $C - \sum_{i=1}^m A_i y_i \succeq 0$. In that form, the equivalence should be obvious. Hence, they both define the same primal-dual representation of an SDP, module some signs on some matrices. An SDP solver wants the data $(C,A_i,b)$ so which ever form you work with does not make any difference (once you've managed to figure what these matrices are, it is not uniquely determined so you can accidentally define unnecessarily large models)

-
Thanks!In the first model, if change the inequality to equality, will the model become less general? –  Tim Mar 17 '13 at 1:19
No. If you have some constraint $A_i X \leq b_i$, you can write it in the standard equality form by adding a slack $A_i X + s = b_i$ where $s$ is non-negative (and then optimize over the direct product of the semidefinite cone $X\succeq 0$ and the scalar LP cone $s\geq 0$. All solvers work with optimization over the direct products of several cones, the form written above is a special case with only one cone/lmi) –  Johan Löfberg Mar 17 '13 at 13:08
Thanks! Is "the form written above is a special case with only one cone/lmi)" the original one without slack variables? What does "cone/lmi" mean, "lmi" in particular? –  Tim Mar 18 '13 at 13:16
With LMI (Linear matrix inequalities), we typically mean something like the constraint you have taken from Boyd. LMIs arise in the general field of conic programming, where semidefinite programming is one example. A cone is a special type of sets, one example being the set of positive semidefinite matrices, the positive semidefinite cone. So in other words, the linearly parametrized matrix in the Boyd notation is constrained to the cone of psd matrices. –  Johan Löfberg Mar 18 '13 at 17:49