Journal of Convex Analysis 14 (2007), No. 3, 657--666
Copyright Heldermann Verlag 2007
Parametric Computation of the Legendre-Fenchel Conjugate with Application to the Computation of the Moreau Envelope
Jean-Baptiste Hiriart-Urruty
Laboratoire de Mathématiques pour l'Industrie et la Physique, Institut de Mathématiques, Université Paul Sabatier, 118 Route de Narbonne, 31062 Toulouse, France
jbhu@cict.fr
Yves Lucet
Dept. of Computer Science, I. K. Barber School of Arts and Sciences, University of British Columbia, Okanagan -- 3333 University Way, Kelowna BC V1V 1V7, Canada
yves.lucet@ubc.ca
A new algorithm, named the Parametric Legendre Transform (PLT) algorithm, to compute the Legendre-Fenchel conjugate of a convex function of one variable is presented. It returns a parameterization of the graph of the conjugate except for some affine parts corresponding to nondifferentiable points of the function. The approach is extended to the computation of the Moreau envelope, resulting in a simple yet efficient algorithm.
Theoretical results, the description (and extension) of the algorithm, its approximation error and the convergence, as well as the comparison with known algorithms are included.
Keywords: Legendre-Fenchel transform, Fenchel conjugate, Moreau envelope, Moreau-Yosida regularization, fast algorithm, computational convex analysis.
MSC: 65Y20, 52A41, 90C25
[ Fulltext-pdf (116 KB)] for subscribers only.