Quadratic Termination Properties of Minimization Algorithms I. Statement and Discussion of Results

摘要

There is a family of gradient algorithms (Broyden, 1970) that includes many useful methods for calculating the least value of a functionF(x), and some of these algorithms have been extended to solve linearly constrained problems (Fletcher, 1971). Some new and fundamental properties of these algorithms are given, in the case thatF(x) is a positive definite quadratic function. In particular these properties are relevant to the case when only some of the iterations of an algorithm make a complete linear search. They suggest that Goldfarb's (1969) algorithm for linearly constrained problems has excellent quadratic termination properties, and it is proved that these properties are better than has been stated in previously published papers. Also a new technique is identified for unconstrained minimization without linear searches.