Analyzing and Improving Quasi-Newton Methods for Unconstrained Optimization
This thesis is concerned with analyzing and improving the performance of quasi-Newton methods for finding the minimum of a real valuedd function of a finite number of real variables. Quasi-Newton methods are a successful way of iteratively solving this problem when the Hessian matrix of second partial derivatives of the function cannot be cheaply computed. Instead they keep an approximation to the Hessian matrix at the current point, and update it at each iteration. A recent algorithm of Davidon's has contributed two important new ideas to the formulation of such updates, while improving upon the computational performance of existing algorithms. In this thesis we analyze the work of Davidon, propose some changes to his algorithm and test some of these, and extend much of the existing analysis of quasi-Newton updates for optimization problems to a broader class of updates which includes Davidon's. The two innovations in Davidon's algorithm are the use of a new update class intended to preserve past derivative information in the Hessian approximation, and the selection of the actual update from this class by a method called optimal conditioning. We explain and analyze both of these aspects thoroughly. The use of the new update class seems to be very beneficial, although our analysis suggests several alternative implementations which are equivalent to Davidon's algorithm on quadratic problems. We extend existing convergence techniques to show that two of these methods enjoy local Q-superlinear convergence under normal assumptions. On the other hand, our theoretical and computational analysis of optimal conditioning indicates that it may not be helpful in most cases, and that further computational testing definitely is required. However, we introduce and test an update which uses optimal conditioning only on some selected iterations, and which seems to show promise. To aid our analysis of Davidon's ideas we introduce the concept of a restricted update class, of which his is an example. We then extend much of the existing analysis of rank-two quasi-Newton updates, including questions of hereditary positive definiteness, mimimum change updates, and performance using perfect line search, to include this broadened update class. This work helps suggest some of our proposed changes to Davidon's algorithm, and is useful in deriving and analyzing quasi-Newton updates for other problems. A basic equivalence shows that our analysis extends to a very general class of rank-two updates. Quasi-Newton methods are currently being applied in a variety of problem areas. We hope that our analysis improves upon their use in unconstrained optimization, and helps make the leading new ideas in the field accessible to other application areas.