# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 5 Exploiting the Convex/concave Decomposition for the DC Algorithm
### Checking Optimality Conditions  
Stationarity of \(x_{k}\) happens when the convex function \(\widetilde{f}(x)+\widehat{g}_{k}^{\top}x\) is minimal at \(x_{k}\) so that for all large \(k\)  
\[0\in\partial\widetilde{f}(x_{k})+\widehat{g}_{k}\;\;\Longleftrightarrow\; \;\widehat{g}_{k}\in\partial\widehat{f}(x_{k})\;\cap\;(-\partial\widetilde{f}( x_{k}))\
eq\emptyset\;\;. \tag{38}\]  
The nonemptiness condition on the right hand side is known as criticality of the DC decomposition at \(x_{k}\), which is necessary but not sufficient even for local optimality of \(f(x)\) at \(x_{k}\). To ensure the latter one has to verify that all \(\widehat{g}_{k}\in\partial\widehat{f}(x_{k})\) satisfy the criticality condition (38) so that  
\[\partial\widehat{f}(x_{k})\;\subset\;-\partial\widetilde{f}(x_{k})\;\; \Longleftrightarrow\;\;\partial^{\perp}\widehat{f}(x_{k})\;\subset\;- \partial\widetilde{f}(x_{k})\;. \tag{39}\]  
The left inclusion is a well known local minimality condition [22], which is already sufficient in the piecewise linear case. The right inclusion is equivalent to the left one due to the convexity of \(\partial\widetilde{f}(x_{k})\).  
If \(\widetilde{f}\) and \(\widehat{f}\) were unrelated convex and concave polyhedral functions, one would normally consider it extremely unlikely that \(\widehat{f}\) were nonsmooth at any one of the finitely many vertices of the polyhedral domain decomposition of \(\widetilde{f}\). For instance when \(\widehat{f}\) is smooth at \(x_{k}\) we find that \(\partial\widehat{f}(x_{k})=\{\widehat{g}_{k}\}\) is a singleton so that criticality according to Equation (38) is already sufficient for local minimality according to Equation (39). As we have seen in Theorem 1 the two parts have exactly the same switching structure. That means they are nonsmooth on the same skeleton of lower dimensional polyhedra. Hence, neither \(\partial^{\perp}\widetilde{f}(x_{k})\) nor \(\partial^{\perp}\widetilde{f}(x_{k})\) will be singletons at minimizing vertices of the upper bound so that checking the validity of Equation (39) appears to be a combinatorial task at first sight.  
However, provided the Linear Independence Kink Qualification (LIKQ) defined in [7] is satisfied at the candidate minimizer \(x_{k}\), the minimality can be tested with cubic complexity even in case of a dense abs-linear form. Moreover, if the test fails one can easily calculate a descent direction \(d\). The details of the optimality test in our context including the calculation of a descent direction are given in the Appendix A. They differ slightly from the ones in [7]. Rather than applying the optimality test Proposition A1 explicitly, one can use its Corollary A2 stating that if \(\hat{x}\) with \(\hat{\sigma}=\sigma(\hat{x})\) is a local minimizer of the restriction of \(f\) to a polyhedron \(\widetilde{\mathcal{P}}_{\sigma}\) with definite \(\sigma>\hat{\sigma}\) then it is a local minimizer of the unrestricted \(f\) if and only if it also minimizes the restriction of \(f\) to \(\widetilde{\mathcal{P}}_{\sigma}\) with the reflection \(\hat{\sigma}=\sigma\rhd\hat{\sigma}\). The latter condition must be true if \(\hat{x}\) also minimizes \(f(x)+\
abla\widehat{f}_{\sigma}\), which can be checked by solving that convex problem. If that test fails the optimization can continue.