# Bundle Enrichment Method for Nonsmooth Difference of Convex Programming Problems
## 2 Notations and Background  
First, we provide some notations and definitions that we will use throughout the paper. The inner product in \(\mathds{R}^{n}\) is \(\langle u,v\rangle=\sum_{i=1}^{n}u_{i}v_{i}\), and \(\|\cdot\|\) is the associated norm. For \(x\in\mathds{R}^{n}\) and \(\varepsilon>0\), \(B(x;\varepsilon)\) is an open ball of the radius \(\varepsilon>0\) centered at \(x\). The function \(f:\mathds{R}^{n}\to\mathds{R}\) is locally Lipschitz continuous on \(\mathds{R}^{n}\) if for every \(x\in\mathds{R}^{n}\), there exists a Lipschitz constant \(L>0\) and \(\varepsilon>0\) such that \(|f(y)-f(z)|\leq L\|y-z\|\) for all \(y,z\in B(x;\varepsilon)\). For a convex function \(f:\mathds{R}^{n}\to\mathds{R}\), its subdifferential at a point \(x\in\mathds{R}^{n}\) is [38; 41]  
\[\partial f(x)=\Big{\{}\xi\in\mathds{R}^{n}:\,f(y)-f(x)\geq\langle\xi,y-x\rangle \quad\text{for all }y\in\mathds{R}^{n}\Big{\}},\]  
and for \(\varepsilon>0\), its \(\varepsilon\)-subdifferential is  
\[\partial_{\varepsilon}f(x)=\Big{\{}\xi_{\varepsilon}\in\mathds{R}^{n}:\,f(y) -f(x)\geq\langle\xi_{\varepsilon},y-x\rangle-\varepsilon\quad\text{for all }y\in\mathds{R}^{n}\Big{\}}.\]Each vector \(\xi\in\partial f(x)\)\(\big{(}\xi_{\varepsilon}\in\partial_{\varepsilon}f(x)\big{)}\) is called a subgradient (\(\varepsilon\)-subgradient) of \(f\) at \(x\). A point \(x^{*}\in\mathds{R}^{n}\) is called a critical point of Problem (1) if  
\[\partial f_{1}(x^{*})\cap\partial f_{2}(x^{*})\
eq\emptyset,\]  
and a point \(x^{*}\in\mathds{R}^{n}\) is said to be an \(\varepsilon\)-critical point if [31]  
\[\partial_{\varepsilon}f_{1}(\tilde{x}^{*})\cap\partial_{\varepsilon}f_{2}( \tilde{x}^{*})\
eq\emptyset.\]  
Next, we recall the basic idea of the standard cutting-plane model for any convex nonsmooth function \(f\). Let \(x_{k}\in\mathds{R}^{n}\) be the current iteration point, \(x_{j}\in\mathds{R}^{n}\) be some auxiliary points (from past iterations), \(\xi_{j}\in\partial f(x_{j})\) be the subgradients of the function \(f\) computed at the point \(x_{j}\in\mathds{R}^{n}\) for \(j\in J^{k}\), and \(J^{k}\) is a nonempty subset of \(\{1,\ldots,k\}\). The cutting-plane model for the function \(f\) can be given by  
\[\tilde{f}^{k}(x)=\max_{j\in J^{k}}\tilde{f}_{j}(x),\]  
where \(\tilde{f}_{j}(x)=f(x_{j})+\langle\xi_{j},x-x_{j}\rangle\). The linearization error  
\[\alpha_{j}^{k}=f(x_{k})-\tilde{f}_{j}(x_{k})\quad\text{ for all }j\in J^{k}\]  
defines how well \(\tilde{f}_{j}\) approximates the function \(f\) at the current iteration point \(x_{k}\). In this paper, we assume that \(f\) is the DC function, and due to the lack of its convexity, the straightforward application of the cutting-plane approach is meaningless. Nevertheless, it can be separately applied to model the DC components \(f_{i},\ i=1,2\). Thus, we have  
\[\tilde{f}_{i}^{k}(x)=\max_{j\in J^{k}}\Big{\{}f_{i}(x_{j})+\langle\xi_{i,j},x- x_{j}\rangle\Big{\}}\quad\text{for }x\in\mathds{R}^{n}.\]  
Here, \(\xi_{i,j}\in\partial f_{i}(x_{j}),\ i=1,2\) are the subgradients of the DC components \(f_{i}\) computed at the auxiliary point \(x_{j}\in\mathds{R}^{n}\) for \(j\in J^{k}\). This approximation can be rewritten as  
\[\tilde{f}_{i}^{k}(x)=\max_{j\in J^{k}}\Big{\{}f_{i}(x_{k})+\langle\xi_{i,j},x -x_{k}\rangle-\alpha_{i,j}^{k}\Big{\}}, \tag{2}\]  
where \(x_{k}\in\mathds{R}^{n}\) is the current iteration point, and \(\alpha_{i,j}^{k},\ i=1,2\) are the linearization errors associated with the \(j\)-th first order expansion of \(f_{i},\ i=1,2\) rooted at the point \(x_{j}\), given by  
\[\alpha_{i,j}^{k}=f_{i}(x_{k})-f_{i}(x_{j})-\langle\xi_{i,j},x_{k}-x_{j}\rangle \quad\text{ for all }j\in J^{k}.\]  
Suppose that information coming from some auxiliary points \(x_{j}\in\mathds{R}^{n}\), \(j\in J^{k}\), along with \(\big{(}x_{k},\xi_{1,k}\in\partial f_{1}(x_{k}),\ \xi_{2,k}\in\partial f_{2}(x_{k})\big{)}\), is available. We condense all such information into a bundle set \(B^{k}\) defined as a set of tuples, one for each point \(x_{j}\).