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_*).

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:,  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,  

Author

Yves Lucet, University of British Columbia, BC, Canada

Contributors

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