A truncated ε-subdifferential method for global DC optimization

We consider the difference of convex (DC) optimization problem subject to box-constraints. Utilizing ε ε -subdifferentials of the DC components of the objective function, we develop a new method for finding global solutions to this problem. This method is based on the combination of a local search method and a special procedure for escaping from nonglobal solutions. The method terminates when the solution found by a local search method cannot be improved anymore. The escaping procedure is designed using subsets of the ε ε -subdifferentials of DC components. We compute the deviation between these subsets and determine ε ε -subgradients providing this deviation. Using these ε ε -subgradients we formulate a subproblem with a convex objective function. The solution to this subproblem is used as a starting point for a local search. We study the convergence of the conceptual version of the proposed method and discuss its implementation. A large number of academic test problems are used to show that the method requires a reasonable computational effort to find higher quality solutions than the four local methods for DC optimization. In addition, we apply the new method to find global solutions to DC optimization problems and compare its performance with that of two benchmark global optimization solvers.