# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 3 Forming and Extending the Abs-Linear Form
} \tag{26}\]  
_where furthermore \(\widehat{f}(x)\leq f(x)\leq\widetilde{f}(x)\)._The max-part of this representation is what is called a polyhedral function in the literature [15]. Since the min-part is correspondingly the negative of a polyhedral function we may also refer to Equation (26) as a DP decomposition, i.e., the difference of two polyhedral functions. We are not aware of a publication that gives a practical procedure for computing such a collection of affine functions \(\alpha_{i}+a_{i}^{\top}\!x\), \(i=1\ldots k\), and \(\beta_{j}+b_{j}^{\top}\!x\), \(j=1\ldots l\), for a given piecewise linear function \(f\). Of course the critical question is in which form the function \(f\) is specified. Here as throughout our work we assume that it is given by a sequence of abs-linear operations. Then we can quite easily compute for each intermediate variable \(v\) representations of the form  
\[v = \sum_{i=1}^{m}\max_{1\leq j\leq k_{i}}(\alpha_{ij}\!+\!a_{ij}^{ \top}\!x)\ +\ \sum_{i=1}^{n}\min_{1\leq j\leq l_{i}}(\beta_{ij}\!+\!b_{ij}^{\top}\!x) \tag{27}\] \[= \max_{ \begin{subarray}{c}j\in I_{i}\\ 1\leq i\leq m\end{subarray} }\sum_{i=1}^{m}(\alpha_{ij_{i}}\!+\!a_{ij_{i}}^{ \top}\!x)+\min_{ \begin{subarray}{c}j\in I_{i}\\ 1\leq i\leq n\end{subarray} }\sum_{i=1}^{n}(\beta_{ij_{i}}\!+\!b_{ij_{i}}^{ \top}\!x). \tag{28}\]  
with index sets \(I_{i}=\{1,\ldots,k_{i}\},1\leq i\leq m\), and \(J_{i}=\{1,\ldots,l_{i}\},1\leq i\leq n\), since one has to consider all possibilities of selecting one affine function each from one of the \(m\) max and \(n\) min groups, respectively. Obviously, (28) involves \(\prod_{i=1}^{m}k_{i}\) and \(\prod_{i=1}^{n}\ell_{i}\) affine function terms in contrast to the first representation (27) which contains just \(\sum_{i=1}^{m}k_{i}\) and \(\sum_{i=1}^{n}\ell_{i}\) of them. Still the second version conforms to the classical representation of convex and concave piecewise linear functions, which yields the following result:  
**Corollary 3** (Explicit computation of the DP representation). : _For any piecewise linear function given as abs-linear procedure one can explicitly compute the representation (26) by implementing the rules of Lemma 1._  
Proof. : We will consider the representations (27) from which (26) can be directly obtained in the form (28). Firstly, the independent variables \(x_{j}\) are linear functions of themselves with gradient \(a=e_{j}\) and inhomogeneity \(\alpha=0\). Then for multiplications by a constant \(c>0\) we have to scale all affine functions by \(c\). Secondly, addition requires appending the expansions of the two summands to each other without any computation. Taking the negative requires switching the sign of all affine functions and interchanging the max and min group. Finally, to propagate through the absolute values we have to apply the rule (6), which means switching the signs in the min group, expressing it in terms of max and merging it with the existing max group. Here merging means pairwise joining each polyhedral term of the old max-group with each term in the switched min-group. Then the new min-group is the old one plus the old max-group with its sign switched. We see that taking the absolute value or, alternatively, maxima or minima generates the strongest growth in the number of polyhedral terms and their size. It seems clear that this representation is generally not very useful because the number of terms will likely blow up exponentially. This is not surprising because we will need one affine function for each element of the polyhedral decompositions of the domain of the max and min term. Typically, many of the affine terms will be redundant, i.e., could be removed without changing the values of the polyhedral terms. Unfortunately, identifying those already requires solving primal or dual linear programming problems, see, e.g., [16]. It seems highly doubtful that this would ever be worthwhile. Therefore, we will continue to advocate dealing with piecewise linear functions in a convenient procedural abs-linear representation.