Moreau envelope
The Moreau envelope (or the Moreau-Yosida regularization) of a proper lower semi-continuous convex function is a smoothed version of . It was proposed by Jean-Jacques Moreau in 1965.[1]
The Moreau envelope has important applications in mathematical optimization: minimizing over and minimizing over are equivalent problems in the sense that the sets of minimizers of and are the same. However, first-order optimization algorithms can be directly applied to , since may be non-differentiable while is always continuously differentiable. Indeed, many proximal gradient methods can be interpreted as a gradient descent method over .
Definition[edit]
The Moreau envelope of a proper lower semi-continuous convex function from a Hilbert space to is defined as[2]
Given a parameter , the Moreau envelope of is also called as the Moreau envelope of with parameter .[2]
Properties[edit]
- The Moreau envelope can also be seen as the infimal convolution between and .
- The proximal operator of a function is related to the gradient of the Moreau envelope by the following identity:
. By defining the sequence 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:
- 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]
References[edit]
- ^ 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.
- ^ a b Neal Parikh and Stephen Boyd (2013). "Proximal Algorithms" (PDF). Foundations and Trends in Optimization. 1 (3): 123–231. Retrieved 2019-01-29.
- ^ 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].
- ^ Osher, Stanley; Heaton, Howard; Fung, Samy Wu (2022-11-23). "A Hamilton–Jacobi-based Proximal Operator". arXiv:2211.12997 [math.OC].
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