Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search

In this paper, we establish the first explicit and non-asymptotic global convergence analysis of the BFGS method when deployed with an inexact line search scheme that satisfies the Armijo-Wolfe conditions. We show that BFGS achieves a global convergence rate of (1-1) ᵏ for -strongly convex functions with L-Lipschitz gradients, where =L denotes the condition number. Furthermore, if the objective function's Hessian is Lipschitz, BFGS with the Armijo-Wolfe line search achieves a linear convergence rate only determined by the line search parameters and independent of the condition number. These results hold for any initial point x₀ and any symmetric positive definite initial Hessian approximation matrix B₀, although the choice of B₀ affects the iteration count required to attain these rates. Specifically, we show that for B₀ = LI, the rate of O ( (1-1) ᵏ) appears from the first iteration, while for B₀ = I, it takes d iterations. Conversely, the condition number-independent linear convergence rate for B₀ = LI occurs after O ( (d +M f (x₀) -f (x_*) ^{3/2}) ) iterations, whereas for B₀ = I, it holds after O (M f (x₀) -f (x_*) ^{3/2} (d +) ) iterations. Here, d denotes the dimension of the problem, M is the Lipschitz parameter of the Hessian, and x_* denotes the optimal solution. We further leverage these global linear convergence results to characterize the overall iteration complexity of BFGS when deployed with the Armijo-Wolfe line search.