Faster than the fast Legendre transform, the linear-time Legendre transform. (English) Zbl 0909.65037

Lucet, Yves

Numer. Algorithms 16, No. 2, 171-185 (1997).

An algorithm is proposed for numerical computation of the Legendre-Fenchel transform \(u^*(s)= \sup_x[\langle s,x\rangle- u(x)]\) with a linear-time complexity in arbitrary space dimensions. A corresponding MATLAB package is described and illustrated with examples.

Reviewer: S.Zlobec (Montreal)

MSC:

65K05	Numerical mathematical programming methods
90C30	Nonlinear programming
52B55	Computational aspects related to convexity
65Y15	Packaged methods for numerical algorithms
90C25	Convex programming

Keywords:

Legendre-Fenchel transform; convex hull; linear-time complexity; MATLAB package

Software:

Matlab; na13