  In this paper, we present a global complexity analysis of the classical BFGS
method with inexact line search, as applied to minimizing a strongly convex
function with Lipschitz continuous gradient and Hessian. We consider a variety
of standard line search strategies including the backtracking line search based
on the Armijo condition, Armijo-Goldstein and Wolfe-Powell line searches. Our
analysis suggests that the convergence of the algorithm proceeds in several
different stages before the fast superlinear convergence actually begins.
Furthermore, once the initial point is far away from the minimizer, the
starting moment of superlinear convergence may be quite large. We show,
however, that this drawback can be easily rectified by using a simple
restarting procedure.
