Representations and Analysis of Piecewise Linear Functions in Abs-normal form

Manuel Radons^*

It follows from the well known min/max representation given by Scholtes in his recent Springer book, that all piecewise linear continuous functions \(y = F(x) : \mathbb{R}^n \to \mathbb{R}^m\) can be written in a so-called abs-normal form. This means in particular, that all nonsmoothness is encapsulated in \(s\) absolute value functions that are applied to intermediate switching variables \(z_i\) for \(i=1, \ldots ,s\). The relation between the vectors \(x, z\), and \(y\) is described by four matrices \(Y, L, J\), and \(Z\), such that \[ \left(\begin{matrix} z \\ y \end{matrix}\right) = \left(\begin{matrix} b \\ c \end{matrix}\right) + \left(\begin{matrix} Z & L \\ J & Y \end{matrix}\right) \left(\begin{matrix} x \\ |z| \end{matrix}\right) \] which can be generated by ADOL-C or other Automatic Differentation Tools. Here \(L\) is a strictly lower triangular matrix, and therefor \( z_i\) can be computed successively from previous results. We show that in the square case \(n=m\) the system of equations \(F(x) = 0\) can be rewritten in terms of the variable vector \(z\) as a linear complementarity problem (LCP). The transformation itself and the properties of the LCP depend on the Schur complement \(S = L - Z J^{-1} Y\). We discuss associated linear algebra computations and highlight various theoretical and numerical effects via examples. %through examples.

Mathematics Subject Classification: 65F99 65K99

Keywords: switching depth, smooth dominance, Perron-Frobenius radius, linear complementarity, Lipschitz-continuity, Automatic differentiation

Minisymposion: Nonsmooth Optimization