Analytical Solution to a simple l1 norm problem

Question

Can we solve this simple optimization problem analytically?

$ \min_{w}\dfrac{1}{2}\left(w-c\right)^{2}+\lambda\left|w\right| $

where c is a scalar and w is the scalar optimization variable.

Answer 1

Let $f(w) = \frac{1}{2}(c-w)^2+\lambda|w|$. Since $|\cdot|$ is not differentiable at $0$, some care must be taken when locating the minimizers. In particular, it is not necessarily the case that the minimizer of $f$ occurs at the minimizers of $w \mapsto \frac{1}{2}(c-w)^2 \pm \lambda w$ separately.

It is clear that $f(w) \uparrow \infty$ as $|w|\to \infty$, hence a minimizer exists.

If we take $c=1, \lambda = 2$ we see that the minimizer occurs at $w=0$, which is not a minimizer of the separate functions. It occurs because, under the appropriate circumstances (the slopes of the individual functions must be opposite in sign), we can have a minimizer when $\frac{1}{2}(c-w)^2+\lambda w = \frac{1}{2}(c-w)^2 -\lambda w$, which reduces to $w=0$.

More formally, we note that $f$ is locally Lipschitz, so we can compute the Clark generalized gradient at $w$ as $\partial f(w) = \begin{cases} \{w-c+ \lambda \operatorname{sgn} w, & w \neq 0 \\ \{-c\}+ [-|\lambda|, |\lambda|], & w = 0 \end{cases}$. At a minimum, we will have $0 \in \partial f(w)$.

If we take $w>0$, then $0 \in \partial f(w)$ implies $w =c-\lambda$ (which means we must have $c > \lambda$). Similarly, if $w<0$, we get $w =c+\lambda$ (which means we must have $c< -\lambda$).

If $w=0$, then $0 \in \partial f(0)$ implies $0 = -c + \xi$, where $|\xi| \le |\lambda|$, (which implies $|c| \le |\lambda|$).

For this it is clear that $\min_w f(w) = \min (f(c-\lambda), f(0), f(c+\lambda))$.

If $\lambda\ge 0$, then the above shows that $\min_w f(w) = \begin{cases} f(c-\lambda), & c > \lambda \\ f(0), & |c| \le |\lambda| \\ f(c+\lambda), & c < -\lambda \end{cases}$

Answer 2

Set $f(w)=\frac{1}{2}(w-c)^2+\lambda |w|$, equal to $\frac{1}{2}(w-c)^2\pm\lambda w$. We find $f'(w)=w-c\pm \lambda$. Setting this to zero gives $c\pm \lambda$ as the only critical values of $f$. As $w$ gets large, $f(w)$ grows without bound, so the minimum is going to be at one of the two critical values. At those values, we have $f(c+\lambda)=\frac{\lambda^2}{2}+\lambda|c+\lambda|$, and $f(c-\lambda)=\frac{\lambda^2}{2}+\lambda|c-\lambda|$. Which one is minimal depends on whether $c,\lambda$ are the same sign or different signs.

Also need to compare with $f(0)=\frac{c^2}{2}$, $f$ is nondifferentiable there.