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.

  where   denotes the convex conjugate of  . 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   is the maximizer of the above expression, then   is the minimizer in the primal formulation and vice versa.

See also

edit

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 (2022-11-23). "A Hamilton–Jacobi-based Proximal Operator". arXiv:2211.12997 [math.OC].
edit