5
$\begingroup$

I would like some help in deriving the Lagrangian dual function of a sum-of-norms minimization problem :

$\sum{||A_{i}x-b_{i}||}$ when $A_{i}$ are matrices, and $b_{i},x$ vectors.

I understand I can rewrite the problem as a minimization on (x,y) and define the new target function as :

$\sum{||y_{i}||}$ under constraints stating that $y_{i}=A_{i}x-b{i}$ (when $y_{i}$ are vectors of course). So these are in fact linear constraints, right?

But what now? Can I use the conjugate of the L2 norm function in order to derive the Lagrangian dual function? Or can I derive it directly? ( I prefer to see a direct derivation by calculating the min of the Lagrangian on x with a fixed multiplier.).

Thank you!

$\endgroup$
1
  • $\begingroup$ Anyone ha an Idea? $\endgroup$ – Curious Jan 3 '14 at 19:12
1
$\begingroup$

After introducing the linear constraints, you just form the Lagrangian and minimize it: $$\mathcal{L}(x,y_i,\lambda_i)=\sum_i \|y_i\|+\lambda_i^T(y_i - A_i x+b_i)$$

$$\inf_{x, y_i} \mathcal{L}(x,y_i,\lambda_i) =\begin{cases} -\infty & \text{ if } \sum_i A_i^T\lambda_i \ne 0 \ \text{ or } \ \|\lambda_i\| > 1 \\ \sum_i b_i^T \lambda_i & \text{ otherwise } \end{cases} $$ So the dual problem is: $$ \begin{gathered}\max_{\lambda_i} \sum_i b_i^T \lambda_i\\ \text{s.t.}: \sum_i A_i^T\lambda_i = 0, \\ \quad\|\lambda_i\| \le 1, \ \forall \ i. \end{gathered} $$

$\endgroup$
1
  • $\begingroup$ would you explain me how $\lambda^T b$ become $b^T \lambda$? would you use inner product or any other formula? $\endgroup$ – Humayoo Dec 17 '16 at 13:41

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.