Amendment Unconstrained Optimization Problems, Quasi-newton Nonmonotonic Trust Region Algorithm

Trust region method is one of the important numerical computational methods in conlinear optimization. It has been paid so much attention by many researchers in the field of nonlinear optimization. Compared with line search method, TR method has two outstanding advantages: one is it has very strong stability and robustness; the other is its strong convergence. Because of the boundness of trust region. it can deal with nonconvex models. So far. TR method enlists in one of the two major numerical options for solving nonlinear optimization [1].Compared with line search method, TR method not only has strong convergence [2], but can solve bad-scaled problems efficiently with less iteration numbers. However, because it is difficult to solve the subproblem. the new iterative point is hard to obtain by using TR method, while line search method is easier to obtain the new point. As a result, in order to make good use of the advantages of both methods. Jorge Nocedal and Yuan Yaxiang [3] proposed an idea of combining TR method and line search method in 1991. In paper [25]. with backtracking line search and no need to resolve the subprobleni of TR method. the computational amount is greatly reduced. But in order to maitain the positive definiteness of B_k, causing some B_k do not perfectly match (?)²f(x_k). and then the subproblem of TR method does not match the original problem accordingly. In paper [5], E.Micheal Gertz propesed a new TR method with line search method. It not only no need to resolve the subproblem, but since using Wolfe line search at every iteration, B_k satisfies the quasi-Newton equation and maitains the positive definiteness. It fully developped the propertises of quasi-Newton formular and avoided the disadvantages of paper [25].In this paper, we mainly study the nonmonotonic TR method based on modified quasi-Newton equations. Since in real computations, the monotonic algorithms can not guarantee the validity of some problems, In 1986. Grippo,etc [6,7] lay out a nonmonotone line search technique, and applied it to Newton method and cutted Newton method. In 1993, Deng Naiyang and others [8] firstly applied nonmonotonic technique to trust region method and proved its global and superlinear convergence under suitable conditions. Numerical experiments showed that the nonmonotonic trust region method was superior to the corresponding monotonic method for some problems. The nonmonotonic techniquementioned above is realized by f_? = (?) f(x_k-j), where m(0) = 0,0≤m(k)≤min[m(k-1)+1,M],M is the given positive integer. Based on the proceeding work, we propese two kinds of new nonmonotonic TR algorithms.In chapter 1, we firstly give a brief introduction of the background and current situation of Optimization, and methods to solve TR subproblem. THen, we review the major nonexact line search methods for unconstrained optimization.In chapter 2, we propose a new quasi-Newton nonmonotonictrust region algorithm. We adjust the trust radius using not only (?). but also the previous ratios {r_k-m…,r_k}, where m is some positive integer. Under proper assumptions. we prove the global convergence of the algorithm and numerical experiments show the algorithm is competitive.In chapter 3, we present a modified quasi-Newton nonmonotonic trust region algorithm with Wolfe line search. Unlike traditonal nonmonotonic trust region algorithms, our algorithm gets the next point by the nonmonotonic Wolfe line search at each iteration. This new algorithm not only does not resolve the sub-problem but also satisfies the modified quasi-Newton condition at each iteration and simultaneously maintains a positive-definite approximation to the Hessian of the objective function. Under mild conditions, we prove the global convergence and numerical results show its efficiency.