Optimization Online


Fast Moreau Envelope Computation I: Numerical Algorithms

Yves Lucet (yves.lucet***at***ubc.ca)

Abstract: The present article summarizes the state of the art algorithms to compute the discrete Moreau envelope, and presents a new linear-time algorithm, named NEP for NonExpansive Proximal mapping. Numerical comparisons between the NEP and two existing algorithms: The Linear-time Legendre Transform (LLT) and the Parabolic Envelope (PE) algorithms are performed. Worst-case time complexity, convergence results, and examples are included. The fast Moreau envelope algorithms first factor the Moreau envelope as several one-dimensional transforms and then reduce the brute force quadratic worst-case time complexity to linear time by using either the equivalence with Fast Legendre Transform algorithms, the computation of a lower envelope of parabolas, or, in the convex case, the non expansiveness of the proximal mapping.

Keywords: Moreau-Yosida approximate, Legendre-Fenchel transform, Conjugate, Discrete Legendre Transform, Envelope of Functions, Numerical Algorithm, Linear-time worst-case complexity

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Optimization Software and Modeling Systems (Problem Solving Environments )

Citation: Published: http://dx.doi.org/10.1007/s11075-006-9056-0


Entry Submitted: 10/05/2005
Entry Accepted: 10/06/2005
Entry Last Modified: 01/08/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society