# Bundle Enrichment Method for Nonsmooth Difference of Convex Programming Problems
###### Abstract
The piecewise linear underestimates or subgradients of both DC components are utilized to compute search directions. The methods include the codifferential method [26], the proximal bundle method with the concave affine model [27; 28], the proximal bundle method for DC optimization [29; 30], the proximal point algorithm [31], the proximal linearized algorithm [32], the double bundle method [33], and the nonlinearly constrained DC bundle method [34];
* The methods in the third category are those that use the convex piecewise linear model of the first DC component and one subgradient of the second DC component to compute search directions at each iteration [35; 36]. They differ from those in the first category as at each iteration of these methods, the model of the first DC component is updated and the new subgradient of the second component is calculated. They also differ from those in the second category as they use only one subgradient of the second DC component at each iteration whereas the DC-Bundle methods may use more than one subgradient of this component to build its piecewise linear model. Note that some overlapping is unavoidable when classifying methods into different categories: for instance, the proximal bundle method for DC optimization [30] may be classified into both the second and the third categories. The other methods in the third category include the aggregate subgradient method for DC optimization [35] and the augmented subgradient method [36]. In the former method, the aggregate subgradient of the first DC component and one subgradient of the second component are utilized to compute search directions. In the latter method, augmented subgradients of convex functions are defined and used to model the first DC component. Then, this model and one subgradient of the second DC component are used for computing search directions. The proposed BEM-DC method belongs to the DC-bundle family whose main features, with respect to the DCA, are  
* developing a model function based on cutting-plane approximations of \(f_{1}\) and, possibly, \(f_{2}\);
* adding a regularization term (typically a proximity one) to the model for stabilization purposes. We assume the familiarity of the reader with the basic notions of bundle methods. We refer to the following books and articles from the vast literature available [37; 38; 39; 40; 41; 42; 43; 44; 45]. In our iterative scheme, we adopt two cutting-plane approximations (based, as usual in bundle methods, on information coming from previous iterations) for \(f_{1}\) and \(f_{2}\), respectively. Consequently, we have a model which is still DC, being the difference of two convex piecewise affine functions. Similarly to [29; 33], we tackle the (global) minimization of the model by solving a set of convex problems whose cardinality depends on the number of linearizations adopted to approximate the function \(f_{2}\). The novelty of the approach consists of the dynamic management of the bundle. This enables us to achieve a parsimonious use of the information available, in view of reducing the computational burden to minimize the model function at each iteration. The adopted strategies are based on the following:  
* The information coming from the previous iterates contributes to the approximation of exactly one of the DC components \(f_{1}\) and \(f_{2}\), depending on the sign of the linearization error relative to the current iterate. During the iterative process, every time a new point is generated, subgradients of both component functions \(f_{1}\) and \(f_{2}\) are calculated, but only one of them will enter the calculation of the search direction: the choice being driven, at each of the successive iterations, by the sign of the linearization error with respect to the current point. Such sign may change at each iteration.