# How to derive the dual of a semidefinite program (SDP)?

I have a semidefinite program (SDP) here, which is equivalent to the trace norm,

$$\begin{array}{ll} \max_{Y \in \mathbb{R}^{m \times n}} & \text{trace}(X^T Y) \\ \text{subject to} & \left[ \begin{array}{cc} I_m & Y \\ Y^T & I_n \end{array} \right] \succeq 0, \end{array} \label{eq:aa:primal}$$

Now I want to derive its dual in a form,

$$\begin{array}{ll} \min_{\substack{W_{1} \in \mathbb{S}^{m}, \\ W_{2} \in \mathbb{S}^{n}}} & \text{trace}(W_{1}) + \text{trace}(W_{2}) \\ \text{subject to} & \left[ \begin{array}{cc} W_{1} & (1/2) X \\ (1/2) X^T & W_{2} \end{array} \right] \succeq 0, \end{array} \label{eq:aa:dual}$$

How am I supposed to introduce the dual variables here?

• Have you tried putting the primal problem into standard form ($\max \mbox{tr}(CQ)$ subject to $\mbox{tr}(A_{i}Q=b_{i}$ for $i=1, 2, \ldots, k$ and $Q \succeq 0$)? What is your objective function matrix $C$? What are the linear equality constraints? What is the dual of that standard form problem? – Brian Borchers Oct 23 '16 at 1:07
• The approach @BrianBorchers suggests is certainly a reasonable one. I think it is better, however, if people can learn to derive more general dual problems through the Lagrangian. In this case, the Lagrange multiplier is a single semidefinite matrix $Z\in\mathbb{R}^{(m+n)\times(m+n}$. What you will find as you simplify the dual function is that you can extract $W_1$ and $W_2$ out of that. – Michael Grant Oct 23 '16 at 16:42
• @MichaelGrant Thanks for your suggestion! However I am thinking why does it makes sense to integrate the product of two matrices which is another $m+n \times m+n$ matrix into the Lagrange form with $\text{trace}{X^TY}, which is not a matrix? – good2know Oct 23 '16 at 19:28 • I'm not sure what you're asking. Do you know how to build a Lagrangian? – Michael Grant Oct 23 '16 at 19:29 • @MichaelGrant Are you suggesting adding an additional$-Z\left[ \begin{array}{cc} I_m & Y \\ Y^T & I_n \end{array} \right]$in the optimization problem? – good2know Oct 23 '16 at 19:36 ## 1 Answer EDIT: I mistakenly misread the original problem as a minimization, not a maximization, so this is wrong. For one thing, the dual is indeed a minimization. But there will also be some sign differences as well. My apologies to the OP, and feel free to remove your upvotes and/or downvote. Let me go ahead and write out my suggestion. As I mentioned, the Lagrange multiplier for any SDP constraint$Q \succeq 0$is a PSD matrix of the same size. Thus the Lagrangian is $$L(Y,Z) = \langle X, Y \rangle - \left\langle Z,\begin{bmatrix} I_m & Y \\ Y^T & I_n \end{bmatrix} \right\rangle$$ where$Z\in\mathcal{S}^{m+n}_+$. (I'm using the definition$\langle A,B \rangle = \mathop{\textrm{Tr}}(A^TB)$here.) To facilitate simplification, we express$Zin a block form: $$Z \triangleq \begin{bmatrix} Z_{11} & Z_{12} \\ Z_{12}^T & Z_{22} \end{bmatrix}$$ \begin{aligned} L(Y,Z) &= \langle X, Y \rangle - \left\langle \begin{bmatrix} Z_{11} & Z_{12} \\ Z_{12}^T & Z_{22} \end{bmatrix}, \begin{bmatrix} I_m & Y \\ Y^T & I_n \end{bmatrix} \right\rangle\\ &= \langle X, Y \rangle - \langle Z_{11}, I_m \rangle - \langle Z_{22}, I_n \rangle - 2 \langle Z_{12}, Y \rangle \\ &= \langle X - 2 Z_{12}, Y \rangle - \langle Z_{11}, I_m \rangle - \langle Z_{22}, I_n\rangle \end{aligned} The dual function is therefore $$g(Z) = \inf_Y L(Y,Z) = \begin{cases} - \langle Z_{11}, I_m \rangle - \langle Z_{22}, I_n \rangle & X - 2 Z_{12} = 0 \\ -\infty & X - 2 Z_{12} \neq 0 \end{cases}$$ The-\infty$arises from the fact that if$X\neq 2Z_{12}$, that linear expression is unbounded below. So the only way you get a bounded value for$g(Z)$is if that first term is identically zero. (For nonlinear dual functions, you would do a more traditional minimization; e.g., by differentiating with respect to$Y$.) Given this dual function, the dual problem is \begin{array}{ll} \text{maximize} & g(Z) \\ \text{subject to} & Z \succeq 0 \end{array} Technically, this is the true Lagrange dual. But in practice we move the implicit domain constraints out of the dual function. \begin{array}{ll} \text{maximize} & - \langle Z_{11}, I_m \rangle - \langle Z_{22}, I_n \rangle \\ \text{subject to} & 2 Z_{12} = X \\ & Z \succeq 0 \end{array} Eliminating$Z_{12}$we obtain \begin{array}{ll} \text{maximize} & - \langle Z_{11}, I_m \rangle - \langle Z_{22}, I_n \rangle = -\mathop{\textrm{Tr}}(Z_{11}) - \mathop{\textrm{Tr}}(Z_{22}) \\ \text{subject to} & \begin{bmatrix} Z_{11} & (1/2) X \\ (1/2) X^T & Z_{22} \end{bmatrix} \succeq 0 \end{array} Of course, we have$W_1 \rightarrow Z_{11}$and$W_2 \rightarrow Z_{22}\$. And the true dual is a maximization, not a minimization as you have written it, so flip yours to a maximization (negating the objective) and we're done.

• I was close! Thanks for your answer! I didn't realize that trace could be written in the inner product! Thanks again for your enlightening answer. – good2know Oct 23 '16 at 19:58
• Are you suggesting that the dual I gave is wrong and should be the maximization? – good2know Oct 23 '16 at 21:13
• Yes, I am. The correct dual is a maximization. – Michael Grant Oct 23 '16 at 21:14
• My TA said the original formulation of the dual is actually right, could you help me figuring out where we have missed? – good2know Oct 31 '16 at 22:33
• Aha! Well, I'll tell you what I missed---for some reason, I thought your original problem was a minimization, so the dual was a maximization. But now that I've taken another look I realize that of course it is the other way around! My apologies. – Michael Grant Oct 31 '16 at 22:35