Moreau envelope

Short description: Mathematical optimization function

The Moreau envelope (or the Moreau-Yosida regularization) $M_f$ of a proper lower semi-continuous convex function $f$ is a smoothed version of $f$. It was proposed by Jean-Jacques Moreau in 1965.

The Moreau envelope has important applications in mathematical optimization: minimizing over $M_f$ and minimizing over $f$ are equivalent problems in the sense that the sets of minimizers of $f$ and $M_f$ are the same. However, first-order optimization algorithms can be directly applied to $M_f$, since $f$ may be non-differentiable while $M_f$ is always continuously differentiable. Indeed, many proximal gradient methods can be interpreted as a gradient descent method over $M_f$.

Definition

The Moreau envelope of a proper lower semi-continuous convex function $f$ from a Hilbert space ${𝒳}$ to $(-\mathrm{\infty },+\mathrm{\infty }]$ is defined as

$M_f(v)=\underset{x\in {𝒳}}{\inf }(f(x)+\frac{1}{2}\Vert x-v{\Vert }_2^2).$

Given a parameter $\lambda \in \mathbb{ℝ}$, the Moreau envelope of $\lambda f$ is also called as the Moreau envelope of $f$ with parameter $\lambda$.

Properties

• The Moreau envelope can also be seen as the infimal convolution between $f$ and $(1/2)\Vert \cdot {\Vert }_2^2$.
• The proximal operator of a function is related to the gradient of the Moreau envelope by the following identity:

$\mathrm{\nabla }{M}_{\lambda f}(x)=\frac{1}{\lambda }(x-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}}_{\lambda f}(x))$. By defining the sequence $x_{k+1}={\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}}_{\lambda f}(x_k)$ and using the above identity, we can interpret the proximal operator as a gradient descent algorithm over the Moreau envelope.

• Using Fenchel's duality theorem, one can derive the following dual formulation of the Moreau envelope:

$$M_{\lambda f}(v)=\underset{p\in {𝒳}}{\max }(⟨p,v⟩-\frac{\lambda }{2}\Vert p{\Vert }^2-f^{*}(p)),$$ where $f^{*}$ denotes the convex conjugate of $f$. Since the subdifferential of a proper, convex, lower semicontinuous function on a Hilbert space is inverse to the subdifferential of its convex conjugate, we can conclude that if $p_0\in {𝒳}$ is the maximizer of the above expression, then $x_0:=v-\lambda p_0$ is the minimizer in the primal formulation and vice versa.

• By Hopf–Lax formula, the Moreau envelope is a viscosity solution to a Hamilton–Jacobi equation. Stanley Osher and co-authors used this property and Cole–Hopf transformation to derive an algorithm to compute approximations to the proximal operator of a function.

See also

• Proximal operator
• Proximal gradient method

External links

• Hazewinkel, Michiel, ed. (2001), "Moreau envelope function", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page 
• A Hamilton–Jacobi-based Proximal Operator: a YouTube video explaining an algorithm to approximate the proximal operator