4
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ Do you mean $\succeq$ instead of $\geq$ in the last constraint? $\endgroup$
    – Max Hutchinson
    Mar 15, 2013 at 22:18

2 Answers 2

Reset to default
3
$\begingroup$

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)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks!In the first model, if change the inequality to equality, will the model become less general? $\endgroup$
    – Tim
    Mar 17, 2013 at 1:19
  • $\begingroup$ 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) $\endgroup$
    – Johan Löfberg
    Mar 17, 2013 at 13:08
  • $\begingroup$ 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? $\endgroup$
    – Tim
    Mar 18, 2013 at 13:16
  • $\begingroup$ 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. $\endgroup$
    – Johan Löfberg
    Mar 18, 2013 at 17:49
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Tim
    Mar 16, 2013 at 4:55
  • $\begingroup$ "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. $\endgroup$
    – Brian Borchers
    Mar 19, 2013 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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