# Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions
## 5 Exploiting the Convex/concave Decomposition for the DC Algorithm  
In order to minimize the decomposed objective function \(f\) we may use the DCA algorithm [17] which is given in its basic form using our notation by  
Choose  
\[x_{0}\in\mathbb{R}^{n}\]  
For  
\[k=0,1,2,\ldots\]  
Calculate  
\[g_{k}\in-\partial\big{(}\frac{1}{2}\widehat{f}\big{)}(x_{k})\]  
Calculate  
\[x_{k+1}\in\partial\big{(}\frac{1}{2}\widehat{f}\big{)}^{*}(g_{k})\]  
where \(\big{(}\frac{1}{2}\widetilde{f}\big{)}^{*}\) denotes the Fenchel conjugate of \(\big{(}\frac{1}{2}\widetilde{f}\big{)}\). For a convex function \(h:\mathbb{R}^{n}\mapsto\mathbb{R}\) one has  
\[w\in\partial h^{*}(y)\quad\Leftrightarrow\quad w\in\operatorname*{argmin}_{x \in\mathbb{R}^{n}}\{h(x)-y^{\top}x\},\]  
see [15], Chapter 11. Hence, the classic DCA reduces in our Euclidean scenario to a simple recurrence  
\[x_{k+1}\in\operatorname*{argmin}_{x\in\mathbb{R}^{n}}\left\{\widetilde{f}(x) +\widehat{g}_{k}^{\top}x\right\}\quad\text{for some}\quad\widehat{g}_{k}\in \partial\widehat{f}(x_{k}). \tag{36}\]  
The objective function on the left hand side is a constantly shifted convex polyhedral upper bound on \(2f(x)\) since  
\[\widetilde{f}(x)+\widehat{g}_{k}^{\top}x=2f(x)-\left(\widehat{f}(x)-\widehat{ g}_{k}^{\top}x\right)\geq 2f(x)-\widehat{f}(x_{k})+\widehat{g}_{k}^{\top}x _{k}. \tag{37}\]  
It follows from Equation (29) and \(x_{k+1}\) being a minimizer that  
\[f(x_{k+1}) \leq \tfrac{1}{2}\left(\widetilde{f}(x_{k+1})+\widehat{f}(x_{k})+ \widehat{g}_{k}^{\top}(x_{k+1}-x_{k})\right)\] \[\leq \tfrac{1}{2}\left(\widetilde{f}(x_{k})+\widehat{f}(x_{k})\right) \ =\ f(x_{k})\.\]  
Now, since (36) is an LOP, an exact solution \(x_{k+1}\) can be found in finitely many steps, for example by a variant of the Simplex method. Moreover, we can then assume that \(x_{k+1}\) is one of finitely many vertex points of the epigraph of \(\widetilde{f}\). At these vertex points, \(f\) itself attains a finite number of bounded values. Provided \(f\) itself is bounded below, we can conclude that for any choice of the \(\widehat{g}_{k}\in\partial\widehat{f}_{\sigma^{(k)}}\) the resulting function values \(f(x_{k})\) can only be reduced finitely often so that \(f(x_{k})=f(x_{k-1})\) and w.l.o.g \(x_{k}=x_{k-1}\) eventually. We then choose the next \(\widehat{g}_{k}=\
abla\widehat{f}_{\sigma^{(k)}}\) with \(\sigma^{(k)}=\sigma^{(k-1)}\rhd\sigma(x_{k})\) as the reflection of \(\sigma^{(k-1)}\) at \(\sigma(x_{k})\) as defined in (15). If then again \(f(x_{k+1})=f(x_{k})\) it follows from Corollary A2 that \(x_{k}\) is a local minimizer of \(f\) and we may terminate the optimization run. Hence we obtain the DCA variant listed in Algorithm 1, which is guaranteed to reach local optimality under LIKQ. It is well defined even without this property and we conjecture that otherwise the final iterate is still a stationary point of \(f\). The path of the algorithm on the example discussed in Section 5 is sketched in Figure 3. It reaches the stationary point \((0,-1)\) where \(\sigma=(0,-1,0)\) from within the polyhedron with the signature \((-1,-1,-1)\) and then continues after the reflection \((1,-1,1)=(-1,-1,-1)\rhd(0,-1,0)\). From within that polyhedron the inner loop reaches the point \((1,1)\) with signature \((1,0,0)\), whose minimality is established after a search in the polyhedron \(\widetilde{\mathcal{P}}_{(1,1,-1)}\). If the function \(f(x)\) is unbounded below, so will be one of the inner convex problems and the convex minimizer should produce a ray of infinite descent instead of the next iterate \(x_{k+1}\). This exceptional scenario will not be explicitly considered in the remainder of the paper. The reflection operation is designed to facilitate further descent or establish local optimality. It is discussed in the context of general optimality conditions in the following subsection.