Last update : 18/07/2008

CCA - Computational Convex Analysis toolbox description


The CCA package contains numerical algorithms to compute several fundamental transforms of convex analysis for convex and nonconvex functions. Most of its algorithms take a function as input, either as evaluated on a grid or given as a black box, and return the evaluation of the transform on a grid.

The transforms currently implemented are:

  • lft: The Legendre-Fenchel transform (also called Legendre-Fenchel conjugate, Fenchel conjugate, or convex conjugate):
        f*(s) = sup [ < s, x > - f(x)].
    The notation
    <., .>
    denotes the standard scalar product. Several linear-time algorithms are implemented (functions with names lft_*).
  • me: The Moreau envelope (also called Moreau-Yosida approximate):
        M(s) = inf f(x) + || s - x ||.
    The notation
    denotes the Euclidean norm. Several linear-time algorithms are implemented (functions with names me_*).
  • bb: The lower convex envelope (also called convex hull): It is the largest convex function minoring a given function. The implementation uses the Beneath-Beyond algorithm to achieve a linear-time worst-case complexity when the points are sorted along the x-axis. It is used by some fast transform algorithms.
  • pa: The proximal average transforms one convex function into another continuously:
        P(f0,lambda,f1) = [ (1-lambda)(f0 + ||.||^2/2)* + lambda(f1 + ||.||^2/2)* ]* - ||.||^2/2
    is the Fenchel conjugate above. This transform works even if the functions have only partially overlapping or completely disjoint domains. This algorithm, part of the PLQ framework, runs in O(N(f1) + N(f2)) time, where N(f) is the number of pieces in the PLQ function f.
  • fitz: The Fitzpatrick function of a finite operator A defined on the real line (functions with names op_fitz* and plq_fitz*):
        F[A,n](x,xstar) =         sup              sum [ <a(i+1)-a(i),astar(i)> ] + <x-a(n-1),astar(n-1)> + <a(1),xstar>
                          (a(1),astar(1)) in A     i=1
                       (a(n-1), astar(n-1)) in A
    The most efficient general algorithm implemented runs in worst-case cubic time. Other algorithms with fixed parameters are implemented that further reduce the time complexity.
  • rock: The Rockafellar function of a real, finite operator A:
        R(A, a(k))(x) = { (x-a(i))*bm(i) + sum(j=i+1:k, (a(j-1)-a(j))*bm(j)) , if a(i-1) < x <= a(i) <= a(k)
                        { (x-a(i))*bp(i) + sum(j=k:i-1, (a(j+1)-a(j))*bp(j)) , if a(k) <= a(i) <= x <= a(i+1)
    This algorithm uses PLQ functions to achieve a worst-case linear time complexity.
  • Unit tests are available in the tests/ directory to test that the package is rightly setup and to provide additional examples. To run all unit tests use (in the directory the package was unpacked) exec tests/test.sci;

    See Also

    Main functions:,  lft_llt,  lft_llt2d,  me_llt,  me_llt2d,  bb,  Alternative algorithms:,  me_nep,  me_nep2d,  me_pe,  me_pe2d,  Fitzpatrick/Rockafellar algorithms:,  op_fitz,  op_fitzinf,  plq_fitzinf0,  plq_rock,  Functions provided for comparison only:,  lft_direct,  lft_direct2d,  me_direct,  me_direct2d,  me_brute2d,  op_fitz_brute,  op_fitz_direct,  plq_fitzinf0_direct,  


    Yves Lucet, University of British Columbia, BC, Canada


  • Yves Lucet (PI, 1996-)
  • Bryan Gardiner (Research Assistant 2008-)
  • Scott Fazackerley (USRA 2007, Honours student 2007-08)
  • Michael Trienis (M.Sc. student 2006-2007)
  • Jeff Dicker (USRA student 2005)
  • Andrew Tonner (Research Assistant 2005)
  • Bibliography

  • Y. Lucet, 200Y, Numerical Computation of Fitzpatrick Functions.
  • H. H. Bauschke, Y. Lucet, and M. Trienis, 2008, How To Transform One Convex Function Continuously Into Another, SIAM Review, 50(1):115-132.
  • Y. Lucet, H. H. Bauschke, and M. Trienis, 2007, The Piecewise Linear-Quadratic Model for Computational Convex Analysis, Computational Optimization and Applications.
  • Y. Lucet, 2006, Fast Moreau Envelope Computation I: Numerical Algorithms, Numerical Algorithms, 43(3):235-249
  • Y. Lucet, 2005, A linear Euclidean distance transform algorithm based on the Linear-time Legendre Transform, Proceedings of the Second Canadian Conference on Computer and Robot Vision (CRV 2005), IEEE Computer Society Press, 2005.
  • Y. Lucet, 1997, Faster than the fast Legendre transform, the linear-time Legendre transform, Numerical Algorithms, 16(2):171-185. Code in Netlib.
  • Y. Lucet, 1996, A fast computational algorithm for the Legendre-Fenchel transform, Computational Optimization and Applications, 6(1):27-57.