# 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? Mar 15 '13 at 22:18

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) 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. Mar 18 '13 at 17:49

There is a duality theory for SDP that is similar to the duality theory for linear programming. The SDP duality theory is weaker than LP duality theory in that you need a constraint qualification in order for strong duality to hold.

Unfortunately, there is no commonly agreed standard primal and dual problem formulation. If you replace the less than or equal to constraints in the first formulation with equality constraints and take the dual, and fix the notation a bit, then you'll get Boyd's form of the SDP problem as the dual of the other problem. As written these aren't quite a primal dual pair, but they are both reasonably normal SDP formulations.

• Thanks! (1)Could you elaborate how "If you replace the less than or equal to constraints in the first formulation with equality constraints and take the dual, and fix the notation a bit, then you'll get Boyd's form of the SDP problem as the dual of the other problem"? (2) Do you mean "Boyd's form of the SDP problem" is the dual of "the other problem"? What does "the other problem"refer to?
– Tim
Mar 16 '13 at 4:55
• "the other problem" refers to the problem that you quoted from Wikipedia. My point was simply that different authors use slightly different variations in their primal-dual SDP formulations. These variations are not of any great significance since it's relatively easy to transform between different SDP formulations. Mar 19 '13 at 15:41