1%
2%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3\subsection{Drivers for Abs-Normal Form}
4\label{absdrivers}
5%
6In this subsection we consider functions $y=F(x):\R^n \rightarrow \R^m$ that are non-smooth because of the occurrence of
7the absolute value function. The drivers provided generate a piecewise-linear
8approximation of the function $F$ in a point $x_0$ and first order derivatives of
9this second order approximation. The piecewise-linear model will be called piecewise
10linearization in the following. Further information about the piecewise linearization
11you can find in \cite{Griewank13}.
12
13The piecewise linearization is given in \textit{abs-normal} form by
14\[ \left[\begin{array}{c}
15          z\\y
16         \end{array}\right]
17   =\left[\begin{array}{c}
18          c\\b
19         \end{array}\right]
20    +\left[\begin{array}{cc}
21          Z & L\\ J & Y
22         \end{array}\right]
23    \left[\begin{array}{c}
24          x\\|z|
25         \end{array}\right].
26\]
27Here $z\in\R^s$ is a vector of $s\ge 0$ \textit{switching variables} and correspondingly
28the two vectors and four matrices specifying the function $F$ have the format
29\[c\in\R^s,\quad Z\in\R^{s\times n},\quad L\in\R^{s\times s},\quad b\in \R^m,\quad J\in\R^{m\times n}, Y\in\R^{m\times s}.\]
30The matrix $L$ is strictly lower triangular.
31
32To compute the piecewise linearization $\Delta F(x_0;x)$ the abs-normal mode has to be
33enabled by using
34\begin{tabbing}
35\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
36\>{\sf enableMinMaxUsingAbs()}
37\end{tabbing}
38before the $\mathit{trace\_on}()$ command.
39If one is interested in the number $s$ of absolute value functions occurring in the function
40evaluation, one can get it by
41\begin{tabbing}
42\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
43\>{\sf int get\_num\_switches(tag)}\\
44\>{\sf short int tag;}         \> // tape identification
45\end{tabbing}
46after tracing the function $F$.
47
48In abs-normal mode several drivers are available. For a start there is a driver
49to evaluate $y=F(x)$. The driver also returns the values of $z$ which are the arguments
50of the intermediate absolute value functions. The evaluations of the absolute value
51function is interpreted as $|z_i|=\sigma_i*z_i$ with $\sigma_i=sign(z_i)$ in the zero
52order mode. The vector $\sigma\equiv \{-1,0,1\}^s$ is called signature vector.
53
54\begin{tabbing}
55\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
56\>{\sf int zos\_pl\_forward(tag,m,n,keep,x,y,z)}\\
57\>{\sf short int tag;}         \> // tape identification \\
58\>{\sf int n;}                 \> // number of independent variables $n$ and $m=1$\\
59\>{\sf int m;}                 \> // number of dependent variables $m$\\
60\>{\sf int keep;}              \> // flag for reverse mode preparation\\
61\>{\sf double x[n];}           \> // independent vector $x$ \\
62\>{\sf double y[m];}           \> // dependent vector $y=F(x)$ \\
63\>{\sf double z[s];}           \> // argument of $\mathbf{abs}(z)$
64\end{tabbing}
65%
66Additionally, there are drivers for the forward mode to evaluate first order
67derivatives of the piecewise linearization. For first order derivatives another
68signature vector generated by
69\begin{tabbing}
70\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
71\>{\sf int firstsign($z_i$, $Z[i]$)}\\
72\>{\sf double z[s];}          \> // i-th component of argument of $\mathbf{abs}(z)$ \\
73\>{\sf double Z[s][p];}          \> // i-th row of first derivative $Z=z\prime (x)X$
74\end{tabbing}
75has to be used. \textit{firstsign(u)} of a vector $u$ is defined as the \textit{sign()}
76of the first non-vanishing component of $u$ if that exists; otherwise the value is zero.
77More detailed information can be found in \cite{Griewank13}.
78
79\begin{tabbing}
80\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
81\>{\sf int fos\_pl\_forward(tag,m,n,x0,x1,y0,y1,z0,z2)}\\
82\>{\sf short int tag;}         \> // tape identification \\
83\>{\sf int m;}                 \> // number of dependent variables $m$\\
84\>{\sf int n;}                 \> // number of independent variables $n$\\
85\>{\sf double x0[n];}          \> // independent vector $x$ \\
86\>{\sf double x1[n];}          \> // tangent vector $x1$\\
87\>{\sf double y0[m];}          \> // dependent vector $y_0=F(x_0)$ \\
88\>{\sf double y1[m];}          \> // first derivative $y_1=F^\prime (x_0)x_1$\\
89\>{\sf double z0[s];}          \> // argument of $\mathbf{abs}(z_0)$ \\
90\>{\sf double z1[s];}          \> // first derivative $z_1=z_0^\prime (x_0)x_1$
91\end{tabbing}
92
93\begin{tabbing}
94\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
95\>{\sf int fov\_pl\_forward(tag,m,n,p,x,X,y,Y,z,Z)}\\
96\>{\sf short int tag;}         \> // tape identification \\
97\>{\sf int m;}                 \> // number of dependent variables $m$\\
98\>{\sf int n;}                 \> // number of independent variables $n$\\
99\>{\sf int p;}                 \> // number of directions\\
100\>{\sf double x[n];}           \> // independent vector $x$ \\
101\>{\sf double X[n][p];}        \> // tangent matrix $X$\\
102\>{\sf double y[m];}           \> // dependent vector $y=F(x)$ \\
103\>{\sf double Y[m][p];}        \> // first derivative matrix $Y=F^\prime (x)X$\\
104\>{\sf double z[s];}           \> // argument of $\mathbf{abs}(z)$ \\
105\>{\sf double Z[s][p];}        \> // first derivative matrix $Z=z^\prime (x)X$
106\end{tabbing}
107
108In contrast to the drivers above the reverse mode does not require any directions.
109It always returns one row of the Jacobian matrix.
110
111\begin{tabbing}
112\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
113\>{\sf int fov\_pl\_reverse(tag,m,n,s,rownum,z)}\\
114\>{\sf short int tag;}         \> // tape identification \\
115\>{\sf int m;}                 \> // number of dependent variables $m$\\
116\>{\sf int n;}                 \> // number of independent variables $n$\\
117\>{\sf int s;}                 \> // number of sign switches\\
118\>{\sf int rownum;}            \> // required row no. of abs-normal form \\
119\>{\sf double z[n];}           \> // resulting adjoint value $z^T = u^T F^\prime (x)$\\
120\end{tabbing}
121
122One may also compute the sparsity pattern of the extended Jacobian
123matrix
124
125\begin{tabbing}
126\hspace{0.5in}\={\sf short int tag;} \hspace{1.1in}\= \kill    % define tab position
127\>{\sf \#include $<$adolc/sparse/sparsedrivers.h$>$} \>\phantom{something}\\
128\>{\sf int absnormal\_jac\_pat(tag,m,n,s,x,JP)}\\
129\>{\sf short int tag;}         \> // tape identification \\
130\>{\sf int m;}                 \> // number of dependent variables $m$\\
131\>{\sf int n;}                 \> // number of independent variables $n$\\
132\>{\sf int s;}                 \> // number of sign switches\\
133\>{\sf const double* x;}       \> // point of evaluation\\
134\>{\sf unsigned int** JP;}     \> // sparsity pattern of abs-normal form \\
135\end{tabbing}
136% \bibitem{Griewank13}
137% Andreas Griewank,
138% {\em On stable piecewise linearization and generalized algorithmic differentiation}.
139% Optimization Methods and Software 28(6):1139--1178, 2013.
140