# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 3 Forming and Extending the Abs-Linear Form
The arrows indicate the path of our reflection version of the DCA method as described in Section 5. When \(\sigma\) is definite, i.e., has no zero components, which we will denote by \(0\
otin\sigma\), it follows from the continuity of \(z(x)\) that \(\mathcal{P}_{\sigma}\) has full dimension \(n\) unless it is empty. In degenerate situations this may also be true for indefinite \(\sigma\) but then the closure of \(\mathcal{P}_{\sigma}\) is equal to the extended closure  
\[\bar{\mathcal{P}}_{\bar{\sigma}}\ \equiv\ \{x\in\mathbb{R}^{n}:\sigma(x) \prec\bar{\sigma}\}\ \supset\ \text{close}(\mathcal{P}_{\bar{\sigma}}) \tag{14}\]  
for some definite \(0\
otin\tilde{\sigma}>\sigma\). Here the (reflexive) partial ordering \(<\) between the signature vectors satisfies the equivalence  
\[\tilde{\sigma}<\sigma\quad\iff\quad\tilde{\sigma}_{i}\sigma_{i}\leq\sigma_{i} ^{2}\quad\text{for}\quad i=1\ldots s\quad\iff\quad\bar{\mathcal{P}}_{\bar{ \sigma}}\subset\bar{\mathcal{P}}_{\sigma}\]  
as shown in [13]. One can easily check that for any \(\sigma>\hat{\sigma}\) there exists a unique signature  
\[(\sigma\rhd\delta)_{i}\quad=\quad \begin{cases}\sigma_{i}\quad\text{if}\quad \delta_{i}\
eq 0\\ -\sigma_{i}\quad\text{if}\quad\delta_{i}=0\end{cases} \quad\text{for}\quad i=1 \ldots s \tag{15}\]  
We call \(\tilde{\sigma}=\sigma\rhd\delta\) the reflection of \(\sigma\) at \(\hat{\sigma}\), which satisfies also \(\tilde{\sigma}>\hat{\sigma}\) and we have in fact \(\bar{\mathcal{P}}_{\bar{\sigma}}\cap\bar{\mathcal{P}}_{\sigma}=\bar{\mathcal{ P}}_{\bar{\sigma}}\). Hence the relation between \(\sigma\) and \(\tilde{\sigma}\) is symmetric in that also \(\sigma=\tilde{\sigma}\rhd\delta\). Therefore we will call \((\sigma,\hat{\sigma})\) a complementary pair with respect to \(\hat{\sigma}\). In the very special case \(z_{i}=x_{i}\) for \(i=1\ldots n=s-1\) the \(\bar{\mathcal{P}}_{\sigma}\) are orthants and their reflections at the origin \(\{0\}=\bar{\mathcal{P}}_{0}\subset\mathbb{R}^{n}\) are their geometric opposites \(\bar{\mathcal{P}}_{\bar{\sigma}}\) with \(\tilde{\sigma}=-\sigma\). Here one can see immediately that all edges, i.e., one-dimensional polyhedra, have Cartesian signatures \(\pm e_{i}\) for \(i=1\ldots n\) and belong to \(\mathcal{P}_{\sigma}\) or \(\bar{\mathcal{P}}_{\bar{\sigma}}\) for any given \(\sigma\). Notice that \(\hat{x}\) is a local minimizer of a piecewise linear function if and and only if it is a local minimizer along all edges of nonsmoothness emanating form it. Consequently, optimality of \(f\) restricted to a complementary pair is equivalent to local optimality on \(\mathbb{R}^{n}\), not only in this special case, but whenever the Linear Independence Kink Qualification (LIKQ) holds as introduced in [13] and defined in the Appendix A. This observation is the basis of the implicit optimality condition verified by our DCA variant Algorithm 1 through the use of reflections. The situation is depicted in Figure 3 where the signatures \((-1,-1,-1)\) and \((1,-1,1)\) as well as \((1,-1,1)\) and \((1,1,-1)\) form complementary pairs at \((0,-1)\) and \((1,1)\), respectively. At both reflection points there are four emanating edges, which all belong to one of the three polyhedra mentioned. Applying the propagation rules from Lemma 1, one obtains with \(\delta x=0\in\mathbb{R}^{n}\) the recursion  
\[\delta z_{1}=\delta(c_{1}+Z_{1}x)=0\] \[\delta z_{i}=(|M_{i}|+2|L_{i}|)\delta z+|L_{i}||z|\qquad\text{for} \quad i=2\ldots s\,\]  
where the modulus is once more applied componentwise for vectors and matrices. Hence, we have again in matrix vector notation  
\[\delta z=(|M|+2|L|)\delta z+|L||z|\, \tag{16}\]  
which yields for \(\delta z\) the explicit expression  
\[\delta z\ =\ (I-|M|-2|L|)^{-1}|L||z|\ =\ \sum_{j=0}^{v}(|M|+2|L|)^{j}\ |L||z|\ \geq\ 0. \tag{17}\]Here, \(v\) is the so-called switching depth of the abs-linear form of \(f\), namely the largest \(v\in\mathbb{N}\) such that \((|M|+|L|)^{v}\
eq 0\), which is always less than \(s\) due to the strict lower triangularity of \(M\) and \(L\).