Rates of superlinear convergence for classical quasi-Newton methods
(2022) Mathematical Programming — Vol. 194, n° 1-2, p. 159-190 (2022)
Files
CORE_RP_3238.pdf
Open Access - Adobe PDF
- 767.41 KB
Details
- Authors
Rodomanov, Anton 
- Abstract
- We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form (nL2μ2k)k/2 and (nLμk)k/2 respectively, where k is the iteration counter, n is the dimension of the problem, μ is the strong convexity parameter, and L is the Lipschitz constant of the gradient.
- Affiliations
Citations
Rodomanov, A., & Nesterov, Y. (2022). Rates of superlinear convergence for classical quasi-Newton methods. Mathematical Programming, 194(1-2), 159-190. https://doi.org/10.1007/s10107-021-01622-5 (Original work published 2022)