# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 3 Forming and Extending the Abs-Linear Form
The unit lower triangular \((I-|M|-2|L|)\) is an M-matrix [14], and interestingly enough does not even depend on \(x\) but directly maps \(|z|=|z(x)|\) to \(\delta z=\delta z(x)\). For the radius of the function itself, the propagation rules from Lemma 1 then yield  
\[\delta f(x)=\delta y=|b|^{\top}\delta z\geq 0. \tag{18}\]  
This nonnegativity implies the inclusion Equation (1) already mentioned in Section 1, i.e. :  
**Theorem 1** (Inclusion by convex/concave decomposition). : _For any piecewise affine function \(f\) in abs-linear form, the construction defined in Section 2 yields a convex/concave inclusion_  
\[\widehat{f}(x)\ \leq f(x)\ =\ \tfrac{1}{2}(\widetilde{f}(x)+\widehat{f}(x)) \ \leq\ \widetilde{f}(x)\.\]  
_Moreover, the convex and the concave parts \(\widetilde{f}(x)\) and \(\widehat{f}(x)\) have exactly the same switching structure as \(f(x)\) in that they are affine on the same polyhedra \(\mathcal{P}_{\sigma}\) defined in (13)._  
Proof. : Equations (16) and (17) ensure that \(\delta f(x)\) is nonnegative at all \(x\in\mathbb{R}^{n}\) such that  
\[\widehat{f}(x)=f(x)-\delta f(x)\leq f(x)\leq f(x)+\delta f(x)\leq\widetilde{f }(x)\.\]  
It follows from Equation (17) that the radii \(\delta z_{i}(x)\) are like the \(|z_{i}(x)|\) piecewise linear with the only nonsmoothness arising through the switching variables \(z(x)\) themselves. Obviously this property is inherited by \(\delta f(x)\) and the linear combinations \(\widetilde{f}(x)=f(x)+\delta f(x)\) and \(\widehat{f}(x)=f(x)-\delta f(x)\), which completes the proof. Combining Equations (16) and (18) with the abs-linear form of the piecewise affine function \(f\) and defining \(\tilde{z}=(z,\delta z)\in\mathbb{R}^{2s}\), one obtains for the calculation of \(\tilde{f}(x)=\tilde{y}=(y,\delta y)\) the following abs-linear form  
\[\tilde{z} =\tilde{c}+\tilde{Z}x+\tilde{M}\tilde{z}+\tilde{L}|\tilde{z}|\, \tag{19}\] \[\tilde{y} =\tilde{d}+\tilde{a}^{\top}x+\tilde{b}^{\top}z \tag{20}\]  
with the vectors and matrices defined by  
\[\tilde{c} = \begin{bmatrix}c\\ 0\end{bmatrix} \in\mathbb{R}^{2s},\ \tilde{Z}= \begin{bmatrix}Z\\ 0\end{bmatrix} \in\mathbb{R}^{2s\times n},\ \tilde{M}= \begin{bmatrix}M&0\\ 0&|M|+2|L|\end{bmatrix} \in\mathbb{R}^{2s\times 2s},\] \[\tilde{L} = \begin{bmatrix}L&0\\ |L|&0\end{bmatrix} \in\mathbb{R}^{2s\times 2s},\ \tilde{d}= \begin{bmatrix}d\\ 0\end{bmatrix} \in\mathbb{R}^{2},\ \tilde{a}= \begin{bmatrix}a&0\end{bmatrix} \in \mathbb{R}^{n\times 2},\ \tilde{b}= \begin{bmatrix}b&0\\ 0&|b|\end{bmatrix} \in\mathbb{R}^{2s\times 2}.\]  
Then, Equations (19) and (20) yield  
\[ \begin{bmatrix}z\\ \delta z\end{bmatrix}  = \begin{bmatrix}c\\ 0\end{bmatrix} + \begin{bmatrix}Z\\ 0\end{bmatrix} x+ \begin{bmatrix}M&0\\ 0&|M|+2|L|\end{bmatrix}\begin{bmatrix}z\\ \delta z\end{bmatrix} + \begin{bmatrix}L&0\\ |L|&0\end{bmatrix}\begin{bmatrix}|z|\\ |\delta z|\end{bmatrix} = \begin{bmatrix}c+Zx+Mz+L|z|\\ (|M|+2|L|)\delta z+|L||z|\end{bmatrix} \] \[ \begin{bmatrix}y\\ \delta y\end{bmatrix}  =\tilde{d}+\tilde{a}^{\top}x+\tilde{b}^{\top}z= \begin{bmatrix}d\\ 0\end{bmatrix} + \begin{bmatrix}a^{\top}x\\ 0\end{bmatrix} + \begin{bmatrix}b&0\\ 0&|b|\end{bmatrix} ^{\top} \begin{bmatrix}z\\ \delta z\end{bmatrix} = \begin{bmatrix}d+a^{\top}x+b^{\top}z\\ |b|^{\top}\delta z\end{bmatrix} \,\]  
i.e., Equations (16) and (18). As can be seen, the matrices \(\tilde{M}\) and \(\tilde{L}\) have the required strictly lower triangular form. Furthermore, it is easy to check, that the switching depth of the abs-linear form of \(f\) carries over to the abs-linear form for \(\widetilde{f}\) in that also \((|\tilde{M}|+|\tilde{L}|)^{v}\
eq 0=(|\tilde{M}|+|\tilde{L}|)^{v+1}\). However, notice that this system is not reduced since the \(s\) radii are not switching variables, but globally nonnegative anyhow. We can now obtain explicit expressions for the central values, radii, and bounds for a given signature \(\sigma\). **Corollary 1** (Explicit representation of the centered form).