# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## Appendix A Polynomial Optimality Test Based on Abs-Linear Form
Any such \(\sigma>\hat{\sigma}\) can be written as \(\sigma=\hat{\sigma}+\gamma\) with \(\gamma\in\{-1,0,1\}^{\hat{s}}\) structurally orthogonal to \(\hat{\sigma}\) such that for \(\Gamma=\operatorname{diag}(\gamma)\) we have the matrix equations  
\[\Sigma=\hat{\Sigma}+\Gamma\quad\text{and}\quad\hat{\Sigma}\,\Gamma=0=|\hat{ \Sigma}|\,\Gamma\.\]  
Then we can express the \(z(x)=z_{\sigma}(x)\) for \(x\in\mathcal{P}_{\sigma}\) as  
\[z_{\sigma}(x)\ =\ z_{\hat{\sigma}+\gamma}(x) = (I-M-L\hat{\Sigma}-L\Gamma)^{-1}(c+Zx)\] \[= (I-\hat{L}\Gamma)^{-1}(\hat{c}+\hat{Z}x)\,\]  
with \(\hat{L}=(I-M-L\hat{\Sigma})^{-1}L\). Now \(\hat{x}\) must be the minimizer of \(f\) on \(\bar{\mathcal{P}}_{\sigma}\), i.e., solve the problem  
\[\min a^{\top}\!\!x+b^{\top}\!\!z\qquad s.t.\qquad(I-\hat{L}\Gamma)z=\hat{c}+ \hat{Z}x,\quad P_{\alpha}\Gamma z\ \geqslant\ 0\in\mathbb{R}^{m}\.\] (A4)  
Notice that the inequalities are only imposed on the sign constraints that are active at \(\hat{x}\) since the strict inequalities are maintained in a neighborhood of \(\hat{x}\) due to the continuity of \(z(x)\). Then we get again from KKT theory or equivalently LOP duality that still \(a^{\top}\!=\!-\lambda^{\top}\hat{Z}\) and for a second multiplier vector \(0\leqslant\mu\in\mathbb{R}^{m}\) the equalities  
\[\hat{Z}=(I-M-L\hat{\Sigma})^{-1}Z\quad\text{and}\quad\hat{c}=(I-M-L\hat{\Sigma })^{-1}c\.\]0 (A5)  
Multiplying from the right by the projection \(|\hat{\Sigma}|\) we find that the conditions (A2) and (A3) must still hold so that \(\lambda\) remains exactly the same. Moreover, multiplying from the right by \(\Gamma P_{\alpha}^{\top}\) we get with \(P_{\alpha}P_{\alpha}^{\top}=I_{m}\) and \(\Gamma\Gamma=P_{\alpha}^{\top}\!P_{\alpha}\) after some rearrangement the inequality  
\[\hat{Z}=(I-M-L\hat{\Sigma})^{-1}Z\quad\text{and}\quad\hat{c}=(I-M-L\hat{\Sigma })^{-1}c\.\]1 (A6)  
Now the key observation is that this condition is linear in \(\Gamma\) and is strongest for the choice \(\gamma_{i}=\operatorname{sgn}(\lambda_{i}-b_{i})\) for \(i\in\alpha\) yielding the inequalities  
\[\hat{Z}=(I-M-L\hat{\Sigma})^{-1}Z\quad\text{and}\quad\hat{c}=(I-M-L\hat{\Sigma })^{-1}c\.\]2 (A7)In other words, \(\hat{x}\) is a solution of the branch problems (A4) if and only if it is for the worst case where \(\gamma_{i}=\operatorname{sgn}(\lambda_{i}-b_{i})\) for \(i\in\alpha\). When coincidentally \(\lambda_{i}=b_{i}\) we can define \(\gamma_{i}\) arbitrarily. Note that the complementarity condition \(\mu^{\top}P_{\alpha}z(\hat{x})=0\) associated with Equation (A4) is automatically satisfied at \(\hat{x}\) for any \(\mu\), since \(P_{\alpha}\hat{z}=0\) by definition of the active index set \(\alpha\). These observations yield immediately:  
**Proposition A1** (Necessary and sufficient minimality condition). : _Assume LIKQ holds in that \(P_{\alpha}\hat{Z}\) has full row rank \(m-|\alpha|\). Then the point \(\hat{x}\) is a local minimizer of \(f\) if and only if we have tangential stationarity in that \(a+\hat{Z}^{\top}b\) belongs to the range of \(\hat{Z}^{\top}P_{\alpha}^{\top}\) and normal growth holds in that \(|P_{\alpha}(\lambda-b)|\leq P_{\alpha}\hat{L}^{\top}\lambda\)._  
The verification that LIKQ holds and subsequently the test whether tangential stationarity is satisfied can be based on a QR decomposition of the active Jacobian \(P_{\alpha}\hat{Z}\in\mathbb{R}^{m\times n}\). The main expense here is the calculation of \(\hat{Z}\) itself, which requires one forward substitution on \((I-M-L\hat{\Sigma})\) for each of \(n\) columns of \(Z\) and hence at most \(ns^{2}/2\) fused multiply adds. Very likely this effort will already be made by any kind of active set method for reaching the candidate point \(\hat{x}\). Once the multiplier vector \(\lambda\) is obtained the remaining test (A7) for normal growth is almost for free so that we have a polynomial minimality criterion provided LIKQ holds. Otherwise one may assume a weaker generalization of the Mangasarian Fromovitz constrained qualification called MFKQ in [25].