<< miscellaneous | miscellaneous | common_version >>

CCA (Computational Convex Analysis) >> miscellaneous > CCA

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

Many exact transforms work with piecewise linear-quadratic functions and their subdifferentials, and visualizing these models is easy. See the main pages for PLQ functions and their subdifferentials.

The transforms currently implemented are:

- lft

    The `Legendre-Fenchel transform` (also called Legendre-Fenchel conjugate, Fenchel conjugate, or convex conjugate):

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

    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:

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

    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:

    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

- 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

- B. Gardiner, Y. Lucet, Submitted February 2010, Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis.
- B. Gardiner, Y. Lucet, Submitted January 2010, Graph-Matrix Calculus for Computational Convex Analysis.
- B. Gardiner, Y. Lucet, 2009, Numerical Computation of Fitzpatrick Functions, Journal of Convex Analysis, 16(4).
- H. H. Bauschke, Y. Lucet, and M. Trienis, 2008, How To Transform One Convex Function Continuously Into Another, 50(1):115-132.
- F. P. Preparata and M. I. Shamos, Computational Geometry An Introduction, Series: Monographs in Computer Science, 1st ed. 1985. Corr. 5th printing 1993.
- 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.
- W. L. Hare, 2009, The Proximal Average of Nonconvex Functions: A Proximal Stability Perspective, SIAM Journal on Optimization, 20(2), pp.650-666.

<< miscellaneous | miscellaneous | common_version >>