# Bundle Enrichment Method for Nonsmooth Difference of Convex Programming Problems
## 4 The Proposed BEM-DC Algorithm
 \tag{9}\]  
Then, applying the standard duality arguments to Problem (9), we have the following primal-dual relations:  
\[d_{l}^{k}= -\frac{1}{\delta_{k}}\Big{(}\sum_{j\in J_{1}^{k}\cup T_{l}} \lambda_{j}\xi_{1,j}^{k}-\xi_{2,j^{*}}^{k}\Big{)}, \tag{10}\] \[v_{l}^{k}= -\frac{1}{\delta_{k}}\Big{\|}\sum_{j\in J_{1}^{k}\cup T_{l}} \lambda_{j}\xi_{1,j}^{k}-\xi_{2,j^{*}}^{k}\Big{\|}^{2}-\sum_{j\in J_{1}^{k} \cup T_{l}}\lambda_{j}\alpha_{1,j}^{k}+\alpha_{2,j^{*}}^{k},\] (11) \[w_{l}^{k}= -\frac{1}{2\delta_{k}}\Big{\|}\sum_{j\in J_{1}^{k}\cup T_{l}} \lambda_{j}\xi_{1,j}^{k}-\xi_{2,j^{*}}^{k}\Big{\|}^{2}-\sum_{j\in J_{1}^{k} \cup T_{l}}\lambda_{j}\alpha_{1,j}^{k}+\alpha_{2,j^{*}}^{k}. \tag{12}\]  
Here, \(\lambda_{j}\geq 0\), \(j\in J_{1}^{k}\cup T_{l}\), with \(\sum_{j\in J_{1}^{k}\cup T_{l}}\lambda_{j}=1\), are the optimal variables of the dual of Problem (9). In addition, the definition of the set of problems \(P_{1,j}^{k}\); \(j\in J_{2}^{k}\) implies that  
\[w_{l}^{k}=\min_{d}w_{l}^{k}(d)=w_{l,j^{*}}^{k}(d_{l,j^{*}}^{k})\leq w_{l,j}^{k }(d_{l,j}^{k}),\quad j\in J_{2}^{k}.\]  
Since in the bundle index set \(J_{2}^{k}\), there exists an index, say \(j_{0}\), associated with the tuple \(b(x_{k})\) (see (3)) for which \(\xi_{2,j_{0}}^{k}\in\partial f_{2}(x_{k})\) and \(\alpha_{2,j_{0}}^{k}=0\), we have  
\[w_{l}^{k}\leq w_{l,j_{0}}^{k}=w_{l,j_{0}}^{k}(d_{l,j_{0}}^{k})=-\frac{1}{2 \delta_{k}}\Big{\|}\sum_{j\in J_{1}^{k}\cup T_{l}}\lambda_{j}^{0}\xi_{1,j}^{k} -\xi_{2,j_{0}}^{k}\Big{\|}^{2}-\sum_{j\in J_{1}^{k}\cup T_{l}}\lambda_{j}^{0} \alpha_{1,j^{*}}^{k}, \tag{13}\]  
for \(\lambda_{j}^{0}\geq 0\), \(j\in J_{1}^{k}\cup T_{l}\), with \(\sum_{j\in J_{1}^{k}\cup T_{l}}\lambda_{j}^{0}=1\). This together with (12) suggests a possible termination criterion for the proposed algorithm. In fact, whenever \(w_{l}^{k}\geq-\eta\), we have  
\[\frac{1}{2\delta_{k}}\Big{(}\Big{\|}\sum_{j\in J_{1}^{k}\cup T_{l}}\lambda_{j} ^{0}\xi_{1,j}^{k}-\xi_{2,j_{0}}^{k}\Big{\|}^{2}\Big{)}+\sum_{j\in J_{1}^{k} \cup T_{l}}\lambda_{j}^{0}\alpha_{1,j}^{k}\leq\eta,\]  
which indicates that the subgradient \(\xi_{2,j_{0}}^{k}\in\partial f_{2}(x_{k})\) is at a distance not bigger than \(\sqrt{2\delta_{k}\eta}\) from the \(\varepsilon\)-subdifferential of \(f_{1}\) at \(x_{k}\), where  
\[\varepsilon=\sum_{j\in J_{1}^{k}\cup T_{l}}\lambda_{j}^{0}\alpha_{1,j}^{k}\leq\eta.\]  
This property can be interpreted as the approximate satisfaction at the point \(x_{k}\) of criticality. Nevertheless, we implement the termination test of the proposed algorithm in the more common form of \(v_{l}^{k}\geq-\eta\). In fact, from (10) and (11), \(v_{l}^{k}\geq-\eta\) implies \(w_{l}^{k}\geq-\eta\). Further, the fulfillment of the condition \(w_{l,j_{0}}^{k}\geq-\eta\) provides an alternative termination criterion as  
\[v_{l,j_{0}}^{k}=-\frac{1}{\delta_{k}}\Big{(}\Big{\|}\sum_{j\in J_{1}^{k}\cup T _{l}}\lambda_{j}^{0}\xi_{1,j}^{k}-\xi_{2,j_{0}}^{k}\Big{\|}^{2}\Big{)}-\sum_{j \in J_{1}^{k}\cup T_{l}}\lambda_{j}^{0}\alpha_{1,j}^{k}\geq-\eta. \tag{14}\]  
**Remark 2**. : _In the above case, we embed the switching direction technique. That is, we use \(d_{1}^{k}\) as a tentative displacement, and if the descent failure occurs, then we implement an Armijo-type line search along the direction \(d_{1,j_{0}}^{k}\). Only in the case of failure of the latter is a null step declared._  
Next, we present the proposed BEM-DC algorithm 1 in the step-by-step format. We denote by \(i_{\rm ds}=1\) when the switching direction technique is embedded. ```
Require: The stopping tolerance parameter \(\eta>0\), the null step parameter \(\theta>0\), the proximity threshold \(\delta_{min}>0\), the sufficient descent parameter \(\mu\in(0,1)\), and the step size reduction parameters \(\sigma_{1},\ \sigma_{2}\in(0,1)\). ```  
**Algorithm 1**BEM-DC. **Remark 3**.