Moreau envelope

The Moreau envelope (or the Moreau-Yosida regularization)  M f {\displaystyle M_{f}} of a proper lower semi-continuous convex function f {\displaystyle f} is a smoothed version of  f {\displaystyle f} . It was proposed by Jean-Jacques Moreau in 1965.[1]

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

## Definition

[edit]

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

M λ f ( v ) = inf x ∈ X ( f ( x ) + 1 2 λ ‖ x − v ‖ 2 2 ) . {\displaystyle M_{\lambda f}(v)=\inf _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2\lambda }}\|x-v\|_{2}^{2}\right).}

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

## Properties

[edit]

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

∇ M λ f ( x ) = 1 λ ( x − p r o x λ f ( x ) ) {\displaystyle \nabla M_{\lambda f}(x)={\frac {1}{\lambda }}(x-\mathrm {prox} _{\lambda f}(x))} . By defining the sequence  x k + 1 = p r o x λ f ( x k ) {\displaystyle x_{k+1}=\mathrm {prox} _{\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 λ f ( v ) = max p ∈ X ( ⟨ p , v ⟩ − λ 2 ‖ p ‖ 2 − f ∗ ( p ) ) , {\displaystyle M_{\lambda f}(v)=\max _{p\in {\mathcal {X}}}\left(\langle p,v\rangle -{\frac {\lambda }{2}}\|p\|^{2}-f^{*}(p)\right),} where  f ∗ {\displaystyle f^{*}} denotes the convex conjugate of  f {\displaystyle 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 ∈ X {\displaystyle p_{0}\in {\mathcal {X}}} is the maximizer of the above expression, then  x 0 := v − λ p 0 {\displaystyle 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.[3] 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.[4]

## See also

[edit]

* Proximal operator
* Proximal gradient method

## References

[edit]

1. ^ Moreau, J. J. (1965). "Proximité et dualité dans un espace hilbertien". Bulletin de la Société Mathématique de France. 93: 273–299\. doi:10.24033/bsmf.1625. ISSN 0037-9484.
2. ^ a b Neal Parikh and Stephen Boyd (2013). "Proximal Algorithms" (PDF). Foundations and Trends in Optimization. 1 (3): 123–231. Retrieved 2019-01-29.
3. ^ Heaton, Howard; Fung, Samy Wu; Osher, Stanley (2022-10-09). "Global Solutions to Nonconvex Problems by Evolution of Hamilton–Jacobi PDEs". arXiv:2202.11014 [math.OC].
4. ^ Osher, Stanley; Heaton, Howard; Fung, Samy Wu (2023). "A Hamilton–Jacobi-based proximal operator". Proceedings of the National Academy of Sciences. 120 (14): e2220469120. arXiv:2211.12997. Bibcode:2023PNAS..12020469O. doi:10.1073/pnas.2220469120. PMC 10083605. PMID 36989305.

## External links

[edit]

* "Moreau envelope function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
* A Hamilton–Jacobi-based Proximal Operator: a YouTube video explaining an algorithm to approximate the proximal operator