# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 6 [PERSON]'s Piecewise Linear Example  
According to [6], [PERSON] suggested three Rosenbrock-like test functions for nonsmooth optimization. One of them given by  
\[f(x)=\tfrac{1}{4}\ |x_{1}-1|\ +\ \sum_{i=1}^{n-1}|x_{i+1}-2|x_{i}|+1| \tag{40}\]  
is nonconvex and piecewise linear. It is shown in [6] that this function has \(2^{n-1}\) Clarke stationary points only one of which is a local and thus the global minimizer. Numerical studies showed that optimization algorithms tend to be trapped at one of the stationary points making it an interesting test problem. We have demonstrated in [23] that using an active signature strategy one can guarantee convergence to the unique minimizer from any starting point albeit using in the worst case \(2^{n}\) iterations as all stationary points are visited. Let us first write the problem in the new abs-linear form. Defining the \(s=2\,n\) switching variables  
\[z_{i}=F_{i}(x,|z|)=x_{i}\quad\text{for}\quad 1\leq i<n,\qquad z_{n}=F_{n}(x,|z|)=x _{1}-1,\]  
and  
\[z_{n+i}=F_{n+i}(x,|z|)=x_{i+1}-2\,|z_{i}|+1\text{ for }1\leq i<n,\quad z_{s}= \tfrac{1}{4}|z_{n}|+\sum_{i=1}^{n-1}|z_{n+i}|\]the resulting objective function is then simply identical to \(y=f(x)=z_{s}\). With the vectors and matrices  
\[c^{\top}=(0,-1,e_{n-1}^{\top},0)\in\mathbb{R}^{(n-1)+1+(n-1)+1},\ Z= \begin{bmatrix} I_{n-1}&0\\ I_{n-1}&0\\ 0&1\\ 0&0\end{bmatrix} \in\mathbb{R}^{s\times(n-1)+1}\,\]  
\[M=0\,\ L= \begin{bmatrix}0&0&0&0\\ 0&0&0&0\\ -2\ I_{n-1}&0&0&0\\ 0&\frac{1}{4}&e_{n-1}^{\top}&0\end{bmatrix} \in\mathbb{R}^{s\times(n-1)+1+(n-1)+ 1}\,\ d=0\in\mathbb{R},\]  
\[a=0\,\ b^{\top}=(0,\cdots,0,1)\in\mathbb{R}^{(2n-1)+1}\,\]  
where \(Z\) and \(L\) have different row partitions, one obtains an abs-linear form (11) of \(f\). Here, \(I_{k}\) denotes the identity matrix of dimension \(k\), \(e^{\top}=(1,\cdots,1)\in\mathbb{R}^{k}\) the vector containing only ones and the symbol \(0\) pads with zeros to achieve the specified dimensions. One can easily check that \(|L|^{2}\
eq 0=|L|^{3}\), hence this example has switching depth \(v=2\). The geometry of the situation is depicted in Figure 3, which was already briefly discussed in Sections 3 and 5. Since the corresponding extended abs-linear form for \(\tilde{f}=(y,\delta y)\) does not provide any new insight we do not state it here. Directly in terms of the original equations we obtain for the radii  
\[\delta z_{i}=0\ \ \text{for}\ \ 1\leqslant i\leqslant n,\quad\delta z_{n+i}=2| z_{i}|\ =\ 2|x_{i}|\ \ \text{for}\ \ 1\leqslant i<n \tag{41}\]  
and  
\[\delta f=\delta z_{s} = \tfrac{1}{4}|z_{n}|+\sum_{i=1}^{n-1}(|z_{n+i}|+2\delta z_{n+i}) \tag{42}\] \[= \tfrac{1}{4}|x_{1}-1|+\sum_{i=1}^{n-1}(|x_{i+1}-2\,|x_{i}|+1|+4|x _{i}|)\.\]  
Thus, from Equation (7) we get the convex and concave part explicitly as  
\[\left. \begin{aligned} \widetilde{z}_{i}&=z_{i}&=\widehat{z}_{i} \ \ \text{for}\ \ 1\leqslant i\leqslant n\,\\ \widetilde{z}_{n+i}&=x_{i+1}+1\\ \widehat{z}_{n+i}&=x_{i+1}-4|z_{i}|+1=x_{i+1}-4|x_{i}|+1 \end{aligned} \right\}\ \ \text{for}\ \ 1\leqslant i<n\]  
and most importantly  
\[\left. \begin{aligned} \widetilde{f}=z_{s}+\delta z_{s}& =\tfrac{1}{2}|x_{1}-1|+2\sum_{i=1}^{n-1}\left(|x_{i+1}-2\,|x_{i}|+1| +2|x_{i}|\right)\\ \widehat{f}=z_{s}-\delta z_{s}&=-4\sum_{i=1}^{n-1}|x_{i}|. \end{aligned} \right.\]  
Clearly \(\widehat{f}\) is a concave function and to check the convexity of \(\widetilde{f}\) we note that  
\[|x_{i+1}-2\,|x_{i}|+1|+2|x_{i}| = |2\,|x_{i}|\ -1-x_{i+1}|+\big{(}2|x_{i}|-1-x_{i+1}\big{)}+x_{i+1}+1 \tag{43}\] \[= 1+x_{i+1}+2\max\left(0,2|x_{i}|-x_{i+1}-1\right)\.\]  
The last expression is the sum of an affine function and the positive part of the sum of the absolute value and an affine function, which must therefore also be convex. The corresponding term in Equation (42) is the same with the convex function \(2|x_{i}|\) added, so that \(\delta f\) is also convex in agreement with the general theory.