A characterization of superlinear convergence and its application to quasi-Newton methods

Abstract:

Let F be a mapping from real n-dimensional Euclidean space into itself. Most practical algorithms for finding a zero of F are of the form \[ {x_{k + 1}} = {x_k} - B_k^{ - 1}F{x_k},\] where $\{ {B_k}\}$ is a sequence of nonsingular matrices. The main result of this paper is a characterization theorem for the superlinear convergence to a zero of F of sequences of the above form. This result is then used to give a unified treatment of the results on the superlinear convergence of the Davidon-Fletcher-Powell method obtained by Powell for the case in which exact line searches are used, and by Broyden, Dennis, and Moré for the case without line searches. As a by-product, several results on the asymptotic behavior of the sequence $\{ {B_k}\}$ are obtained. An interesting aspect of these results is that superlinear convergence is obtained without any consistency conditions; i.e., without requiring that the sequence $\{ {B_k}\}$ converge to the Jacobian matrix of F at the zero. In fact, a modification of an example due to Powell shows that most of the known quasi-Newton methods are not, in general, consistent. Finally, it is pointed out that the above-mentioned characterization theorem applies to other single and double rank quasi-Newton methods, and that the results of this paper can be used to obtain their superlinear convergence.