# Bundle Enrichment Method for Nonsmooth Difference of Convex Programming Problems
## 5 Termination Property of Algorithm BEM-DC  
In this section, we provide the proof of the Algorithm BEM-DC, taking any starting point \(x_{1}\in\mathbb{R}^{n}\) as an input, that returns an approximate critical point \(x^{*}\). Assume that the set  
\[\mathcal{F}_{1}\triangleq\Big{\{}x\in\mathbb{R}^{n}:f(x)\leq f(x_{1})\Big{\}}\]  
is bounded and the numbers \(L_{1}\) and \(L_{2}\) are the Lipschitz constants of \(f_{1}\) and \(f_{2}\), respectively, on the set \(\mathcal{F}_{1}\). Note that, whenever the tuple \(b(y)\) is inserted into the temporary bundle \(TB_{t}\) associated with the function \(f_{1}\) at the trial point \(y\) (see _Step 6_), then \(t\|d_{t}^{k}\|\leq\theta\) implies \(\xi_{1}^{+}(y)\in\partial_{\varepsilon}f_{1}(x_{k})\) for \(\varepsilon\leq 2\theta L_{1\theta}\), where \(L_{1\theta}\) is the Lipschitz constant of \(f_{1}\) on the set  
\[\mathcal{F}_{\theta}\triangleq\Big{\{}x\in\mathbb{R}^{n}:dist(x,\mathcal{F}_{ 1})\leq\theta\Big{\}}.\]  
Lemma 1: _Let \(L_{1\theta}\) and \(L_{2}\) be the Lipschitz constants of \(f_{1}\) and \(f_{2}\), respectively, on the set \(\mathcal{F}_{\theta}\). Then the following bound holds:_  
\[\|d_{t}^{k}\|\leq\frac{L_{1\theta}+L_{2}}{\delta_{min}}=D. \tag{17}\]  
Proof: Throughout the algorithm, we have \(\delta_{k}\geq\delta_{min}\), and thus, the inequality follows from (10). Remark 5: _The bound given in (17) is also valid for \(\|d_{t,j_{0}}^{*}\|\)._  
Next, we prove that the number of inner iterations of algorithm BEM-DC is finite. Lemma 2: _At any given \(k\)-th outer iteration, the inner iteration terminates, either fulfilling the sufficient decrease condition (Step 4) or satisfying the stopping condition (Step 2)._  
Proof: Suppose by contradiction that the inner iteration does not terminate. Since (see Remark 5) \(\|d_{t,j_{0}}^{*}\|\) is bounded and \(t\) becomes arbitrarily small, the algorithm cannot loop infinitely many times between Steps 4 and 5. Thus, it loops infinitely many times between Steps 1 and 7, giving rise to an infinite number of null steps. Observe now that every time a null step occurs and the tuple \(b(y)\) is generated at Step 6, we have  
\[f(x_{k}+t_{l}d_{l}^{k})-f(x_{k}) =f_{1}(x_{k}+t_{l}d_{l}^{k})-f_{2}(x_{k}+t_{l}d_{l}^{k})-\Big{(} f_{1}(x_{k})-f_{2}(x_{k})\Big{)}\] \[\geq t_{l}\mu v_{l}^{k},\quad\text{for some}\quad 0<t_{l}<1.\]  
Considering  
\[\alpha_{1,l+1}^{k}=f_{1}(x_{k})-f_{1}(x_{k}+t_{l}d_{l}^{k})+t_{l}\langle\alpha_ {1,l+1}^{k},d_{l}^{k}\rangle,\]  
the convexity of \(f_{2}\), and \(\delta_{2,l_{0}}^{k}\in\partial f_{2}(x_{k})\), it follows  
\[\langle\delta_{1,l+1}^{k}-\delta_{2,l_{0}}^{k},d_{l}^{k}\rangle-\alpha_{1,l+1} ^{k}\geq\Big{(}\frac{1}{t_{l}}-1\Big{)}\alpha_{1,l+1}^{k}+\mu v_{l}^{k}>\mu v_ {l}^{k}. \tag{18}\]  
Furthermore, since the sequence \(\{w_{l}^{k}\}_{l\to\infty}\), is monotonically non-decreasing and bounded from above by zero, it is convergent. Note that the sequence \(\{w_{l,j_{0}}^{k}\}_{l\to\infty}\) (see (13)) is convergent as well. Consequently, from boundedness of \(\|d_{t,j_{0}}^{k}\|\), there exists a convergent subsequence \(\{d^{k}_{i,j_{0}}\}_{l\in\mathcal{L}}\to\bar{d}^{k}_{0}\), and thus, the subsequence \(\{v^{k}_{l,j_{0}}\}_{l\in\mathcal{L}}\) also converges to a limit, say \(\bar{v}^{k}_{0}\leq 0\), for some subset of indices \(\mathcal{L}\subset\{1,2,\ldots\}\). Next, consider two successive indices \(p,q\in\mathcal{L}\). From (18) and the definition of Problem \(P^{k}_{l,j_{0}}\), we obtain  
\[\langle\bar{c}^{k}_{1,p+1}-\bar{c}^{k}_{2,j_{0}},d^{k}_{p}\rangle -\alpha^{k}_{1,p+1}>\mu v^{k}_{p,j_{0}},\quad\text{and}\] \[\langle\bar{c}^{k}_{1,p+1}-\bar{c}^{k}_{2,j_{0}},d^{k}_{q}\rangle -\alpha^{k}_{1,p+1}\leq\bar{v}^{k}_{q,j_{0}}.\]  
Therefore, we obtain  
\[v^{k}_{q,j_{0}}-\mu v^{k}_{q,j_{0}}>\langle\bar{c}^{k}_{1,p+1}-\bar{c}^{k}_{2, j_{0}},d^{k}_{q}-d^{k}_{p}\rangle.\]  
Passing this to the limit, we have \((1-\mu)\bar{v}^{k}_{0}\geq 0\), which, taking into account \(\bar{v}^{k}_{0}\leq 0\), implies \(\bar{v}^{k}_{0}=0\).