Moreau envelope

The Moreau envelope (or the Moreau-Yosida regularization) [math]\displaystyle{ M_f }[/math] of a proper lower semi-continuous convex function [math]\displaystyle{ f }[/math] is a smoothed version of [math]\displaystyle{ f }[/math]. It was proposed by Jean-Jacques Moreau in 1965. The Moreau envelope has important applications in mathematical optimization: minimizing over [math]\displaystyle{ M_f }[/math] and minimizing over [math]\displaystyle{ f }[/math] are equivalent problems in the sense that set of minimizers of [math]\displaystyle{ f }[/math] and [math]\displaystyle{ M_f }[/math] are the same. However, first-order optimization algorithms can be directly applied to [math]\displaystyle{ M_f }[/math], since [math]\displaystyle{ f }[/math] may be non-differentiable while [math]\displaystyle{ M_f }[/math] is always continuously differentiable. Indeed, many proximal gradient methods can be interpreted as a gradient descent method over [math]\displaystyle{ M_f }[/math].

Definition

The Moreau envelope of a proper lower semi-continuous convex function [math]\displaystyle{ f }[/math] from a Hilbert space [math]\displaystyle{ \mathcal{X} }[/math] to [math]\displaystyle{ (-\infty,+\infty] }[/math] is defined as

[math]\displaystyle{ M_{\lambda f}(v) = \inf_{x\in\mathcal{X}} \left(f(x) + \frac{1}{2\lambda} \|x - v\|_2^2\right). }[/math]

Given a parameter [math]\displaystyle{ \lambda \in \mathbb{R} }[/math], the Moreau envelope of [math]\displaystyle{ \lambda f }[/math] is also called as the Moreau envelope of [math]\displaystyle{ f }[/math] with parameter [math]\displaystyle{ \lambda }[/math].

Properties

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

[math]\displaystyle{ \nabla M_{\lambda f}(x) = \frac{1}{\lambda} (x - \mathrm{prox}_{\lambda f}(x)) }[/math]. By defining the sequence [math]\displaystyle{ x_{k+1} = \mathrm{prox}_{\lambda f}(x_k) }[/math] 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:

[math]\displaystyle{ M_{\lambda f}(v) = \max_{p \in \mathcal X} \left( \langle p, v \rangle - \frac{\lambda}{2} \| p \|^2 - f^*(p)\right), }[/math] where [math]\displaystyle{ f^* }[/math] denotes the convex conjugate of [math]\displaystyle{ f }[/math]. 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 [math]\displaystyle{ p_0 \in \mathcal X }[/math] is the maximizer of the above expression, then [math]\displaystyle{ x_0 := v - \lambda p_0 }[/math] 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