Fast Moreau Envelope Computation I: Numerical Algorithms

Yves Lucet (yves.lucetubc.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

Download:

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

Modify/Update this entry