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