<?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="plq_coSplit">
  <info>
    <pubdate>14-May-2010</pubdate>
  </info>

  <refnamediv>
    <refname>plq_coSplit</refname>
    <refpurpose>Piecewise linear quadratic (plq), Convex hull (splitting algorithm)</refpurpose>
  </refnamediv>

   <refsynopsisdiv>
     <title>Calling Sequence</title>
     <synopsis>plqco = plq_coSplit(plqf)</synopsis>
   </refsynopsisdiv>

   <refsection>
     <title>Parameters</title>
     <variablelist>

       <varlistentry>
         <term>plqf</term>
         <listitem>
           <para>matrix. A plq function whose convex hull will be computed.</para>
         </listitem>
       </varlistentry>

       <varlistentry>
         <term>plqco</term>
         <listitem>
           <para>matrix. A plq function that is the convex hull of the original function.</para>
         </listitem>
       </varlistentry>

     </variablelist>
   </refsection>

   <refsection>
     <title>Description</title>

     <para>
       Computes the convex hull of a continuous, but not necessarily convex, plq
       function, where the input and output are given in the form of a plq
       matrix.
     </para>

     <para>
       This algorithm works by reformulating the convex hull of f as
       <!--<programlisting role="example"><![CDATA[
    co f = co min (co g_1, co g_2, ..., co g_n) = (max(g_1*, g_2*, ..., g_n*))* ,
       ]]></programlisting>-->
	   <para>
			<inlinemediaobject>
				<imageobject>
					<imagedata fileref="plq_ImagesOfEquationsByLatex/plq_coSplit/plq_coSplit_1.png"/>
				</imageobject>
			</inlinemediaobject>
		</para>
	   <para>
       where co represents the convex hull, max/min are functions that
       are the pointwise minima and maxima of their arguments, * is
       the convex conjugate, and each g_i is defined via
	   </para>
       <!--<programlisting role="example"><![CDATA[
    g_i(x) = { f(x), if X(i-1) <= x <= X(i);
             { %inf, otherwise.

    X is the x-values in the GPH matrix: X = gph(1,:).
       ]]></programlisting>-->
	   <para>
			<inlinemediaobject>
				<imageobject>
					<imagedata fileref="plq_ImagesOfEquationsByLatex/plq_coSplit/plq_coSplit_2.png"/>
				</imageobject>
			</inlinemediaobject>
		</para>
     </para>

     <para>
       plq_coSplit requires worst-case quadratic time, and best-case
       linear time.  g_i* require O(1) work, but the model may grow as
       its maximum is computed with each g_i*, so the max takes O(n^2)
       time to compute, where n is the number of points stored in f's
       GPH matrix.  The final conjugate is a linear operation.
     </para>
   </refsection>

   <refsection>
     <title>Examples</title>
     <programlisting role="example"><![CDATA[
// The hull of a linear-linear-quadratic function:
plqf = [0,0,0,%inf; 1,0,-1,1; 2,0,1,-1; 3,0,-1,3; 4,0,1,-3; %inf,0,0,%inf];
result = plq_coSplit(plqf),
scf(); plq_plotMultiple(%f, %f, plqf, result);

// The hull of a more complicated function:
plqf = [-3,1,8,16;0,0,1,4;3,0,-1,4;%inf,1,-8,16];
result = plq_coSplit(plqf),
scf(); plq_plotMultiple(%f, %f, plqf, result);
]]></programlisting>
   </refsection>

   <refsection>
     <title>See Also</title>
     <simplelist type="inline">
       <member><link linkend="plq_co">plq_co</link></member>
       <member><link linkend="plq_coDirect">plq_coDirect</link></member>
       <member><link linkend="plq_function">plq_function</link></member>
   </simplelist></refsection>

   <refsection>
     <title>Authors</title>
     <para>
       <literal>Bryan Gardiner</literal>, University of British Columbia, BC, Canada
     </para>
   </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>
     </itemizedlist>
   </refsection>

</refentry>
