Documentation
Last update : 18/07/2008
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 LegendreFenchel transform (also called LegendreFenchel conjugate, Fenchel conjugate, or convex conjugate):
f*(s) = sup [ < s, x >  f(x)].
x
The notation <., .>
denotes the standard scalar product. Several lineartime algorithms are implemented (functions with names lft_*).

me: The Moreau envelope (also called MoreauYosida approximate):
2
M(s) = inf f(x) +  s  x .
x
The notation .
denotes the Euclidean norm. Several lineartime 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 BeneathBeyond algorithm to achieve a lineartime worstcase complexity when the points are sorted along the xaxis. It is used by some fast transform algorithms.

pa: The proximal average transforms one convex function into another continuously:
P(f0,lambda,f1) = [ (1lambda)(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*):
n2
F[A,n](x,xstar) = sup sum [ <a(i+1)a(i),astar(i)> ] + <xa(n1),astar(n1)> + <a(1),xstar>
(a(1),astar(1)) in A i=1
...
(a(n1), astar(n1)) in A
The most efficient general algorithm implemented runs in worstcase 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) = { (xa(i))*bm(i) + sum(j=i+1:k, (a(j1)a(j))*bm(j)) , if a(i1) < x <= a(i) <= a(k)
{ (xa(i))*bp(i) + sum(j=k:i1, (a(j+1)a(j))*bp(j)) , if a(k) <= a(i) <= x <= a(i+1)
This algorithm uses PLQ functions to achieve a worstcase 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,
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 200708)

Michael Trienis (M.Sc. student 20062007)

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):115132.
Y. Lucet, H. H. Bauschke, and M. Trienis, 2007, The Piecewise LinearQuadratic Model for Computational Convex Analysis, Computational Optimization and Applications.
Y. Lucet, 2006, Fast Moreau Envelope Computation I: Numerical Algorithms, Numerical Algorithms, 43(3):235249
Y. Lucet, 2005, A linear Euclidean distance transform algorithm based on the Lineartime 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 lineartime Legendre transform, Numerical Algorithms, 16(2):171185. Code in Netlib.
Y. Lucet, 1996, A fast computational algorithm for the LegendreFenchel transform, Computational Optimization and Applications, 6(1):2757.