CCA numerical library for Computational Convex Analysis
    Copyright (C) 2008-2012, Yves Lucet

This toolbox implements functions for convex operations.


Here are the main files provided by the package. 

======
<PATH>
======

loader.sce    Scilab script to load demos, library, and
              help files.

builder.sce   Scilab script to compile the library and
              the online help system.
README.txt    The present file

lft_version.sci
        Discrete Legendre transform functions and 
        internal functions. It contains all the
        functions to compute the discrete Legendre
        transform and associated functions. The main
        function is pl_lft_llt. One may want to use the
        pl_bb function to compute the lower convex
        envelope of a set of points in the plane
        using the Beneath-Beyond algorithm.  The
        function pl_lft_direct is provided for
        comparison only.  The remaining functions
        (pl_lft_direct_d, _pl_fusion, _pl_fusionsci) are
        internal and should not be called directly.

me_version.sci
        Discrete Moreau envelope functions. The main 
        functions are pl_me_llt and pl_me_pe for nonconvex
        univariate functions, pl_me_nep for convex
        univariate functions. For bivariate
        functions, use pl_me_llt_2d and pl_me_pe_2d for
        nonconvex data, and pl_me_nep_2d for convex
        data. The functions pl_me_brute_2d, pl_me_direct,
        pl_me_direct_2d are provided for comparison
        only.  The function pl_me_pe2d_d is an internal
        function and should not be used directly.

plq_version.sci
        Operations on Piecewise Linear-Quadratic
        functions, which are represented as matrices.
        Algorithms are included to perform PLQ
        addition, scalar multiplication, evaluation,
        minimization and maximization, projection, and
        inf-convolution and deconvolution, as well as
        compute Fenchel conjugates, Moreau envelopes,
        convex hulls, proximal averages, and Rockafellar
        functions, and restricted Fitzpatrick functions.
        A PLQ approximation of an arbitrary convex
        function can be built.  There are functions to
        plot PLQ functions and their averages.  See help
        plq_function for the complete list of functions.

op_version.sci
        Operator functions.  There are a number of
        algorithms to evaluate Fitzpatrick functions
        of an operator on a grid.  The main functions
        are op_fitz and op_fitzinf, for computing
        Fitzpatrick functions of a specified, and
        infinite order, respectively.  op_fitz_brute
        and op_fitz_direct are provided for comparison
        to op_fitz.

For more details on the Scilab functions defined in the 
main toolbox files, refer to the Scilab online help 
(item CCA toolbox).

============================
Unit Tests: in <PATH>/tests/
============================

test.sci  Scilab script that runs all unit tests in 
          the current folder (files test_*.sci) and
          record the results in test.log

test_*.sci  Unit test files that validate the algorithms
            and provide numerous examples of their
            use. Test files included are:
        test_pl_bb.sci: Unit tests and examples for the
            pl_bb function.
        test_common.sci: Unit tests for the functions
            in common.sci.
        test_fenchel.sci: General unit tests for
            1D and 2D Legendre-Fenchel conjugates.
        test_pl_fusion.sci: Unit tests for the internal 
            functions _pl_fusion and _pl_fusionsci.
        test_ll.sci: Unit tests for the Lasry-Lions
            double envelope algorithms.
        test_llt.sci: Unit tests and examples for 
            the functions pl_lft_llt, pl_lft_llt_d,
            pl_lft_direct, and pl_lft_direct_d.
        test_moreau.sci: General unit tests for
            Moreau envelope functions.
        test_pl_me_llt.sci: Unit tests and examples for
            the functions pl_me_llt, pl_me_llt_2d,
            pl_me_direct, and pl_me_direct_2d:
            computation of the discrete Moreau
            envelope using the LLT algorithm.
        test_pl_me_nep.sci: Unit tests and examples for
            the functions pl_me_nep, pl_me_nep_2d, and
            pl_me_direct: computation of the
            discrete Moreau envelope using the
            NEP algorithm.
        test_pl_me_pe.sci: Unit tests and examples for 
            the functions pl_me_pe, pl_me_pe_2d:
            computation of the discrete Moreau
            envelope using the PE algorithm.
        test_plq_*.sci: Unit tests and examples for
            the PLQ functions provided in plq.sci.
        test_plt.sci: Tests the Parametric Moreau
            Envelope algorithm pl_me_plt, which uses
            the Parametric Legendre Transform.
        test_rock.sci: Unit tests for the computation
            of Rockafellar functions.
        

                Each of the unit test files can be called 
                independently by giving the command 
                  exec "<PATH>/tests/name_of_test.sci"; 
                or
                  exec (CCADIR+'/tests/name_of_test.sci');
                Then calling:
                  runTestFile()
                will return a true if the tests succeeded,
                false otherwise.

test_CCA.log  Results of the tests you should obtain.
              


=======================
Demos: in <PATH>/demos/
=======================

demo.sci     Scilab script calling all the demonstration 
             files and displaying the corresponding graphs.
demo_pa.sce  Scilab script calling the Proximal Average demos.

Here is the detail of the demos provided in the Demos menu.
Alternatively the CCA demo menu can be launched directly by
running the command 
    exec "<PATH>/demos/demo.sci";
or
    exec (CCADIR+'/demos/demo.sci'); 

Each of the following demo file can also be called 
independently by giving the command 
    exec "<PATH>/demos/name_of_demo.sci"; 
or
    exec (CCADIR+'/demos/name_of_demo.sci'); 

1. time_me.sci
Compare 4 algorithms to compute the Moreau envelope. Each
algorithm is timed on the computation of the Moreau envelope
of the function f(x)=x^2 on the grid N={1,2,3,...,n} for
increasing values of n=100, 200, 300, ..., 3000. The 4
algorithms compared are LLT, PE, NEP, and direct.The results
show that the NEP algorithm is the fastest but requires
additional structure like convexity, followed by the llt
algorithm, the PE algorithm, and the direct algorithm. (The
later is provided for comparison only.)
Functions demoed: pl_me_llt, me_pe_d, pl_me_nep, pl_me_direct

2. abs.sci
Computes the Moreau envelope and the proximal mapping of the
absolute value function on the interval [-1,1]. It
illustrates the smoothing property of the Moreau envelope at
the origin.
Function demoed: pl_me_direct

3. sqr.sci
Computes the Moreau envelope and the proximal mapping of the
smooth convex function f(x)=x^2 on the interval
[-15,15]. The resulting envelope approximates the function
from below, and its proximal mapping is clearly monotone.
Function demoed: pl_me_direct

4. nonconvexabs.sci
Computes the Moreau envelope of the nonsmooth nonconvex
function f(x)=||x|-1| on the interval [-2.5,2.5]. The Moreau
envelope does not smooth kinks arising from local maxima,
only those arising from minima.  The proximal mapping is
monotone with a jump at the origin as it is a
nondifferentiable point.
Function demoed: pl_me_direct

5. nonconvexsqr.sci
Computes the Moreau envelope and the proximal mapping of the
smooth nonconvex function f(x)=(x^2-1)^2 on the interval
[-1.5,1.5]. The Moreau envelope introduces a kink at the
origin (local maximum).  The proximal mapping is monotone
with a jump at the origin as it is a nondifferentiable point
of the Moreau envelope.
Function demoed: pl_me_direct

6.pl_bb.sci
Computes the lower convex envelope of the smooth nonconvex
function f(x)=(x^2-1)^2 on the interval [-2,2]. The envelope
retains the vertices on the convex hull and discards the
vertices in the open interval ]-1,1[ corresponding to the
concave part of f.
Function demoed: pl_bb

7. pl_lft_direct.sci
Illustrate the convergence of the Legendre-Fenchel conjugate
of the absolute value function when the size of the
intervals is increased.  The conjugate is computed on
intervals [-2,2], [-4,4], [-8,8], and [-160,160]. It is
converging to the indicator function of the interval [-1,1]
Function demoed: pl_lft_direct

8. time_lft.sci
Compare 3 algorithms to compute the Legendre-Fenchel
conjugate.  Each algorithm is timed on the computation of
conjugate of the absolute value function on the grid
N={1,2,3,...,n} for increasing values of n=100, 300, 500,
..., 4000. The 3 algorithms compared are pl_lft_direct, pl_lft_llt
using _pl_fusion, and pl_lft_llt using _pl_fusionsci. For the values of
n considered, the llt algorithm with the option _pl_fusionsci is
the fastest mostly due to its compiled instructions. The llt
algorithm with the _pl_fusion option comes next although it has
a better complexity since it uses Scilab interpreted
commands.
Functions demoed: pl_lft_direct, pl_lft_llt

9. llnonconvexabs.sci
Illustrates the Lasry-Lions double envelope of the nonconvex
function ||x| - 1|.  Both the discrete pl_ll and the PLQ
explicit algorithms are shown.
Functions Demoed: pl_ll, plq_me/plq_scalar

10. plq_co.sce
Illustrates the convex hull of an arbitrary PLQ function.
In this case, the function is nonconvex and nonsmooth, so
the convex hull is convex and nonsmooth.  The function
does not decrease to negative infinity as x goes to positive
or negative infinity, so the convex hull is finite as x goes
to +/- infinity as well.
Function demoed: plq_co

11. plq_coSplit.sce
Demonstrates the steps of the plq_coSplit algorithm using convex
duality, by computing the convex hull of a sample nonconvex PLQ
function.
Function demoed: plq_coSplit

12. time_co.sce
Compares the performance of the plq_coDirect and plq_coSplit
algorithms for computing convex hulls of PLQ functions, by computing
the convex hull of a quadratic spline of increasing number of pieces.
Functions demoed: plq_coDirect, plq_coSplit

13. plq_rock.sce
Demonstrates the Rockafellar function of an operator for
each possible point in the operator.  This demos uses the
PLQ algorithm which runs in time linear with the size of the
operator.  This algorithm is also used to compute the
PLQ Fitzpatrick function of infinite order when x* is zero.
Function demoed: plq_rock

14. time_fitz.sci
Compares 4 algorithms to evaluate general Fitzpatrick
functions of an operator.  Each algorithm is timed on the
computation of the Fitzpatrick function of infinite order
for the half-norm-squared operator for increasing grid
sizes, depending on the parameters the user selects when the
demo is run.  The algorithms are op_fitz_brute,
op_fitz_direct, op_fitz, and op_fitzinf.  op_fitz is the
fastest completely general algorithm, and op_fitzinf is
faster when computing infinite order functions.
Functions demoed: op_fitz_brute, op_fitz_direct, op_fitz, op_fitzinf

15. time_plq_etc.sce
Compares the PLQ, GPH, OPT, and LLT algorithms for computing the
Legendre-Fenchel transform, the Moreau envelope, and the Proximal
average of a function of increasing size.

PLQ PROXIMAL AVERAGE DEMOS

16. im_q2l.sce
Compares the arithmetic and proximal averages of a quadratic
function and a linear function.  It shows that functions
being equal at a point doesn't mean the proximal average
at the point will equal that value.
Function demoed: plq_pa

17. nl2nl.sce
Plots the proximal average transition from -log(x) to
-log(-x).  It shows that a proximal average exists even when
two functions have completely disjoint domains.  The
proximal average remains convex for all lambdas.
Function demoed: plq_pa

18. norm.sce
Illustrates the proximal average of two cones by a contour
plot with one level curve (at z=1) for each lambda.
Function demoed: pl_lft_llt_2d

19. sub.sce
Plots the proximal average of the indicator function of the
Y=0 plane and the indicator function of the X=0 plane in 3d
space.  The average can be plotted as a subdivided graph or
as an animation.
Function demoed: plq_pa

20. im_exp2expstar.sce
Plots the proximal average of exp(x) and its conjugate,
s*ln(s)-s.
Function demoed: plq_pa

21. pa_nonconvex.sce
Demonstrates the proximal average of two nonconvex functions
with a smoothing parameter of 0.5. Note that the proximal
average does not remain convex.
Function demoed: plq_pa_mu

GRAPH-MATRIX CALCULUS (GPH) DEMOS

22. gph_lft.sce
Demonstrates the computation of the conjugate of a PLQ function in
graph (GPH) matrix form as the mirroring of the graph of the
subdifferential over the line y=x.
Function demoed: gph_lft

23. gph_me.sce
Demonstrates the GPH Moreau envelope algorithm for various scaling
parameters.
Function demoed: gph_me

24. gph_pa.sce
Demonstrates how the proximal average transforms the subdifferential
of f(x) = -x for x<0, x^2 for x>=0, into the subdifferential of
g(x) = 1 for x=1, %inf for x~=1.
Function demoed: gph_pa

========
Credits:
========
See copyright.txt for the list of contributors to this library.
