Accelerated Level Bundle Methods With Inexact Oracle For Nonsmooth Optimization

Optimization is an important branch of Operational Research and Cy-bernetics and has always been arousing a wide and hot concern at home and abroad.Nonsmooth optimization is a special type of optimization problems with wide range of application such as optimal control,joint opportunities constrained programming,signal processing and randan programming,etc.In recent years,with the deepening of the optimization in practical applica-tions,most problems often show two major characteristics:First,their scales are large and their structure are special;Second,the function value and sub-gradient of the problem are difficult or impossible to be calculated accurately.Therefore,traditional nonsmooth optimal methods can not solve these prob-lems.Thus,the stable and excellent numerical algorithms to study this kind of nonsmooth optimization problems have crucial theoretical significance and application value.This dissertation presents two types of accelerated level bundle methods with inexact data for solving nonsmooth optimization problems.Firstly,in this thesis,accelerated level bundle method with inexact data for nonsmooth optimizations is proposed.Due to the fact that exact function values and subgradients are not easy to compute,a piecewise linear approx-imation model of the original objective function is constructed by utilizing inaccurate function values and inaccurate subgradients.This model is lo-cated under the side of the objective function.In conjunction with the ac-celerated strategy,acceleration refers to that during iterative processes,three iteration points sequences are designed to update the cutting plane model,the proximal center and the upper bound of the optimal objective function val-ue of original problem,respectively.At last,the complexity of the proposed method is analyzed to obtain the optimal iteration complexity for solving the nonsmooth optimization problem.The complexity does not depend on any problem parameters such as the Lipschitz constant and the diameter of the feasible set.Secondly,the dissertation is improved on the basis of the above method.Accelerated proximal level bundle method with inexact data for solving non-smooth optimization problems is proposed.By replacing the original Eu-clidean norm with general proximal functions,this method can not only ef-fectively use geometric properties of the feasible set,but can also control the quantity of cutting planes used in the cutting plane model.This ensures that the memory required to store the cutting planes does not increase linearly with the number of iterations,which in turn overcomes the iterative effect generated by the above algorithm,i.e,as the number of iterations increases,the amount of computation will rises,which causes that the convergence of the algorithm is weakened.In addition,as the same as the previous method,the optimal iterative complexity of the algorithm for nonsmooth optimiza-tions can still yield without entering any problem parameters.Finally,numerical experiments on the proposed algorithm are performed,the results of numerical experiments show that these two algorithms which are proposed in this thesis are superior to the traditional inexact level bundle methods.