# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 1 Introduction and Notation
#### Conditioning of the Decomposition  
In parts of the literature the two convex functions \(\widetilde{f}\) and \(-\widehat{f}\) are assumed to be nonnegative, which has some theoretical advantages. In particular, see, e.g., [4], one obtains for the square \(h=f^{2}\) of a DC function \(f\) the decomposition  
\[h\ =\ \tfrac{1}{4}(\widetilde{f}+\widehat{f})^{2}\ =\ \tfrac{1}{2}\{\,\frac{1}{ \,\underline{1}\,(\widetilde{f}^{2}+\widehat{f}^{2})}{\equiv h}+\tfrac{1}{4}[ -(\widetilde{f}-\widehat{f})^{2}]\,\}. \tag{2}\]  
The sign conditions of \(\widetilde{f}\) and \(\widehat{f}\) are necessary to ensure that the three squares on the right hand side are convex functions. Using the Apollonius identity \(f\cdot h=\tfrac{1}{2}[(f+h)^{2}-f^{2}-h^{2}]\) one may then deduce in a constructive way that not only sums but also products of DC functions inherit this property. In general, since the convex functions \(\widetilde{f}\) and \(-\widehat{f}\) have both supporting hyperplanes one can at least theoretically always find positive coefficients \(\alpha\) and \(\beta\) such that  
\[\widetilde{f}(x)+\alpha+\beta\|x\|^{2}\quad\geqslant\quad 0\quad\geqslant\quad \widehat{f}(x)-\alpha-\beta\|x\|^{2}\qquad\text{for}\quad x\in\mathbb{R}^{n}\.\]  
Then the average of these modified functions is still \(f\) and their respective convexity/concavity properties are maintained. In fact, this kind of proximal shift can be used to show that any twice Lipschitz continuously differentiable function is DC, which raises the suspicion that the property by itself does not provide all that much exploitable structure from a numerical point of view. We believe that for its use in practical algorithms one has to make sure or simply assume that the condition number  
\[\kappa(\widetilde{f},\widehat{f})\ =\ \sup_{x\in\mathbb{R}^{n}}\frac{| \widetilde{f}(x)|+|\widehat{f}(x)|}{|\widetilde{f}(x)+\widehat{f}(x)|}\in[1,\infty]\]  
is not too large. Otherwise, there is the danger that the value of \(f\) is effectively lost in the rounding error of evaluating \(\widetilde{f}+\widehat{f}\). For sufficiently large quadratic shifts of the nature specified above one has \(\kappa\sim\beta\). The danger of an excessive growth in \(\kappa\) seems akin to the successive widening in interval calculations and similarly stems also from the lack of strict arithmetic rules. For example doubling \(f\) and then subtracting it yields the successive decompositions  
\[(2f)-f=(\widetilde{f}+\widehat{f})-\tfrac{1}{2}(\widetilde{f}+\widehat{f})=( \widetilde{f}-\tfrac{1}{2}\widehat{f})+(\widehat{f}-\tfrac{1}{2}\widetilde{f })=\tfrac{1}{2}[(2\widetilde{f}-\widehat{f})+(2\widehat{f}-\widetilde{f})]. \tag{3}\]  
If in Equation (3) by chance we had originally \(-\widehat{f}=\tfrac{1}{2}\widetilde{f}>0\) so that \(f=\tfrac{1}{2}\widetilde{f}\) with the condition number \(\kappa(\widetilde{f}_{\cdot}-0.5\widetilde{f})=3\) we would get after the doubling and subtraction the condition number \(\kappa(2.5\widetilde{f}_{\cdot}-2\widetilde{f})=9\). So it is obviously important that the original algorithm avoids as much as possible calculations that are ill-conditioned in that they even just partly compensate each other. Throughout the paper we assume that the functions in question are evaluated by a computational procedure that generates a sequence of intermediate scalars, which we denote generically by \(u,v\) and \(w\). The last one of these scalar variables is the dependent, which is usually denoted by \(f\). All of them are continuous functions \(u=u(x)\) of the vector \(x\in\mathbb{R}^{n}\) of independent variables. As customary in mathematics we will often use the same symbol to identify a function and its dependent variable. For the overall objective we will sometimes distinguish them and write \(y=f(x)\). For most of the paper we assume that the intermediates are obtained from each other by affine operations or the absolute value function so that the resulting \(u(x)\) are all piecewise linear functions. The paper is organized as follows.