# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 4 Computation of Generalized Gradients and Constructive Oracle Paradigm  
For optimization by variants of the DCA algorithm [17] one needs generalized gradients of the convex and the concave component. Normally, there are no strict rules for propagating generalized gradients through nonsmooth evaluation procedures. However, exactly this is simply assumed in the frequently invoked oracle paradigm, which states that at any point \(x\in\mathbb{R}^{n}\) the function value \(f(x)\) and an element \(g\in\partial f(x)\) can be evaluated. We have argued in [18] that this is not at all a reasonable assumption. On the other hand, it is well understood that for the convex operations: Positive scaling, addition, and taking the maximum the rules are strict and simple. Moreover, then the generalized gradient in the sense of [PERSON] \(\partial\widetilde{f}(x)\subset\mathbb{R}^{n}\) is actually a subdifferential in that all its elements define supporting hyperplanes. Similarly \(\partial\widetilde{f}(x)\) might be called a superdifferential in that the tangent planes bound the concave part from above. In other words, we have at all \(x\in\mathbb{R}^{n}\) and for all increments \(\Delta x\)  
\[\widetilde{f}(x+\Delta x)\ \geqslant\ \widetilde{f}(x)+\widetilde{g}^{\top} \Delta x\quad\text{if}\quad\widetilde{g}\in\partial\widetilde{f}(x)\]  
and  
\[\widehat{f}(x+\Delta x)\ \leqslant\ \widehat{f}(x)+\widetilde{g}^{\top} \Delta x\quad\text{if}\quad\widehat{g}\in\partial\widehat{f}(x)\,\]  
which imply for \(\widetilde{g}\in\partial\widetilde{f}(x)\) and \(\widehat{g}\in\partial\widehat{f}(x)\) that  
\[\widehat{f}(x+\Delta x)+\widetilde{f}(x)+\widetilde{g}^{\top} \Delta x\leqslant 2f(x+\Delta x)\leqslant\widetilde{f}(x+\Delta x)+ \widehat{f}(x)+\widehat{g}^{\top}\Delta x\, \tag{29}\]  
where the lower bound on the left is a concave function and the upper bound is convex, both with respect to \(\Delta x\). Notice that the generalized superdifferential \(\partial\widehat{f}\) being the negative of the subdifferential of \(-\widehat{f}\) is also a convex set. Now the key question is how we can calculate a suitable pair of generalized gradients \((\widetilde{g},\widehat{g})\in\partial\widetilde{f}(x)\times\partial\widehat {f}(x)\). As we noted above the convex part and the negative of the concave part only undergo convex operations so that for \(v=c\,u\)  
\[\partial\widetilde{v}=\begin{cases}c\ \partial\widetilde{u}&\text{if}\ \ c>0\\ 0&\text{if}\ \ c=0\quad\text{and}\quad\partial\widehat{v}= \begin{cases}c\ \partial\widehat{u}&\text{if}\ \ c>0\\ 0&\text{if}\ \ c=0\\ c\ \partial\widehat{u}&\text{if}\ \ c<0\end{cases}  \tag{30}\]  
and for \(v=u+w\)  
\[\partial\widetilde{v}\ =\ \partial\widetilde{u}+\partial\widetilde{w}\quad \text{and}\quad\partial\widehat{v}\ =\ \partial\widehat{u}+\partial\widehat{w}. \tag{31}\]  
Finally, for \(v=|u|\) we find by Equation (6) that \(\partial\widehat{v}=\partial\widehat{u}-\partial\widetilde{u}\) as well as  
\[\tfrac{1}{2}\partial\widetilde{v}=\partial\max(\widetilde{u},-\widehat{u}) \ =\ \begin{cases}\partial\,\widetilde{u}&\text{if}\ \ u>0\\ \operatorname{conv}\{\widehat{c}\widehat{u}\cup(-\widehat{v}\widehat{u})\}& \text{if}\ \ u=0\\ -\partial\widehat{u}&\text{if}\ \ u<0\end{cases} \, \tag{32}\]  
where we have used that \(u=\tfrac{1}{2}(\widetilde{u}+\widehat{u})\) in Equation (32). The sign of the arguments \(u\) of the absolute value function are of great importance, because they determine the switching structure. For this reason, we formulated the cases in terms of \(u\) rather than in the convex/concave components. The operator \(\operatorname{conv}\{\cdot\}\) denotes taking the convex hull or envelope of a given usually closed set. It is important to state that within an abs-linear representation the multipliers \(c\) will stay constant independent of the argument \(x\), even if they were originally computed as partial derivatives by an abs-linearization process and thus subject to round-off error.