<?xml version="1.0" encoding="ISO-8859-1"?><refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook" version="5.0-subset Scilab" xml:lang="en" xml:id="CCA"><info><pubdate>04-Apr-2006</pubdate></info><refnamediv><refname>CCA</refname><refpurpose>Computational Convex Analysis toolbox description</refpurpose></refnamediv>
  
   
  
   
  
   
  
   
  
   

  
   <refsection><title>Description</title>
	
      <para>
		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.
	</para>

        <para>
          Many exact transforms work with piecewise linear-quadratic functions and their subdifferentials, and visualizing these models is easy.  See the main pages for <link linkend="plq_function">PLQ functions</link> and their <link linkend="gph_function">subdifferentials</link>.
        </para>
	
      <para>
		The transforms currently implemented are:
	</para>
	
      <itemizedlist>
	
         <listitem>
		
            <variablelist>
			
               <varlistentry><term>lft</term><listitem>
				
                  <para>The <literal>Legendre-Fenchel transform</literal> (also called Legendre-Fenchel conjugate, Fenchel conjugate, or convex conjugate): 
					<!--<programlisting><![CDATA[
    f*(s) = sup [ < s, x > - f(x)].
             x
]]></programlisting>-->
					<para>
						<inlinemediaobject>
							<imageobject>
								<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_1.png"/>
							</imageobject>
						</inlinemediaobject>
					</para>
                  </para>

                  <para>The notation <!--<programlisting><![CDATA[<., .>]]></programlisting>-->

						<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_2.png"/>
								</imageobject>
							</inlinemediaobject>
						</para>				  
				  
				  <para>denotes the standard scalar product. Several linear-time algorithms are implemented (functions with names lft_*).</para>
				  
				  </para>
			
               </listitem></varlistentry>

			
               <varlistentry><term>me</term><listitem>
				
                  <para>The <literal>Moreau envelope</literal> (also called Moreau-Yosida approximate):
					<!--<programlisting><![CDATA[
                                 2
    M(s) = inf f(x) + || s - x ||.
            x
]]></programlisting>-->
						<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_3.png"/>
								</imageobject>
							</inlinemediaobject>
						</para>
                  </para>
				
                  <para>
					The notation <!--<programlisting><![CDATA[||.||]]></programlisting>-->
					<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_4.png"/>
								</imageobject>
							</inlinemediaobject>
					</para>
					<para>denotes the Euclidean norm. Several linear-time algorithms are implemented (functions with names me_*).</para>
				  </para>
			
               </listitem></varlistentry>

			
               <varlistentry><term>pl_bb</term><listitem>
				
                  <para>The lower <literal>convex envelope</literal> (also called <literal>convex hull</literal>): 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.</para>
			
               </listitem></varlistentry>

            
               <varlistentry><term>pa</term><listitem>
              
                  <para>The <literal>proximal average</literal> transforms one convex function into another continuously:
                <!--<programlisting><![CDATA[
    P(f0,lambda,f1) = [ (1-lambda)(f0 + ||.||^2/2)* + lambda(f1 + ||.||^2/2)* ]* - ||.||^2/2
]]></programlisting>-->
					<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_5.png"/>
								</imageobject>
							</inlinemediaobject>
					</para>
                <para>where</para> <!--<programlisting><![CDATA[*]]></programlisting>-->
					<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_6.png"/>
								</imageobject>
							</inlinemediaobject>
					</para>
				<para>is the Fenchel conjugate above.</para>
              </para>
              
                  <para>
                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.
              </para>
            
               </listitem></varlistentry>

            
               <varlistentry><term>fitz</term><listitem>
              
                  <para>The <literal>Fitzpatrick function</literal> of a finite operator A defined on the real line (functions with names op_fitz* and plq_fitz*):
                <!--<programlisting><![CDATA[
                                               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
]]></programlisting>-->
					<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_7.png"/>
								</imageobject>
							</inlinemediaobject>
					</para>
                <para>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.</para>
              </para>
            
               </listitem></varlistentry>

            
               <varlistentry><term>rock</term><listitem>
              
                  <para>The <literal>Rockafellar function</literal> of a real, finite operator A:
					<para>
							<inlinemediaobject>
								<imageobject>
									<imagedata fileref="miscellaneous_ImagesOfEquationsByLatex/about_CCA/about_CCA_8.png"/>
								</imageobject>
							</inlinemediaobject>
					</para>
                <!--<programlisting><![CDATA[
    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)
]]></programlisting>-->
                <para>This algorithm uses PLQ functions to achieve a worst-case linear time complexity.</para>
              </para>
            
               </listitem></varlistentry>
		
            </variablelist>
	
         </listitem>
	
      </itemizedlist>
	
      

  
   </refsection>

  
   <refsection><title>See Also</title><simplelist type="inline">
	
      <member>Main functions:</member>
	
      <member>
         <link linkend="pl_lft_llt">pl_lft_llt</link>
      </member>
    
      <member>
         <link linkend="pl_lft_llt_2d">pl_lft_llt_2d</link>
      </member>
	
      <member>
         <link linkend="pl_me_llt">pl_me_llt</link>
      </member>
	
      <member>
         <link linkend="pl_me_llt_2d">pl_me_llt_2d</link>
      </member>		
	
      <member>
         <link linkend="pl_bb">pl_bb</link>
      </member>
	
	
      <member>Alternative algorithms:</member>
	
      <member>
         <link linkend="pl_me_nep">pl_me_nep</link>
      </member>
	
      <member>
         <link linkend="pl_me_nep_2d">pl_me_nep_2d</link>
      </member>
	
      <member>
         <link linkend="pl_me_pe">pl_me_pe</link>
      </member>
	
      <member>
         <link linkend="pl_me_pe_2d">pl_me_pe_2d</link>
      </member>

    
      <member>Fitzpatrick/Rockafellar algorithms:</member>
    
      <member>
         <link linkend="op_fitz">op_fitz</link>
      </member>
    
      <member>
         <link linkend="op_fitzinf">op_fitzinf</link>
      </member>
    
      <member>
         <link linkend="plq_fitzinf0">plq_fitzinf0</link>
      </member>
    
      <member>
         <link linkend="plq_rock">plq_rock</link>
      </member>
	
	
      <member>Functions provided for comparison only:</member>
	
      <member>
         <link linkend="pl_lft_direct">pl_lft_direct</link>
      </member>
	
      <member>
         <link linkend="pl_lft_direct_2d">pl_lft_direct_2d</link>
      </member>
	
      <member>
         <link linkend="pl_me_direct">pl_me_direct</link>
      </member>
	
      <member>
         <link linkend="pl_me_direct_2d">pl_me_direct_2d</link>
      </member>
	
      <member>
         <link linkend="pl_me_brute_2d">pl_me_brute_2d</link>
      </member>	
    
      <member>
         <link linkend="op_fitz_brute">op_fitz_brute</link>
      </member>
    
      <member>
         <link linkend="op_fitz_direct">op_fitz_direct</link>
      </member>
    
      <member>
         <link linkend="plq_fitzinf0_direct">plq_fitzinf0_direct</link>
      </member>
  
   </simplelist></refsection>

  
   <refsection><title>Authors</title><para>
    
      <literal>Yves Lucet</literal>, University of British Columbia, BC, Canada
  </para></refsection>

  
   <refsection><title>Contributors</title>
     
      <simplelist>
        <member>Yves Lucet (PI, 1996-)</member>
        <member>Bryan Gardiner (Research Assistant 2008-)</member>
        <member>Scott Fazackerley (USRA 2007, Honours student 2007-08)</member>
        <member>Michael Trienis (M.Sc. student 2006-2007)</member>
        <member>Jeff Dicker (USRA student 2005)</member>
        <member>Andrew Tonner (Research Assistant 2005)</member>
      </simplelist>
  
   </refsection>

  
   <refsection><title>Bibliography</title>
		
         <itemizedlist>
		
            
            <listitem>B. Gardiner, Y. Lucet, Submitted February 2010, Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis.</listitem>

            <listitem>B. Gardiner, Y. Lucet, Submitted January 2010, Graph-Matrix Calculus for Computational Convex Analysis.</listitem>

            <listitem>B. Gardiner, Y. Lucet, 2009, Numerical Computation of Fitzpatrick Functions, Journal of Convex Analysis, 16(4).</listitem>
        
            <listitem>H. H. Bauschke, Y. Lucet, and M. Trienis, 2008, <!-- <link xlink:href="http://link.aip.org/link/?SIR/50/115"> -->How To Transform One Convex Function Continuously Into Another<!-- </link>, <link xlink:href="http://epubs.siam.org/sirev">SIAM Review</link> -->, 50(1):115-132.</listitem>

            <listitem>F. P. Preparata and M. I. Shamos, Computational Geometry An Introduction, Series: Monographs in Computer Science, 1st ed. 1985. Corr. 5th printing 1993.</listitem>
        
            <listitem>Y. Lucet, H. H. Bauschke, and M. Trienis, 2007, <!-- <link xlink:href="http://springerlink.com/content/j726881521t4541l/?p=04f8a46505064fbcb36aaf3165ca2a05&amp;pi=6"> -->The Piecewise Linear-Quadratic Model for Computational Convex Analysis<!-- </link>, <link xlink:href="http://springerlink.com/content/1573-2894/"> -->, Computational Optimization and Applications<!-- </link> -->.</listitem>
		
            <listitem>Y. Lucet, 2006, <!-- <link xlink:href="http://www.springerlink.com/content/h80k45x24t1q7426/"> -->Fast Moreau Envelope Computation I: Numerical Algorithms<!-- </link>, <link xlink:href="http://www.springer.com/west/home/computer/foundations?SGWID=4-156-70-35597981-0"> -->, Numerical Algorithms<!-- </link> -->, 43(3):235-249.</listitem>
		
            <listitem>Y. Lucet, 2005, <!-- <link xlink:href="http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1443139"> -->A linear Euclidean distance transform algorithm based on the Linear-time Legendre Transform<!-- </link> -->, Proceedings of the Second Canadian Conference on Computer and Robot Vision (CRV 2005), IEEE Computer Society Press, 2005.</listitem>
		
            <listitem>Y. Lucet, 1997, <!-- <link xlink:href="http://www.springerlink.com/openurl.asp?genre=article&amp;id=doi:10.1023/A:1019191114493"> -->Faster than the fast Legendre transform, the linear-time Legendre transform<!-- </link>, <link xlink:href="http://www.springer.com/west/home/computer/foundations?SGWID=4-156-70-35597981-0">-->, Numerical Algorithms<!-- </link> -->, 16(2):171-185. Code in Netlib.</listitem>
		
            <listitem>Y. Lucet, 1996, <!-- <link xlink:href="http://www.springerlink.com/link.asp?id=x777265871618672"> -->A fast computational algorithm for the Legendre-Fenchel transform<!-- </link>, <link xlink:href="http://springerlink.com/content/1573-2894/"> -->, Computational Optimization and Applications<!-- </link> -->, 6(1):27-57.</listitem>

            <listitem><!-- http://portal.acm.org/citation.cfm?id=1655289 --> W. L. Hare, 2009, The Proximal Average of Nonconvex Functions: A Proximal Stability Perspective, SIAM Journal on Optimization, 20(2), pp.650-666.</listitem>
	
         </itemizedlist>

  
   </refsection>

</refentry>
