# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 3 Forming and Extending the Abs-Linear Form  
In practice all piecewise linear objectives can be evaluated by a sequence of abs-linear operations, possibly after min and max have been rewritten as  
\[\min(u,w)=\tfrac{1}{2}(u+w-|u-w|)\quad\text{and}\quad\max(u,w)=\tfrac{1}{2}(u+w+|u -w|). \tag{10}\]  
Our only restriction is that the number \(s\) of intermediate scalar quantities, say \(z_{i}\), is fixed, which is true for example in the \(\max-\min\) representation. Then we can immediately cast the procedure in matrix-vector notation as follows:  
**Lemma 2** (Abs-Linear Form). : _Any continuous piecewise affine function \(f:x\in\mathbb{R}^{n}\mapsto y\in\mathbb{R}\) can be represented by_  
\[ \begin{split} z&=c+Zx+Mz+L|z|\,\\ y&=d+a^{\top}x+b^{\top}z\,\end{split}  \tag{11}\]  
_where \(z\in\mathbb{R}^{s},Z\in\mathbb{R}^{s\times n},M,L\in\mathbb{R}^{s\times s}\) strictly lower triangular, \(d\in\mathbb{R},a\in\mathbb{R}^{n},b\in\mathbb{R}^{s}\) and \(|z|\) denotes the componentwise modulus of the vector \(z\)._  
It should be noted that the construction of this general abs-linear form requires no analysis or computation whatsoever. However, especially for our purpose of generating a reasonably tight DC decomposition, it is advantages to reduce the size of the abs-normal form by eliminating all intermediates \(z_{j}\) with \(j<s\) for which \(|z_{j}|\) never occurs on the right hand side. To this end we may simply substitute the expression of \(z_{j}\) given in the \(j\)-th row in all places where \(z_{j}\) itself occurs on the right hand side. The result is what we will call a reduced abs-normal form, where after renumbering, all remaining \(z_{j}\) with \(j<s\) are switching variables in that \(|z_{j}|\) occurs somewhere on the right hand side. In other words, all but the last column of the reduced, strictly lower triangular matrix \(L\) are nontrivial. Again, this reduction process is completely mechanical and does not require any nontrivial analysis, other than looking up which columns of the original \(L\) were zero. The resulting reduced system is smaller and probably denser, which might increase the computation effort for evaluating \(f\) itself. However, in view of Equation (9) we must expect that for the reduced form the radii will grow slower if we first accumulate linear coefficients and then take their absolute values. Hence we will assume in the remainder of this paper that the abs-normal form for our objective \(f\) of interest is reduced. Based on the concept of abs-linearization introduced in [11], a slightly different version of a (reduced) abs-normal form was already proposed in [12]. Now in the present paper, both \(z\) and \(y\) depend directly on \(z\) via the matrix \(M\) and the vector \(b\), but \(y\) does no longer depend directly on \(|z|\). All forms can be easily transformed into each other by elementary modifications. The intermediate variables \(z_{i}\) can be calculated successively for \(1\leqslant i\leqslant s\) by  
\[z_{i}=c_{i}+Z_{i}x+M_{i}z+L_{i}|z|\, \tag{12}\]  
where \(Z_{i}\), \(M_{i}\) and \(L_{i}\) denote the \(i\)th rows of the corresponding matrix. By induction on \(i\) one sees immediately that they are piecewise affine functions \(z_{i}=z_{i}(x)\), and we may define for each \(x\) the signature vector  
\[\sigma(x)=(\text{sgn}(z_{i}(x)))_{i=1\ldots s}\in\{-1,0,1\}^{s}\.\]  
Consequently we get the inverse images  
\[\mathcal{P}_{\sigma}\ \equiv\ \{x\in\mathbb{R}^{n}:\text{sgn}(z(x))=\sigma\} \quad\text{for}\quad\sigma\in\{-1,0,1\}^{s}\, \tag{13}\]which are relatively open polyhedra that form collectively a disjoint decomposition of \(\mathbb{R}^{n}\). The situation for the second example of Nesterov is depicted in Figure 3 in the penultimate section. There are six polyhedra of full dimension, seven polyhedra of co dimension 1 drawn in blue and two points, which are polyhedra of dimension 0. The point \((0,-1)\) with signature \((0,-1,0)\) is stationary and the point \((1,1)\) with signature \((1,0,0)\) is the minimizer as shown in [7].