What Is a Simple and Explicit Dual of $ h \left( x \right) = {\left\| x - d \right\|}_{2}^{2} + \sum_{i = 1}^{4} {\left\| {A}_{i} X \right\|}_{2} $ What is a simple and explicit dual of $h(x) =||x-d||_2^2 +\Sigma^{4}_{i=1}||A_iX||_2$
Where $A_i\in \mathbb{R}^{5x5}$ matrices.
Since the primal has no constraints I have tried to come up with the following two constraints and derive the dual:
1) $y=x-d$  
$inf_{x,y}||y||_2^2 + \Sigma^{4}_{i=1}||A_iX||_2 + \lambda(y-x+d)$
2) $y_i= A_ix$ 
$inf_{x,y}||x-d||_2^2 + \Sigma^{4}_{i=1}||y_i||_2 + \Sigma^{4}_{i=1}\lambda_i(y_i-A_ix)$
In both situations I am stuck and not sure how to continue.
 A: Here's how I'd rewrite it:
\begin{array}{ll}
\text{minimize}   & \|x-d\|_2^2 + \sum_i t_i \\
\text{subject to} & \|A_ix\|_2 \leq t_i, ~ i=1,2,3,4 
\end{array}
Alternatively, 
\begin{array}{ll}
\text{minimize}   & \|x-d\|_2^2 + \sum_i t_i \\
\text{subject to} & (A_ix,t_i) \in \mathcal{K}_2, ~ i=1,2,3,4 
\end{array}
Where $\mathcal{K}_2$ is the second-order cone of appropriate size. The Lagrangian is
$$L(x,y_1,z_1,y_2,z_2,y_3,z_3,y_4,z_4) = \|x-d\|_2^2 + \sum_i t_i - \sum_i \langle (y_i,z_i), (A_ix,t_i) \rangle = \|x-d\|_2^2 + \sum_i t_i(1-z_i) - \langle x, \sum_i A_i^T y_i \rangle$$
Where each Lagrange multiplier $(y_i,z_i)$ must also lie in $\mathcal{K}_2$; that is, $\|y_i\|_2\leq z_i$. The dual function, therefore, is
$$g(y_1,z_1,y_2,z_2,y_3,z_3,y_4,z_4)=\inf_{x,t_1,t_2,t_3,t_4} L(x,y_1,z_1,y_2,z_2,y_3,z_3,y_4,z_4)$$
The optimality conditions are
$$2(x-d) = \sum_i A_i^T y_i, \quad z_1=z_2=z_3=z_4=1$$
The $t,z$ terms are all zero, leaving us with the terms involving $x$. We're supposed to eliminate $x$, but I'm going to start by eliminating the $y_i$ sum, simplifying, and then putting it back in:
\begin{aligned}
g(\dots) &= \|x-d\|_2^2 - \langle x, 2(x-d) \rangle \\
               &= x^Tx - 2d^T x + d^T d - 2x^Tx + 2d^Tx \\
               &= \|d\|_2^2 -\|x\|_2^2 = \|d\|-2^2 - \tfrac{1}{4} \|\sum_i A_i^T y_i  + 2d \|_2^2
\end{aligned}
How convenient! ;-) So the dual is
\begin{array}{ll}
\text{maximize} &\|d\|_2^2 - \tfrac{1}{4} \|\sum_i A_i^T y_i  + 2d \|_2^2 \\
\text{subject to} & \|y_i\|_2 \leq z_i, ~ i=1,2,3,4 \\
                             & z_1=z_2=z_3=z_4=1
\end{array}
or, eliminating the $z_i$ variables,
\begin{array}{ll}
\text{maximize} &\|d\|_2^2 - \tfrac{1}{4} \|\sum_i A_i^T y_i  + 2d \|_2^2 \\
\text{subject to} & \|y_i\|_2 \leq 1, ~ i=1,2,3,4
\end{array}
