Analytical Solution to a simple l1 norm problem 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.
 A: 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}$
A: 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.
