Skip to main content
SpringerLink
Log in

A fast computational algorithm for the Legendre-Fenchel transform

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  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

    Google Scholar 

  2. B. Brighi and M. Chipot Approximated convex envelope of a function. Siam J.Num.Anal., Vol 31, N.1, pp128–148, 1994

    Google Scholar 

  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 2nd 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

    Google Scholar 

  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 2nd 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

    Google Scholar 

  10. J.-P. Quadrat Thorme asymptotique en programmation dynamique. C.R.Acad.Sci.Paris,t. 311, Srie I,p745–748, 1990

    Google Scholar 

  11. R.T. Rockafellar Convex Analysis. Princeton university Press, Princeton, New york, 1970

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire Approximation et Optimisation, UFR MIG, Université Paul Sabatier, 118 Route de Narbonne, 31062, Toulouse Cedex, France

    Y. Lucet

Authors
  1. Y. Lucet
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lucet, Y. A fast computational algorithm for the Legendre-Fenchel transform. Comput Optim Applic 6, 27–57 (1996). https://doi.org/10.1007/BF00248008

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00248008

Keywords

Search

Navigation