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

  <refnamediv>
    <refname>gph_function</refname>
    <refpurpose>Graph-matrix calculus (GPH), Function model</refpurpose>
  </refnamediv>

   <refsection>
     <title>Description</title>

     <para>
       A continuous, convex, possibly nonsmooth, PLQ function can be encoded in a "GPH matrix" as follows:

       <!--<programlisting role="example"><![CDATA[
    [x(0)  x(1)  x(2)  ..  x(n)  x(n+1)]
    [s(0)  s(1)  s(2)  ..  s(n)  s(n+1)]
    [y(0)  y(1)  y(2)  ..  y(n)  y(n+1)]

where

x(i) are points in the function's domain,
s(i) are subgradients of f at x(i),
y(i) are the value of f at x(i): y(i) = f(x(i)).

For all i <= j: x(i) <= x(j)
                s(i) <= s(j)
]]></programlisting>-->
			<para>
				<inlinemediaobject>
					<imageobject>
						<imagedata fileref="gph_ImagesOfEquationsByLatex/gph_function/gph_function_1.png"/>
					</imageobject>
				</inlinemediaobject>
			</para>
     </para>

     <para>
       This is a useful representation because the subdifferentials of
       functions under many convex transforms can be computed by a
       matrix multiplication with the graph of the subdifferential of
       the original function.  The above matrix stores the graph of
       the subdifferential.
     </para>

     <para>
       The subdifferential of a PLQ function f is a piecewise affine
       function, with potentially vertical regions where f is
       nonsmooth.  Hence the matrix merely needs to store the vertices
       in the subdifferential, that are necessary to recover the
       entire graph using piecewise linear interpolation.  Breakpoints
       in the domain of f will be x values in gph, but the converse is
       not necessarily true: redundant points may be stored in the
       matrix, as will often be the case after performing a convex
       transform.  Uniqueness of representation is not guaranteed, as
       it is with PLQ functions.
     </para>

     <para>
       The points at index 0 and n+1 are stored to capture the
       subdifferential on the intervals [-%inf,x(1)] and [x(n),%inf],
       respectively.  To indicate that a function has bounded domain
       on the left, set x(0)=x(1) and y(0)=%inf, and for boundedness
       on the right, set x(n)=x(n+1) and y(n+1)=%inf.  All other y(i),
       and all x(i) and s(i), must be finite.
     </para>

     <para>
       The indicator function of a point x0, f(x) = I_{x0}(x) + y0, is
       stored as the matrix

       <!--<programlisting role="example"><![CDATA[
    [x0 x0]
    [s0 s1]
    [y0 y0]
]]></programlisting>-->
			<para>
				<inlinemediaobject>
					<imageobject>
						<imagedata fileref="gph_ImagesOfEquationsByLatex/gph_function/gph_function_2.png"/>
					</imageobject>
				</inlinemediaobject>
			</para>

       <para>for any s0 &lt; s1.  (If s0 = s1 then the matrix collapses to
       a single column, and the graph is no longer maximal.)</para>
     </para>
   </refsection>

   <refsection>
     <title>Examples</title>

     <para>
       (The matrices listed are just potential representations, that are
     minimal in size.)
     </para>

     <programlisting role="example"><![CDATA[
//f1(x) = x^2:
G1=[0 1; 0 2; 0 1];

//f2(x) = |x|:
G2=[-1  0  0  1; -1 -1  1  1; 1  0  0  1];

//f3(x) = 0 on [-1,1]; f(x) = %inf elsewhere:
G3=[ -1 -1  1   1; -1  0  0   1; %inf 0  0 %inf];

//f4(x) = 0 on [-1,1]; f(x) = x^2 - 1 elsewhere:
G4=[-2 -1 -1  1  1  2; -4 -2  0  0  2  4; 3  0  0  0  0  3];
]]></programlisting>
   </refsection>

   <refsection>
     <title>See Also</title>
     <simplelist type="inline">
       <member><link linkend="gph_add">gph_add</link></member>
       <member><link linkend="gph_eval">gph_eval</link></member>
       <member><link linkend="gph_isBounded">gph_isBounded</link></member>
       <member><link linkend="gph_isEqual">gph_isEqual</link></member>
       <member><link linkend="gph_lft">gph_lft</link></member>
       <member><link linkend="gph_me">gph_me</link></member>
       <member><link linkend="gph_pa">gph_pa</link></member>
       <member><link linkend="gph_plot">gph_plot</link></member>
       <member><link linkend="gph_prox">gph_prox</link></member>
       <member><link linkend="gph_scalar">gph_scalar</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 January 2010, Graph-Matrix Calculus for Computational Convex Analysis.</listitem>
     </itemizedlist>
   </refsection>

</refentry>
