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 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.
• 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 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.