# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## Appendix A Polynomial Optimality Test Based on Abs-Linear Form  
As illustrated for the Nesterov test function, it may be advantageous to use intermediate variables \(z_{i}\) that are not arguments of the absolute value themselves. For simplicity, we assume that these switching variables that do not impose nonsmoothness are located in the last components of \(z\) and that only the \(\hat{s}\leq s\) components \(z_{1},\ldots z_{\hat{s}}\) are arguments of the absolute value. Let us abbreviate the current iterate \(x_{k}\) with \(\hat{x}=x_{k}\) and denote the corresponding switching vector by \(\hat{z}=z(\hat{x})\), the signature vector \(\hat{v}=\operatorname{sgn}(\hat{z})\) and the active index set by \(\alpha=\{i\leq\hat{s}:\hat{v}_{i}=0\}\) with cardinality \(m\equiv|\alpha|\leq\hat{s}\). Consequently, there are exactly \(2^{m}\) definite signatures by \(\sigma>\hat{v}\) and the same number of limiting gradients for the three generalized differentials \(\hat{v}_{f}^{\overline{\hat{f}}},\hat{c}\hat{f}\), and \(\hat{c}f\). For all \(x\in\mathcal{P}_{\hat{v}}\), the signature \(\hat{v}\) is constant and we can use Corollary 1 to define the smooth function  
\[z_{\hat{v}}(x)\ =\ (I-M-L\hat{\Sigma})^{-1}(c+Zx)\ =\ \hat{c}+\hat{Z}x\, \tag{29}\]  
where we have pulled out the unit lower triangular factor \((I-M-L\hat{\Sigma})\) such that  
\[\hat{Z}=(I-M-L\hat{\Sigma})^{-1}Z\quad\text{and}\quad\hat{c}=(I-M-L\hat{\Sigma })^{-1}c\.\]  
For \(x\approx\hat{x}\) to be contained in the extended closure \(\bar{\mathcal{P}}_{\hat{v}}\) as defined in Equation (14), it must satisfy the \(m\) linear equations  
\[P_{\alpha}z(x)=0\in\mathbb{R}^{m}\quad\text{for}\quad P_{\alpha}=(e_{i}^{\top })_{i\in\alpha}\in\mathbb{R}^{m\times\hat{s}}\]  
with \(e_{i}\) denoting the \(i\)th unit vector in \(\mathbb{R}^{\hat{s}}\). Thus it is necessary and sufficient for \(\bar{\mathcal{P}}_{\hat{v}}\) to be a polyhedron of dimension \(n-m\) that the Jacobian \(P_{\alpha}\hat{Z}\in\mathbb{R}^{m\times n}\) has full row rank \(m\). This rank condition was introducedas LIKQ in [7] and obviously requires that no more than \(n\) switches are active at \(\hat{x}\). As discussed in [7], for the point \(\hat{x}\) to be a local minimizer of \(f\) it is necessary that it solves the trunk problem  
\[\min a^{\top}x+b^{\top}\!\!z\quad s.t.\quad|\hat{\Sigma}|z-\hat{c}-\hat{Z}x=0\.\]  
Here \(|\hat{\Sigma}|\in\mathbb{R}^{\hat{x}\times\hat{s}}\) is the projection onto the \(\hat{s}-m\) vector components whose indices do not belong to \(\alpha\) so the equality constraint combines (A1) and the constraint \(P_{\alpha}z=0\). Now we get from KKT theory or equivalently LOP duality that \(\hat{x}\) is a minimizer on \(\mathcal{P}_{\alpha}\) if and only if for some Lagrange multiplier vector \(\lambda\in\mathbb{R}^{\hat{s}}\)  
\[a^{\top}=-\lambda^{\top}\hat{Z}\quad\text{and}\quad b^{\top}=\lambda^{\top}| \hat{\Sigma}|\.\] (A2)  
Since \(I=|\hat{\Sigma}|+P_{\alpha}^{\top}P_{\alpha}\) we derive that  
\[\lambda^{\top}(I-|\hat{\Sigma}|)\hat{Z}\ =\ \lambda_{\alpha}^{\top}P_{ \alpha}\hat{Z}=-a^{\top}-b^{\top}\!\!\hat{Z}\.\] (A3)  
where \(\lambda_{\alpha}=P_{\alpha}\lambda\). This is a generally overdetermined system of \(n\) equations in the \(m\) components of \(\lambda_{\alpha}\). If it is solvable the full multiplier vector \(\lambda=P_{\alpha}^{\top}\lambda_{\alpha}+|\hat{\Sigma}|b\) is immediately available. Because of the assumed full rank of the Jacobian \(P_{\alpha}\hat{Z}\) we have \(m\leqslant n\), and if \(\hat{x}\) is a vertex in that \(m\!=\!n\) the tangential stationarity condition (A3) is automatically satisfied. Now it is necessary and sufficient for local minimality that \(\hat{x}\) is also a minimizer of \(f\) on all polyhedra \(\bar{\mathcal{P}}_{\sigma}\) with definite \(\sigma>\hat{\sigma}\).