1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}

$\endgroup$

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.