# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 4 Computation of Generalized Gradients and Constructive Oracle Paradigm
In particular their sign will remain fixed throughout whatever algorithmic calculation we perform involving the piecewise linear function \(f\). So, actually the case \(c=0\) could be eliminated by dropping this term completely and just initializing the left hand side \(v\) to zero. Because we have set identities we can propagate generalized gradient pairs \((\
abla\vec{u},\
abla\vec{u})\in\partial\vec{u}\times\partial\vec{u}\) and perform the indicated algebraic operations on them, starting with the Cartesian basis vectors  
\[\
abla\vec{x}_{j}=\
abla\vec{x}_{j}=\
abla x_{j}=e_{j}\ \ \text{since}\ \ \vec{x}_{j}=\vec{x}_{j}=x_{j}\ \ \text{for}\ \ j=1\ldots n\.\]  
The result of this propagation is guaranteed to be an element of \(\partial\vec{f}\times\partial\vec{f}\). Recall that in the merely Lipschitz continuous case generalized gradients cannot be propagated with certainty since for example the difference \(v=w-u\) generates a proper inclusion \(\partial v\subset\partial w-\partial u\). In that vein we must emphasize that the average \(\frac{1}{2}(\
abla\vec{f}+\
abla\widehat{f})\) need not be a generalized gradient of \(f=\frac{1}{2}(\vec{f}+\widehat{f})\) as demonstrated by the possibility that \(\widehat{f}=-\vec{f}\) algebraically but we happen to calculate different generalized gradients of \(\vec{f}\) and \(-\widehat{f}\) at a particular point \(x\). In fact, if one could show that \(\partial f=\frac{1}{2}(\partial\vec{f}+\partial\widehat{f})\) one would have verified the oracle paradigm, whose use we consider unjustified in practice. Instead, we can formulate another corollary for sufficiently piecewise smooth functions. **Definition 1**. : _For any \(d\in\mathbb{N}\), the set of functions \(f:\mathbb{R}^{n}\mapsto\mathbb{R},y=f(x)\), defined by an abs-normal form_  
\[z = F(x,z,|z|)\,\] \[y = \varphi(x,z),\]  
_with \(F\in\mathcal{C}^{d}(\mathbb{R}^{n+s+s})\) and \(\varphi\in\mathcal{C}^{d}(\mathbb{R}^{n+s})\), is denoted by \(\mathcal{C}^{d}_{\mathrm{abs}}(\mathbb{R}^{n})\)._  
Once more, this definition differs slightly from the one given in [7] in that \(y\) depends only on \(z\) and not on \(|z|\) in order to match the abs-linear form used here. Then one can show the following result:  
**Corollary 4** (Constructive Oracle Paradigm). : _For any function \(f\in\mathcal{C}^{2}_{\mathrm{abs}}(\mathbb{R}^{n})\) and a given point \(x\) there exist a convex polyhedral function \(\widetilde{\Delta f}(x;\Delta x)\) and a concave polyhedral function \(\widehat{\Delta f}(x;\Delta x)\) such that_  
\[f(x+\Delta x)-f(x)\ =\ \tfrac{1}{2}\left(\widetilde{\Delta f}(x;\Delta x)+ \widehat{\Delta f}(x;\Delta x)\right)+\mathcal{O}(\|\Delta x\|^{2})\]  
_Moreover, both terms and their generalized gradients at \(\Delta x=0\) or anywhere else can be computed with the same order of complexity as \(f\) itself._  
Proof. : In [11], we show that  
\[f(x+\Delta x)-f(x)=\Delta f(x;\Delta x)+\mathcal{O}(\|\Delta x\|^{2})\,\]  
where \(\Delta f(x;\Delta x)\) is a piecewise linearization of \(f\) developed at \(x\) and evaluated at \(\Delta x\). Applying the convex/concave decomposition of Theorem 1, one obtains immediately the assertion with a convex polyhedral function \(\widehat{\Delta f}(x;\Delta x)\) and a concave polyhedral function \(\widehat{\Delta f}(x;\Delta x)\) evaluated at \(\Delta x\). The complexity results follow from the propagation rules derived so far. We had hoped that it would be possible to use this approximate decomposition into polyhedral parts to construct at least locally an exact decomposition of a general function \(f\in\mathcal{C}^{d}_{\mathrm{abs}}(\mathbb{R}^{n})\) into a convex and compact part. The natural idea seems to add a sufficiently large quadratic term \(\beta\|\Delta x\|^{2}\) to  
\[f(x+\Delta x)-f(x)-\tfrac{1}{2}\widehat{\Delta f}(x;\Delta x)=\tfrac{1}{2} \widetilde{\Delta f}(x;\Delta x)+\mathcal{O}(\|\Delta x\|^{2})\]  
such that it would become convex. Then the same term could be subtracted from \(\widehat{\Delta f}(x;\Delta x)\) maintaining its concavity.