# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 2 Propagating Bounds and/or Radii  
In Equation (3) we already assumed that doubling is done componentwise and that for a difference \(v=w-u\) of DC functions \(w\) and \(u\), one defines the convex and concave parts by  
\[\widetilde{(w-u)}=\widetilde{w}-\widehat{u}\qquad\text{and}\qquad\widehat{(w -u)}=\widehat{w}-\widetilde{u}\,\]  
respectively. This yields in particular for the negation  
\[\widetilde{(-u)}=-\widehat{u}\quad\text{and}\quad\widehat{(-u)}=-\widetilde {u}. \tag{4}\]  
For piecewise linear functions we need neither the square formula Equation (2) nor the more general decompositions for products. Therefore we will not insist on the sign conditions even though they would be also maintained automatically by Equation (4) as well as the natural linear rules for the convex and concave parts of the sum and the multiple of a DC function, namely  
\[\widetilde{(w+u)} =(\widetilde{w}+\widetilde{u})\qquad\qquad\text{and}\qquad \widehat{(w+u)} =(\widehat{w}+\widehat{u})\,\] \[\widetilde{(c\,u)} =c\,\widehat{u}\qquad\qquad\qquad\text{and}\qquad\qquad \widehat{(c\,u)} =c\,\widehat{u}\qquad\quad\text{if}\quad c\geq 0\,\] \[\widetilde{(c\,u)} =c\,\widehat{u}\qquad\qquad\text{and}\qquad\qquad\widehat{(c\,u )} =c\,\widetilde{u}\qquad\quad\text{if}\quad c\leq 0\.\]  
However, the sign conditions would force one to decompose simple affine functions \(u(x)=a^{\top}x+\beta\) as  
\[u(x)\ =\ \max(0,a^{\top}x+\beta)+\min(0,a^{\top}x+\beta)\ =\ \tfrac{1}{2}( \widetilde{u}(x)+\widehat{u}(x))\, \tag{5}\]  
which does not seem such a good idea from a computational point of view. The key observation for this paper is that as is well known (see e.g., [8]), one can propagate the absolute value operation according to the identity  
\[|u| = \max(u,-u)=\tfrac{1}{2}\max(\widetilde{u}+\widehat{u},-\widetilde {u}-\widehat{u}) \tag{6}\] \[= \max(\widetilde{u},-\widehat{u})+\tfrac{1}{2}(\widehat{u}- \widetilde{u})\] \[\Longleftrightarrow \widetilde{|u|}=2\max(\widetilde{u},-\widehat{u})\quad\text{and} \quad\widehat{|u|}=\widehat{u}-\widetilde{u}\.\]  
Here the equality in the second line can be verified by shifting the difference \(\tfrac{1}{2}(\widehat{u}-\widetilde{u})\) into the two arguments of the max. Again we see that when applying the absolute value operation to an already positive convex function \(u=\tfrac{1}{2}\widetilde{u}\geq 0\) we get \(|\widetilde{u}|=2\widetilde{u}\) and \(|\widetilde{u}|=-\widetilde{u}\) so that the condition number grows from \(\kappa(\widetilde{u},0)=1\) to \(\kappa(2\widetilde{u},-\widetilde{u})=3\). In other words, we observe once more the danger that both component functions drift apart. This looks a bit like simultaneous growth of numerator and denominator in rational arithmetic, which can sometimes be limited through cancelations by common integer factors. It is currently not clear when and how a similar compactification of a given convex/concave decomposition can be achieved. The corresponding rule for the maximum is similarly easy derived, namely  
\[\max(u,w)=\tfrac{1}{2}\max(\widetilde{u}+\widehat{u},\widetilde{w}+\widehat{w} )=\tfrac{1}{2}\left(\max(\widetilde{u}-\widehat{w},\widetilde{w}-\widehat{u}) +(\widehat{u}+\widehat{w})\right)\.\]  
When \(u\) and \(w\) as well as their decomposition are identical we arrive at the new decomposition \(u=\max(u,u)=\tfrac{1}{2}((\widetilde{u}-\widehat{u})+2\widehat{u})\), which obviously represents again some deterioration in the conditioning. While it was pointed out in [4] that the DC functions \(u=\tfrac{1}{2}(\widetilde{u}+\widehat{u})\) themselves form an algebra, their decomposition pairs \((\widetilde{u},\widehat{u})\) are not even an additive group, as only the zero \((0,0)\) has a negative partner, i.e., an additive inverse. Naturally, the pairs \((\widetilde{u},\widehat{u})\) form the Cartesian product between the convex cone of convex functions and its negative, i.e., the cone of concave functions. The DC functions are then the linear envelope of the two cones in some suitable space of locally Lipschitz continuous functions.