Application Of BFGS (MBFGS, CBFGS) In Trust Region Line Search Method

Trust region methods are efficient for solving unconstraint optimization problems. The basic idea of these methods is to approximate the optimization problem by a sequence of quadratic minimization problems subject to some trust region. An attractive property of trust region methods lies in their numerical stability and robustness. They can be applied to solve ill-conditioned problems. Under certain conditions, trust region methods are globally and superlinearly convergent. However, the traditional trust region methods may meet difficulty. 1. The Hessian matrix of the trust region subproblem may not be positive definite. In this case, the trust region subproblem is relatively difficult to solve. In particular, there is a hard case. For this hard case, the convergence rate of some trust region methods is only linear. 2. At each iteration, many trust region subproblems have to be solved, which is computationally cost. 3. To ensure the global convergence of a trust region method, it is generally assumed that the matrix sequence generated by the algorithm is bounded. Yet it is not know what kind of quasi-Newton trust region methods satisfy this condition.Nocedal-Yuan(1998) proposed a trust region-line search method with BFGS update. In the method, the generated iterative matrices are positive definite. A good advantage of Nocedal-Yuan's method lies in that at each iteration, only one trust region subproblem need to be solved. However, to obtained the global convergence of the method, the boundedness of the matrix sequence is still necessary. By use of a modified BFGS formula proposed by Li-Fukushima (2001), Li-Qi(2003)proposed a MBFGS-trust region method. This method enjores the the property that the generated matrices are positive definite. Moreover, the method is globally and superlinearly convergent without requirement of the boundedness of the matrix sequence. However, at each iteration of the method, several trust region subproblems have to be solved.The purpose of this thesis is to develop quasi-Newton type trust region-line search methods. At each step, only one trust region subproblem is solved. We then use the solution of the subproblem as the search direction and get a steplength by line search. We show that if the objective function is convex, then the standard BFGS trust region-line search method is globally convergent. For nonconvex minimization problem, we develop a MBFGS and a CBFGS trust region-line search methods and show their global convergence. The boundedness of the generatedmatrix sequence is not required for all proposed methods to be globally convergent.