Proof of the Moreau Envelope of $l_1$ norm Given function $| \cdot | : \mathbb{R} \rightarrow \mathbb{R}_{+}$ and $\alpha > 0$, its Moreau envelope $e_{\alpha}|\cdot|: \mathbb{R} \rightarrow \mathbb{R}_{+}$, reads:
\begin{equation}
e_{\alpha}|\cdot|\left(x\right) = \inf_{y \in \mathbb{R}}{\bigg\{|y| + \frac{1}{2\alpha} | x - y|^2\bigg\}}
\end{equation}
How would you formally prove that the Moreau Envelope is given by?
\begin{equation}
e_{\alpha}|\cdot|\left(x\right) = 
\begin{cases} \frac{1}{2\alpha}x^2 & |x| \leq \alpha \\ |x| - \frac{\alpha}{2} & |x| > \alpha \end{cases}
\end{equation}
 A: Suppose $y\ge 0$. Observe that
\begin{align}
|y|+\frac{1}{2\alpha}|x-y|^2 =&\ \frac{x^2+y^2}{2\alpha}+\frac{xy}{\alpha}+y = \frac{x^2-(x+\alpha)^2}{2\alpha} + \frac{1}{2\alpha}\left(y^2+2(x+\alpha)y+(x+a)^2 \right)\\
=&\ \frac{x^2-(x+\alpha)^2}{2\alpha} +\frac{(y+x+\alpha)^2}{2\alpha}.
\end{align}
If $x+\alpha>0$, then the minimum occurs when $y = 0$, i.e.
\begin{align}
\frac{x^2-(x+\alpha)^2}{2\alpha} +\frac{(y+x+\alpha)^2}{2\alpha} \ge \frac{x^2}{2\alpha}.
\end{align}
When $x+\alpha<0$ (i.e. $-x>\alpha>0$), then the minimum occurs when $y = -(x+\alpha)$ which means
\begin{align}
\frac{x^2-(x+\alpha)^2}{2\alpha} +\frac{(y+x+\alpha)^2}{2\alpha} \ge \frac{x^2-(x+\alpha)^2}{2\alpha} = -x-\frac{\alpha}{2}=|x|-\frac{\alpha}{2}. 
\end{align}
For $y<0$. Observe that
\begin{align}
|y|+\frac{1}{2\alpha}|x-y|^2 =&\ \frac{x^2+y^2}{2\alpha}+\frac{xy}{\alpha}-y = \frac{x^2-(x-\alpha)^2}{2\alpha} + \frac{1}{2\alpha}\left(y^2+2(x-\alpha)y+(x-\alpha)^2 \right)\\
=&\ \frac{x^2-(x-\alpha)^2}{2\alpha} +\frac{(y+x-\alpha)^2}{2\alpha}.
\end{align}
I will leave you to complete the argument.
