×

zbMATH — the first resource for mathematics

Faster than the fast Legendre transform, the linear-time Legendre transform. (English) Zbl 0909.65037
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.

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
52B55 Computational aspects related to convexity
65Y15 Packaged methods for numerical algorithms
90C25 Convex programming
Software:
Matlab; na13
PDF BibTeX XML Cite
Full Text: DOI