# Bundle Enrichment Method for Nonsmooth Difference of Convex Programming Problems
## 3 The New Model Function  
In this section, we formulate our new model function. First, we distribute the bundle index set \(J^{k}\) into the subsets  
\[J^{k}_{1}=\Big{\{}j:j\in J^{k},\ \alpha^{k}_{j}\leq 0\Big{\}}\quad\text{and}\quad J ^{k}_{2}=\Big{\{}j:j\in J^{k},\ \alpha^{k}_{j}\geq 0\Big{\}}, \tag{4}\]  
where \(J^{k}=J^{k}_{1}\cup J^{k}_{2}\). It is worth noting that this does not properly define a partition of \(J^{k}\) as the indexes corresponding to \(\alpha^{k}_{j}=0\) are in both subsets \(J^{k}_{1}\) and \(J^{k}_{2}\). In addition, \(\alpha^{k}_{j}=\alpha^{k}_{1,j}-\alpha^{k}_{2,j}\) can take any sign due to the nonconvexity of the function \(f\). Based on the sign of \(\alpha^{k}_{j}\), we extract elements from the set \(J^{k}\) and modify the definition of the cutting-plane models, given in (2), accordingly. It is clear that \(\alpha^{k}_{j}\leq 0\) corresponds to \(\alpha^{k}_{1,j}\leq\alpha^{k}_{2,j}\). That is, the linearization error at \(x_{k}\) associated with the linearization of the function \(f_{1}\) rooted at \(x_{j}\) is not bigger than that associated with the function \(f_{2}\). This means that the information provided by \(x_{j}\) is more suited to approximate \(f_{1}\) than \(f_{2}\) around \(x_{k}\). The reverse holds for the case \(\alpha^{k}_{j}\geq 0\). **Remark 1**. : _The structures of the subsets \(J^{k}_{i},\ i=1,2\) depend on the point \(x_{k}\). Thus, they should be updated every time a new iterate \(x_{k+1}\) is calculated._  
Consider the subsets \(J^{k}_{i},\ i=1,2\). Aiming at a parsimonious use of the available information, we restrict the definition of the cutting-plane functions, given in (2), as  
\[\hat{f}^{k}_{i}(x)=\max_{j\in J^{k}_{i}}\Big{\{}f_{i}(x_{k})+\langle\xi_{i,j},x-x_{k}\rangle-\alpha^{k}_{i,j}\Big{\}},\ i=1,2,\]  
which reduces the number of affine pieces defining the convex approximations of the functions \(f_{i},\ i=1,2\). Next, we introduce the variable \(d=x-x_{k}\) and define the function \(h^{k}(d)\) (the model of the difference function \(f(x_{k}+d)-f(x_{k})\)) as  
\[h^{k}(d)=h^{k}_{1}(d)-h^{k}_{2}(d)=\max_{j\in J^{k}_{1}}\Big{(}\langle\xi_{1,j },d\rangle-\alpha^{k}_{1,j}\Big{)}-\max_{j\in J^{k}_{2}}\Big{(}\langle\xi_{2,j },d\rangle-\alpha^{k}_{2,j}\Big{)},\]  
and calculate  
\[w^{k}=\min_{d}w^{k}(d)=\min_{d}h^{k}(d)+\frac{1}{2}\delta_{k}\|d\|^{2}. \tag{5}\]  
Here, \(\delta_{k}\) is the proximity parameter used in most bundle methods, and \(\frac{1}{2}\delta_{k}\|d\|^{2}\) is a stabilizing term used to guarantee the existence of the solution. Letting \(d_{k}\) be the solution to (5), we take \(x_{k+1}=x_{k}+d_{k}\) as the (tentative) new iterate point. Then, we check this point for a possible sufficient decrease in the objective function \(f\) as follows:  
\[f(x_{k}+d_{k})\leq f(x_{k})+\mu v^{k}, \tag{6}\]  
where \(\mu\in(0,1)\) is a given parameter, and \(v^{k}\) is the predicted reduction of the function \(f\) provided by the model function \(h^{k}(d)\). That is, \(v^{k}=v^{k}_{1}-v^{k}_{2}\), where  
\[v^{k}_{1}=h^{k}_{1}(d_{k})=\max_{j\in J^{k}_{1}}\langle\xi_{1,j},d_{k}\rangle-\alpha^{k}_{1,j},\quad\text{and}\] \[v^{k}_{2}=h^{k}_{2}(d_{k})=\max_{j\in J^{k}_{2}}\langle\xi_{2,j},d_{k}\rangle-\alpha^{k}_{2,j}.\]Note that we have \(v^{k}\leq 0\). It is sufficient to observe that both functions \(h_{1}^{k}(d)\) and \(h_{2}^{k}(d)\) are non-positive at \(d=0\). If (6) is satisfied (serious step in bundle method parlance), then the point \(x_{k+1}=x_{k}+d_{k}\) becomes the new estimate of a minimum. Thus, the related information to this point is appended to the bundle, and the bundle index set is updated. Next, the elements of the new index set \(j^{k+1}\) are distributed between \(j^{k+1}_{1}\) and \(j^{k+1}_{2}\) according to (4) (see Remark 1), and the procedure is iterated. If the condition (6) is not satisfied, that is \(f(x_{k}+d_{k})>f(x_{k})+\mu v^{k}\), then there is no sufficient decrease (null step).