New Results on Superlinear Convergence of Classical Quasi-Newton Methods

Anton Rodomanov, Yurii Nesterov

Published 2020-04-29Version 1

We present a new theoretical analysis of local superlinear convergence of the classical quasi-Newton methods from the convex Broyden class. Our analysis is based on the potential function involving the logarithm of determinant of Hessian approximation and the trace of inverse Hessian approximation. For the well-known DFP and BFGS methods, we obtain the rates of the form $\left[\frac{L}{\mu} \left(\exp\left\{\frac{n}{k} \ln \frac{L}{\mu}\right\} - 1\right)\right]^{k/2}$ and $\left[\exp\left\{\frac{n}{k} \ln \frac{L}{\mu}\right\} - 1\right]^{k/2}$ respectively, where $k$ is the iteration counter, $n$ is the dimension of the problem, $\mu$ is the strong convexity parameter, and $L$ is the Lipschitz constant of the gradient. Currently, these are the best known superlinear convergence rates for these methods. In particular, our results show that the starting moment of superlinear convergence of BFGS method depends on the logarithm of the condition number $\frac{L}{\mu}$ in the worst case.