An Approximate Bundle Method For Non-Convex Optimization And Convergence Theory

Proximal bundle method is considered to be one of the most promising methods for solving non-smooth optimization problems.In this paper,due to the requirements of practical calculations,two disturbance functions are used to control the real objective function together,whose information is utilized to construct an augmented function.Thereby bundle method for convex optimization is applied to non-convex optimization problems.Firstly,lower approximate model of the objective function can be constructed similarly,and by solving quadratic programming we expect to find out the minimum point as next candidate point,and furthermore select the decreased point.Furthermore,the dual problem of sub-problem of bundle method is given by utilizing Lagrange function,and at the same time the relation between the solutions of the primal problem which has been disturbed and the dual problem is also revealed.Finally,this paper analyzes the convergence problem from two aspects,i.e.,model property and the asymptotic behavior of the proposed algorithm.This paper constructs a more general lower approximate model for non-convex and non-smooth functions according to actual conditions,analyzes dual problem and convergence problem.It can be divided into four parts,the main ideas are as follow:Chapter One,firstly a series of papers concerning the typical non-convex and non-smooth optimization problems are listed.The ideas of these papers inspire a new method that is the combination of the redistributed proximal bundle method for non-convex optimization and the selection technique of the approximate dummy value of the objective function to solve the more general non-convex and non-smooth unconstrained optimization problems where,:nf R ?R is a non-convex function.Due to the needs of practical calculation,in this paper two disturbance functions are used to control the real objective function together.A hypothesis is proposed that ,with m(y)is a smooth function with m(y)?[-n,n] and f(4)(y)is a relatively simple non-smooth function with f(4)(y)?[ f(y)-?,f(y)+?].Then basic knowledge such as proximate bounded,the 2lower-C function,approximate proximate point mapping Rp,approximate stable point and so on is presented.Chapter Two,we mainly discuss the model construction in which inaccurate bundle information of the objective function is kept in a set,and build an augmented function at the decreased point ?kx for the approximate function of .The idea of convex optimization bundle method is adopted similarly to build the lower approximate model of the augmented function and the plane model is constructed by using the transformation of iterative information and the linearization error.According to ,in other words,by solving the quadratic programming,we expect to the find out the minimum point which is considered to be the next candidate point and,further,select the decreased point from these points,and then,the bundle information is updated and the above steps are repeated to determine the next decreased point.Finally,the proximate bundle method is given,which makes the approximate bundle method described above more logical.Chapter Three,the dual problem of the sub-problem of the bundle method is given by employing the Lagrange function.The relation between the solutions to the primal problem which has been disturbed and solutions to the dual problem are revealed.Then three relevant subgradient ownership relationships are given and the strict theoretical proofs are provided.Chapter Four,considering the cutting plane models constructed in Chapter Two,we analyze and prove four properties of the models.And considering the group of tangent plane models,we find that the parameters ?_n and ?_n are finally stable when iteration reaches a certain point.At the same time,an inequality similar to [29] is obtained and proved.Finally,we consider the stopping criterion of the algorithm,and prove the asymptotic convergence for the proposed algorithm from two situations under the assumption that 0stopTOL = and the algorithm does not stop forever.