2
$\begingroup$

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

\begin{equation} \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} \end{equation}

Now I want to derive its dual in a form,

\begin{equation} \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} \end{equation}

How am I supposed to introduce the dual variables here?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brian Borchers Oct 23 '16 at 1:07
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Oct 23 '16 at 16:42
  • $\begingroup$ @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? $\endgroup$ – good2know Oct 23 '16 at 19:28
  • $\begingroup$ I'm not sure what you're asking. Do you know how to build a Lagrangian? $\endgroup$ – Michael Grant Oct 23 '16 at 19:29
  • $\begingroup$ @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? $\endgroup$ – good2know Oct 23 '16 at 19:36
5
$\begingroup$

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 $Z$ in 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – good2know Oct 23 '16 at 19:58
  • $\begingroup$ Are you suggesting that the dual I gave is wrong and should be the maximization? $\endgroup$ – good2know Oct 23 '16 at 21:13
  • $\begingroup$ Yes, I am. The correct dual is a maximization. $\endgroup$ – Michael Grant Oct 23 '16 at 21:14
  • $\begingroup$ My TA said the original formulation of the dual is actually right, could you help me figuring out where we have missed? $\endgroup$ – good2know Oct 31 '16 at 22:33
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Oct 31 '16 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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