CCA — Computational Convex Analysis toolbox 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:
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_*).
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_*).
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.
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.
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.
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.