A fast computational algorithm for the Legendre–Fenchel transform

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.