Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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)

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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. –  Brian Borchers Mar 19 '13 at 15:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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