Infimum of $\max(0,y) + \frac{1}{2t}(x-y)^2$

Question

I want to compute the Moreau Envelope of the function $f(y) = \max(0,y)$. I know that the Moreau Envelope is given by:

$f_t(x) = \inf_y \{ f(y) + \frac{1}{2t}(x-y)^2 \ | y \in \mathbb{R} \}$

In our case this is:

$f_t(x) = \inf_y \{ \max(0,y) + \frac{1}{2t}(x-y)^2 | y \in \mathbb{R} \}$

Now everything left is computing the infimum. However, somehow I am messing up this step.

I thought about a case distinction with:

• $y < 0$
• $y > 0$
• $y = 0$

But this led to nowhere. Any help?

Answer 1

Guide:

Assuming $t>0$.

If $x\le 0$, the infimum is attained when $y=x$, then we have $$f_t(x)=0.$$

Now, we focus on the case where $x>0$,

If $y \le 0$, $\max(0,y)+\frac1{2t}(x-y)^2=\frac1{2t}(x-y)^2 \ge \frac{x^2}{2t}$

For $y\ge 0$, notice that it is a trade off between the the norm of $y$ and the approximation of $x$. If $y>x$, we could have find a better solution that is less than $x$ and have a smaller norm in $y$. To be explicit, the expression is evaluate to be $$y+\frac1{2t}(x-y)^2$$

which is a quadratic equation subject to the constraint that $y > 0$. Try to find the minimal of this problem.

Edit：

\begin{align}y + \frac1{2t}(x-y)^2 &=\frac1{2t}(x^2-2xy+y^2+2ty)\\ &=\frac1{2t}(y^2+2(t-x)y+x^2)\\ &=\frac1{2t}\left((y+(t-x))^2+x^2-(t-x)^2\right)\\ &=\frac1{2t}\left((y+(t-x))^2-t^2+2tx\right)\\ &=\frac1{2t}((y-(x-t))^2-\frac{t}2+x\end{align}

$\max(0,y)+\frac{1}{2t}(x-y)^2$ is a continuous function in $y$, when $x-t>0$, the minimal is attained there, and the minimal value is $x-\frac{t}2$. Otherwise, the minimal is attained when $y=0$ with value $\frac{x^2}{2t}.$

Answer 2

Below is my attempt:

---

Both summands in the expression $\, \max\left(0,y\right)+ \frac{1}{2t}(x-y)^2 $ are non-negative, thus the infimum is reached when both of them are minimized. The first term is obviously minimized by $y=0$, and the second is by $y=x$. Since you need the infimum expressed as function of $x$, you can compute derivative

$$ \frac{\partial}{\partial{y}}\left[\max\left(0,y\right)+ \frac{\left(x-y\right)^2}{2t} \right] = \frac{\partial}{\partial{y}}\left[\max\left(0,y\right) \right] + \frac{\partial}{\partial{y}}\left[\frac{\left(x-y\right)^2}{2t}\right] $$

$$ \max\left(0,y\right) = \cases{0,\quad y \le 0 \\y, \quad y>0 } \implies \frac{\partial}{\partial{y}}\left[\max\left(0,y\right) \right] = \cases{0,\quad y \le 0 \\1, \quad y>0 } $$

$$ \frac{\partial}{\partial{y}}\left[\frac{\left(x-y\right)^2}{2t}\right]=\frac{y-x}{t} $$

thus

$$ \frac{\partial}{\partial{y}}\left[\max\left(0,y\right)+ \frac{\left(x-y\right)^2}{2t} \right] =\cases{0+\left(y-x\right)/t,\quad y \le 0 \\1+\left(y-x\right)/t, \quad y>0 } $$

The first naive approach I want to try is to set derivatives to zero and compute extrema of $$ f_t\left(x\right) = \inf_y \left\lbrace \max\left(0,y\right) + \frac{\left(x-y\right)^2}{2t} \mid y \in \mathbb{R} \right\rbrace $$

as following:

$$ 0=\frac{\partial}{\partial{y}}\big[\max\left(0,y\right)+ \frac{\left(x-y\right)^2}{2t} \big] =\cases{0+\left(y-x\right)/t,\quad y \le 0 \\1+\left(y-x\right)/t, \quad y>0 } \implies \cases{y_0=x,&$y\le0$\\y_0=x-t,&$y>0$} $$

Thus we get

$$ f_t\left(x\right) = \inf_y \left\lbrace \max\left(0,y\right) + \frac{\left(x-y\right)^2}{2t} \mid y \in \mathbb{R} \right\rbrace {\stackrel{?}{=}} \left.\left(\max\left(0,y\right) + \frac{\left(x-y\right)^2}{2t} \right)\right\rvert_{y=y_0} $$

$$ f_t\left(x\right) = \cases{ 0, & $y\le0$ \\ \max\left(0,x-t\right) + \frac{t}{2} , & $y>0$} $$

Hope this helps.