The Use of Negative Curvature in Minimization Algorithms

Abstract

IN this paper we examine existiing algorithms for minimizing a nonlinear function of many variables which make use of negative curvature. These algorithms can all be viewed as modified versions of Newton's method and their merits and drawbacks are discussed to help identify new and more promising methods. The algorithms considered include ones which compute and search along nonascent directions of negative curvature and ones which search along curvi-linear paths generated by these directions and descent directions. Versions of the Goldfield-Quandt-Trotter method, or equivalently, methods based upon a trust region strategy, and gradient path methods are also considered. When combined with the numerically stable Bunch-Parlett factorization of a symmetric indefinite matrix the latter two approaches give rise to new, and what appears to be, efficient and robust minimization methods which can take advantage of negative curvature when it is encountered. Several suggestions are made for further research in this area.