Rewrite $\frac{1}{2}||x-u||_2^2$ subject to $||x||_1\le c$ to lagrangian form with multiplier $\lambda \ge 0$

Question

Rewrite $\frac{1}{2}||x-u||_2^2$ subject to $||x||_1\le c$ to lagrangian form with multiplier $\lambda \ge 0$

So I'm pretty new to converting constraint functions to Lagrangian form, but I read that you're supposed to rewrite the constraint in a way s.t. it equals 0 then add it to the objective. I don't know how you can write $||x||_1\le c$ in a equation equal to 0 s.t. it keeps this constraint allowing to be any number less than or equal to c.

Answer 1

Define

$$G(x) \triangleq \sup_{\mu \geqslant 0} \mu \cdot \left( \|x\|_1 - c \right).$$

Now, if $\| x \|_1 \leqslant c$, $G(x) = 0$; otherwise, $G(x) = \infty$. Hence

\begin{align} F(u, c) &= \inf_x \frac{1}{2} \| x - u \|_2^2 \quad \text{such that} \quad \| x \|_1 \leqslant c \\ &= \inf_x \sup_{\mu \geqslant 0} \left\{ \frac{1}{2} \| x - u \|_2^2 + \mu \cdot \left( \|x\|_1 - c \right) \right\}, \end{align}

which is a Lagrange-type saddle-point problem.