Dual of this primal optimization problem?

Question

How would one find the dual of the following problem?

$min_x 1/2 ||y-x||_2^2 + \lambda||x||_1 $

Can someone please explain to me how to do this since there are no specific constraints?

Answer 1

You could reformulate your problem as \begin{align*} \operatorname*{minimize}_{x,u} &\quad \frac12 \|u\|_2^2 + \lambda \|x\|_1 \\ \text{subject to} &\quad u = y - x. \end{align*}

The Lagrangian is \begin{align*} L(x,u,z) &= \frac12 \|u\|_2^2 + \lambda \|x\|_1 + \langle z,y-x - u \rangle \\ &= \frac12 \|u\|_2^2 - \langle z,u \rangle + \lambda \|x\|_1 - \langle z,x \rangle + \langle z,y\rangle. \end{align*} The dual function is \begin{align*} g(z) &= \begin{cases} -\frac12 \| z \|_2^2 + \langle z,y \rangle \quad \text{if } \|z\|_{\infty} \leq \lambda \\ -\infty \quad \text{otherwise}. \end{cases} \end{align*}

The dual problem is \begin{align*} \operatorname*{maximize}_z & \quad -\frac12 \| z \|_2^2 + \langle z,y \rangle \\ \text{subject to} &\quad \|z\|_{\infty} \leq \lambda. \end{align*}