A Redistributed Bundle Method For A Class Of Nonsmooth Unconstrained DC Optimization Problems

For solving nonsmooth optimization problems,bundle methods have shown very high efficiency.The bundle method not only ensures the value of the objective function to decrease,but also possesses the property of certain stability,and it has been successfully applied to many fields.The characteristic of this method is that a bundle of information is established to retain the existing iteration information,that is,the bundle method remembers the best iteration point obtained so far and retains the best point in each iteration process,so as to find the optimal solution of the considered problem.In this thesis,we mainly study the redistributed bundle method for solving a class of unconstrained DC optimization problems.The proposed method makes full use of the special structural information in DC components to construct a convex piece-wise linear model of the objective function and overcomes the difficulties caused by the non-convexity of the objective function.Furthermore,the dual theorem is employed to transform the original problem into dual subproblem,their optimal solutions and the next iteration point are obtained,respectively.At the same time,we further discuss the expression of the solution of the subproblem.On this basis,a specific algorithm of redistributed bundle method is proposed.Finally,the convergence of the redistributed bundle method is analyzed in detail.This thesis is mainly based on the idea of redistributed bundle method.In each iteration,convex parameters are appropriately selected to make the objective function convex locally,and a class of non-convex DC optimization problems are transformed into a class of convex optimization problems.The full text is divided into three parts,the main content is as follows:In chapter 1,the historical background and research status of DC programme are introduced,and the basic concepts of DC function are given.Next,several methods for solving non-smooth optimization problems are introduced in detail,These methods include steepest descent method,subgradient method,the cutting plane method and the general bundle method.Finally,in order to better understand the overall framework of this thesis,this chapter gives preliminary knowledge and related conclusions that are closely related to this thesis.At the same time,it lays a theoretical foundation for the further study of the problems in Chapter 2 and Chapter 3.In chapter 2,the basic idea of the redistributed bundle method is first introduced,and a convex piece-wise linear model of the DC function is constructed.On this basis,a penalty subproblem is presented to generate the next iteration point.According to the optimality condition of the subproblem,the explicit expression and basic properties of the optimal solution of the subproblem are given.Furthermore,the duality idea is used to study the solution of the subproblem,and the relationship between the original subproblem and the dual problem is revealed.In the end,the aggregate linearization and other related definitions are given which makes preparations for the convergence analysis of the algorithm in the next chapter.In chapter 3,the redistributed bundle method algorithm for solving unconstrained DC optimization problems is given.At the same time,the in-depth analysis of the algorithm is carried out,including the convergence analysis of the algorithm and the proof of relevant conclusions.In the part of convergence analysis,we mainly discussed in two cases.Case 1: the algorithm produces infinitely many descent steps.Case 2: the algorithm produces the last descent step,followed by infinitely many zero steps.From these two aspects,we study the convergence of the redistributed bundle method proposed in this thesis.