With Line Search Nonmonotone Trust Region Algorithm

In this paper,we study nonmonotonic trust region methods for unconstrained optimization problems.At present,trust region methods and line search methods are mainly two typies of numerical algorithms for nonlinear optimization problems.Compared with line search methods,trust region methods have new idea,validity,strong convergence, can solve good and ill-conditioned problems.In view of the advantages of trust region methods,the study of trust region methods become an important research direction in nonlinear optimization area.The traditional trust region methods are monotonic so that the algorithms have the property of global convergence.However,people found that monotonic algorithms could't pledge the validity for some examples.In 1986,Grippo and others first proposed a kind of nonmonotonic line search technique which use the value of f_l(k)=(?) f(x_k-j),where m(0)=0,0≤m(k)≤min[m(k-1)+1,M],M is the given positive integer.Moreover,Grippo applied the nonmonotonic line search technique to Newton method and cutted Newton method.In 1993,N Y.Deng and others applied the nonmonotonic technique to trust region method firstly and proved its global and superlinear convergence under suitable conditions.Numerical experiments showed that the nonmonotonic trust region methods are superior to the corresponding monotonic method by choosing suitable M.In 2004,basing on an average of the successive function values decreases,a new nonmonotone line search method was proposed in paper.The new nonmonotone line search technique avoids the numerical results relying on the choice of M,can control the degree of nonmonotonicity,and can decrease the number of object function values.In 1998,through combining trust region and line search techniques,Nocedal and Y.X creatively proposed a new method for optimization problems which has advantages of the two methods.Based on the preceding work,we propose two kinds of new nonmonotonic trust region algorithms.In chapter 1,firstly,we summary unconstrained optimization method.Secondly,we mainly review the basic idea,main theories and corresponding research results of trust region method.At last,we introduce the BFGS formula and MBFGS formula.In chapter 2,we propose a new family of nonmonotonic trust region algorithm for unconstrained optimization.This new algorithm does not resolve the subproblem because of combining traditional trust region method with the nonmonotonic Wolfe line search technique which was proposed by Hongchao Zhang and Hager in paper.Moreover, the new algorithm use the strategy which was proposed in paper to adjust trust region radius.Under certain conditions,the global convergence and strong convergence of the algorithm are proved.Numerical results show that the new nonmonotonic trust region algorithm is quite efficient.In chapter 3,we propose another trust region algorithm with a nonmonotonic line search.Because of combining the nonmonotonic Armijo line search with trust region method,The new algorithm doesn't resolve the subproblem.We update B_k by MBFGS method,so B_k approximates to Hessian of the objective function well and keeps positive definite.Under weaker conditions,the global convergence of the algorithm is proved. Some numerical results show that the new nonmonotonic trust region algorithm is efficient.