Dual Optimization Problem I have the following optimization problem,
$$ \text{minimize}_{X,Y} \ \lVert X\rVert_* + \lambda \lVert Y\rVert_1 \\
 \text{subject to }X + Y = C$$
$C \in \mathcal{R}^{m \times n}$,  $\lVert Y\rVert_1$ denotes sum of absolute values of matrix entries ($\lambda \gt 0 $). $\lVert X\rVert_*$ denotes the nuclear norm of a matrix (sum of its singular values). 
I am looking to find its dual problem. I know the usual procedure to deal with this, but cannot think much with this problem.
Any hint, suggests please.
 A: It's actually easier if we work with function notation for awhile and not norms. So let's define $f_1(X)=\|X\|_*$ and $f_2(Y)=\|Y\|_1$ and write it as
$$\begin{array}{ll}
\text{minimize}_{X,Y} & f_1(X) + \lambda f_2(Y) \\
                      & X + Y = C
\end{array}$$
The Lagrangian is
$$\begin{aligned}
L(X,Y,Z) &= f_1(X) + \lambda f_2(Y) - \langle Z, X + Y - C \rangle \\
         &= f_1(X) - \langle Z, X \rangle + \lambda f_2(Y) - \langle Z, Y \rangle + \langle Z, C \rangle
\end{aligned}$$
The dual function is
$$\begin{aligned}
g(Z) = \inf_{X,Y} L(X,Y,Z) &= \inf_X f_1(X) - \langle Z, X \rangle + \inf_Y \lambda f_2(Y) - \langle Z, Y \rangle + \langle Z, C \rangle \\
    &= \langle Z, C \rangle - \sup_X \left( \langle Z, X \rangle - f_1(X) \right) - \sup_Y \left( \langle Z, Y \rangle - \lambda f_2(Y) \right) \\
    &= \langle Z, C \rangle - f_1^*(Z) - \lambda f_2^*(\lambda^{-1} Z)
\end{aligned}$$
where $f_1^*$ and $f_2^*$ are the convex conjugates of $f_1$ and $f_2$, respectively. I hope you'll take my word that they are
$$f_1^*(Z) = \begin{cases} 0 & \|Z\| \leq 1 \\ +\infty & \text{otherwise} \end{cases}
\qquad f_2^*(Z) = \begin{cases} 0 & \|Z\|_\infty \leq 1 \\ +\infty & \text{otherwise} \end{cases}$$
because this answer is already long enough :-) Note the involvement of the dual norms here: $\|\cdot\|$ is the maximum singular value of $Z$, and $\|\cdot\|_\infty$ returns the maximum of the absolute values of the elements of its input. Refer pages 93, 221-222 in Boyd and Vandenberghe for further understanding (courtesy: comment by mkuse).
Putting this together, we have the dual problem
$$\begin{array}{ll}
\text{maximize}_Z & \langle C, Z \rangle - f_1^*(Z) - \lambda f_2^*(\lambda^{-1} Z)
\end{array}$$
This is technically the correct dual. But since $f_1^*$ and $f_2^*$ are indicator functions we will typically convert them to constraints like this:
$$\begin{array}{ll}
\text{maximize}_Z & \langle C, Z \rangle \\
& \|Z\|\leq 1 \\
& \| Z \|_\infty \leq \lambda
\end{array}$$
And that's the dual you're most likely going to want to work with.
If you take the dual of this problem, you'll eventually recover a problem that is equivalent to the primal, but it won't be exactly the same. You'll need a bit of transformation to get back to the exact original form. After all, we just did a bit of transformation ourselves to clean up the dual.
