Can you help me to find the dual of Dual form of $$ \min_{x,z} \frac{1}{2}\|y-x\|^2_2+\lambda\|z\|_1 \\ \text{subject to }Dx=z $$ My attempt has been to find the Lagrangian first: $$ L(x,z,\nu)=\frac{1}{2}\|y-x\|^2_2+\lambda\|z\|_1+\nu^T(Dx-z) $$ And now to find the dual we need to minimize $L(x,z,\nu)$ w.r.t. $x,z$. That is, take the derivative of the Lagrangian and equal to zero. But I can't find how to take derivatives of $L$. We can express $\|y-x\|^2_2$ as $(y-x)^T(y-x)$ but how to deal with $\|z\|_1$?
Your help will be kindly appreciated! Thank you for your time.
you can minimize the lagrangian first with repect to $z$, then with respect to $x$. you can find the minimun value with respect to z without the derivative, intuitively. you can write the lagrangian as $\frac{1}{2}||y-x||^2 + v^TDx + \lambda||z||_1-v^Tz$. to minimize with repect to $z$, you just need to find minimum of $\lambda||z||_1-v^Tz$. you can find that intuitively by using various cases. I did three cases. $\lambda = 0, \lambda> 0, \lambda< 0$. if $\lambda = 0$, $-v^Tz$ is affine, so its minimum is $0$ if $v = 0$ or $-\infty$ otherwise. if $\lambda > 0$, if $\lambda \succeq v$, the minimum possible value is $0$, otherwise it is $-\infty$. also, same condition when $\lambda > 0$. so, generally when $\lambda \succeq v$, the minimum is $0$. and it is $-\infty$ otherwise. after minimizing with respect to $z$ , you have to minimize $min \frac{1}{2}||y-x||^2 + v^TDx$ with respect to $x$ which can be easily done with the gradient as you said. then, after getting the final result, don't forget to write $\lambda \succeq v$ as the constraint for the dual problem. NOTE: I used $\lambda \succeq v$ to mean $\lambda$ is greater than every component of the vector $v$