# Bundle Enrichment Method for Nonsmooth Difference of Convex Programming Problems
###### Abstract  
The Bundle Enrichment Method (BEM-DC) is introduced for solving nonsmooth difference of convex (DC) programming problems. The novelty of the method consists of the dynamic management of the bundle. More specifically, a DC model, being the difference of two convex piecewise affine functions, is formulated. The (global) minimization of the model is tackled by solving a set of convex problems whose cardinality depends on the number of linearizations adopted to approximate the second DC component function. The new bundle management policy distributes the information coming from previous iterations to separately model the DC components of the objective function. Such a distribution is driven by the sign of linearization errors. If the displacement suggested by the model minimization provides no sufficient decrease of the objective function, then the temporary enrichment of the cutting plane approximation of just the first DC component function takes place until either the termination of the algorithm is certified or a sufficient decrease is achieved. The convergence of the BEM-DC method is studied, and computational results on a set of academic test problems with nonsmooth DC objective functions are provided. DC optimization; nonconvex nonsmooth optimization; cutting plane; bundle method +
Footnote †: journal:  
00000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000-0000-00000-00000-0  
Nonsmooth DC programming is an important subclass of DC optimization problems [6], and many practical problems are modeled as a DC programming problem. They include the bridge location problem, the design centering problem [7], the packing problem [8], the production-transportation planning problem [9], the location planning problem [10], the edge detection problem [11], the conic programming problem [12], cluster analysis [13], and regression analysis [14]. Recently, DC optimization problems with uncertain data has become an interesting topic, and the results from robust optimization, in particular those obtained in [15; 16; 17], can be extended to robust DC optimization. DC optimization problems have been studied in the context of both local and global problems, and various methods have been developed for solving these problems globally [7; 18]. To the best of our knowledge, the first local search algorithm for solving DC optimization problems is the difference of convex algorithm (DCA) introduced in [19] and further explored, for example, in [8; 20]. Since then, the development of local DC optimization methods for solving Problem (1) has attracted remarkable scholarly attention. Next, we provide a short description of such methods and give references for more details. These methods can be classified into three categories:  
* The first category consists of the DCA and its modifications. The basic idea of the DCA is to linearize the concave part \(-f_{2}\) around the current iterate by using its subgradient while keeping the convex part \(f_{1}\) as it is in the minimization process. To improve the convergence of the DCA, various modifications have been developed, for instance, in [21; 22; 23]. The boosted DC algorithm (BDCA), proposed in [21; 22], accelerates the convergence of the DCA by using an additional line search step. The inertial DCA, introduced in [23], defines trial points whose sequence of functional values is not necessarily monotonically decreasing. This controls the algorithm from converging to a critical point that is not \(d\)-stationary. In [24], the BDCA is combined with a simple derivative-free optimization method. This allows one to force the \(d\)-stationarity (lack of descent direction) at the obtained point. To avoid the difficulty of solving the DCA's subproblem, in [25], the first DC component is replaced with a convex model, and the second DC component is used without any approximation;
* The methods in the second category, which we refer to as DC-Bundle, are various extensions of the bundle methods for convex problems.