Trust Region Methods With Line Searches

In the present thesis, we mainly study two trust region methods with line searches. In Chapter 1, we briefly introduce the trust region method and some related works.In Chapter 2, a nonmonotone trust region method with a line search technique is presented. Unlike traditional trust region methods, our method does not restrict a monotonic decrease of the objective function value at each iteration, but only requires an average of the successive objective function values decreasing. Moreover, if a trial step is not accepted, our algorithm performs a nonmonotone line search to find a new iteration point instead of resolving the subproblem. Nonmonotone schemes can improve the likelihood of finding a global optimum; also, they can improve convergence speed in cases where a monotone scheme is forced to creep along the bottom of a narrow curved valley. Under mild conditions, we establish the global and superlinear convergence results for the method. Primary numerical results are encouraging.In Chapter 3, a hybrid method combining trust region method with quasi-Newton method is introduced. At each iteration, the method gives priority to trust region method. But if a trust region step is not accepted, the method turns to quasi-Newton method, i.e., a quasi-Newton step is generated by backtracking line search technique. The algorithm is never required to resolve the subproblem, therefore, it can considerably reduce the total cost of computation. Furthermore, we use BFGS method to update matrix B_k, without the assumption condition of f is uniformly convex, we show that the method is globally and superlinearly convergent. Primary numerical results show that the method is promising.