Misplaced Pages

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

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

Definition

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

${\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 ${\displaystyle \lambda \in \mathbb {R} }$, the Moreau envelope of ${\displaystyle \lambda f}$ is also called as the Moreau envelope of ${\displaystyle f}$ with parameter ${\displaystyle \lambda }$.

Properties

• The Moreau envelope can also be seen as the infimal convolution between ${\displaystyle f}$ and ${\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:

${\displaystyle \nabla M_{\lambda f}(x)={\frac {1}{\lambda }}(x-\mathrm {prox} _{\lambda f}(x))}$. By defining the sequence ${\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:

$${\displaystyle M_{\lambda f}(v)=\max _{p\in {\mathcal {X}}}\left(\langle p,v\rangle -{\frac {\lambda }{2}}\|p\|^{2}-f^{*}(p)\right),}$$ where ${\displaystyle f^{*}}$ denotes the convex conjugate of ${\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 ${\displaystyle p_{0}\in {\mathcal {X}}}$ is the maximizer of the above expression, then ${\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. 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

References

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. ^ 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 .
4. Osher, Stanley; Heaton, Howard; Fung, Samy Wu (2022-11-23). "A Hamilton–Jacobi-based Proximal Operator". arXiv:2211.12997 .

External links

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

• Mathematical optimization