Rates of superlinear convergence for classical quasi-Newton methods

Anton Rodomanov () and Yurii Nesterov ()
Additional contact information
Anton Rodomanov: Université catholique de Louvain, ICTEAM
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3238, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: Quasi-Newton methods; Convex Broyden class; DFP; BFGS; Superlinear convergence; Local convergence; Rate of convergence (search for similar items in EconPapers)
Pages: 32
Date: 2023-01-01
Note: In: Mathematical Programming, 2022, vol. 194, p. 159-190
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3238

DOI: 10.1007/s10107-021-01622-5

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().