zbMATH — the first resource for mathematics

A fast computational algorithm for the Legendre-Fenchel transform. (English) Zbl 0852.90117
Summary: We investigate a fast algorithm, introduced by Brenier, which computes the Legendre-Fenchel transform of a real-valued function. We generalize his work to boxed domains and introduce a parameter in order to build an iterative algorithm. The new approach of separating primal and dual spaces allows a clearer understanding of the algorithm and yields better numerical behavior. We extend known complexity results and give new ones about the convergence of the algorithm.

90C30 Nonlinear programming
49J52 Nonsmooth analysis
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI
[1] Y. Brenier Un algorithme rapide pour le calcul de transforme de Legendre-Fenchel discrtes C.R.Acad.Sci.Paris,t.308, Srie I,p587–589,1989
[2] B. Brighi and M. Chipot Approximated convex envelope of a function. Siam J.Num.Anal., Vol 31, N.1, pp128–148, 1994 · Zbl 0796.65009 · doi:10.1137/0731007
[3] L. Corrias Fast Legendre-Fenchel Transform and applications to Hamilton-Jacobi equation and conservation laws. Publication du laboratoire d’analyse numrique. Universit Pierre et Marie Curie, juim 1994
[4] R. Dautray and J.-L. Lions Analyse mathmatique et calcul numrique pour les sciences et les techniques. Masson 2 nd dition. Tome 3, p865–875, 1987
[5] J.-B. Hiriart-Urruty Lipschitz r-continuity of the approximate subdifferential of a convex function. Math. Scand. 47. p123–134, 1980 · Zbl 0426.26005
[6] J.-B. Hiriart-Urruty and C. Lemarchal Convex analysis and minimization algorithms. Springer-Verlag, 1993
[7] D.G. Luenberger Linear and Nonlinear Progamming. Addison-Wesley 2 nd edition, p189–193, 1984
[8] K.I.M. McKinnon, C.G. Millas and M. Mongeau Global optimization for the chemical and phase equilibrium problem using interval analysis. Technical report LAO95-02, January 1995
[9] V.P. Maslov On a new principle of superposition for optimization problems. Russian Math. Surveys 42:3,p43–54, 1987 · Zbl 0707.35138 · doi:10.1070/RM1987v042n03ABEH001439
[10] J.-P. Quadrat Thorme asymptotique en programmation dynamique. C.R.Acad.Sci.Paris,t. 311, Srie I,p745–748, 1990
[11] R.T. Rockafellar Convex Analysis. Princeton university Press, Princeton, New york, 1970
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.