# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 7 Summary, Conclusions and Outlook  
In this paper the following new results were achieved  
* For every piecewise linear function \(f\) given as an abs-linear evaluation procedure, rules for simultaneously evaluating its representation as the average of a concave lower bound \(\widehat{f}\) and a convex upper bound \(\widetilde{f}\) are derived. * The two bounds can be constructively expressed as a single maximum and minimum of affine functions, which drastically simplifies the classical \(\min-\max\) representation. Due to its likely combinatorial complexity we do not recommend this form for practical calculations. * For the two bounds \(\widetilde{f}\) and \(\widehat{f}\), generalized gradients \(\widetilde{g}\) and \(\widehat{g}\) can be propagated forward or reverse through the convex or concave operations that define them. The gradients are not unique but guaranteed to yield supporting hyperplanes and thus provide a verified version of the oracle paradigm. * The DCA algorithm can be implemented such that a local minimizer is reached in finitely many iterations, provided the Linear Independence Kink Qualification (LIKQ) is satisfied. It is conjectured that without this assumption the algorithm still converges in finitely many steps to a Clarke stationary point. Details on this can be found in the companion paper [24]. These results are illustrated on the piecewise linear Rosenbrock variant of Nesterov. On a theoretical level it would be gratifying and possibly provide additional insight, to prove the result of Corollary A3 directly using the explicit representations of the generalized differentials of the convex and concave part given in Corollary 1. Moreover, it remains to be explored what happens when LIKQ is not satisfied. We have conjectured in [25] that just verifying the weaker Mangasarian Fromovitz Kink Qualification (MFKQ) represents an NP hard task. Possibly, there are other weaker conditions that can be cheaply verified and facilitate the testing for at least local optimality. Figure 3: Signatures and reflection-based DCA for Nesterov–Rosenbrock variant (40) with \(n=2\). Global optimality can be characterized theoretically in terms of \(\varepsilon-\)subgradients, albeit with \(\varepsilon\) arbitrarily large [26]. There is the possibility that the alternative definition of \(\varepsilon\)-gradients given in [18] might allow one to constructively check for global optimality. It does not really seem clear how these global optimality conditions can be used to derive corresponding algorithms. The implementation of the DCA algorithm can be optimized in various ways. Notice that for applying the Simplex method in standard form, one could use for the representation as DC function the max-part in the more economical representation Equation (27) introducing \(\vec{m}\) additional variables, rather than the potentially combinatorial Equation (28) to assemble the constraint matrix. In any case it seems doubtful that solving each sub problem to completion is a good idea, especially as the resulting step in the outer iteration is probably much too small anyhow. Therefore, the generalized gradient of the concave part, which defines the inner problem, should probably be updated much more frequently. Moreover, the inner solver might be an SQOP type active signature method or a matrix free gradient method with momentum term, as is used in machine learning, notwithstanding the nonsmoothness of the objective. Various options in that range will be discussed and tested in the companion article [24]. Finally, one should always keep in mind that the task of minimizing a piecewise linear function will most likely occur as an inner problem in the optimization of a piecewise smooth and nonlinear function. As we have shown in [27] the local piecewise linear model problem can be obtained easily by a slight generalization of automatic or algorithmic differentiation, e.g., ADOL-C [28] and Tapenade [29]. Conceptualization, A.G. and A.W. ; methodology, A.G. and A.W.