Name

CCA — Computational Convex Analysis toolbox description

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)].
                 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):

                                     2
        M(s) = inf f(x) + || s - x ||.
                x
    

    The notation

    ||.||

    denotes the Euclidean norm. Several linear-time algorithms are implemented (functions with names me_*).

    pl_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
    

    where

    *

    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*):

                                                   n-2
        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.

See Also

Main functions:, pl_lft_llt , pl_lft_llt_2d , pl_me_llt , pl_me_llt_2d , pl_bb , Alternative algorithms:, pl_me_nep , pl_me_nep_2d , pl_me_pe , pl_me_pe_2d , Fitzpatrick/Rockafellar algorithms:, op_fitz , op_fitzinf , plq_fitzinf0 , plq_rock , Functions provided for comparison only:, pl_lft_direct , pl_lft_direct_2d , pl_me_direct , pl_me_direct_2d , pl_me_brute_2d , op_fitz_brute , op_fitz_direct , plq_fitzinf0_direct

Authors

Yves Lucet, University of British Columbia, BC, Canada

Contributors

Bibliography

  • H. H. Bauschke, Y. Lucet, and M. Trienis, 2008, How To Transform One Convex Function Continuously Into Another, 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.