Greedy quasi-Newton methods with explicit superlinear convergence

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

No 2020006, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this paper, we study greedy variants of quasi-Newton methods. They are based on the updating forulas from a certain subclass of the Broyden family. In particular, this subclass includes the well-known DFP, BFGS ans SR1 updates. However, in contrast to the classical quasi-Newton methods, which use the difference of successive iterates for updating the Hessian approximations, our methods apply basis vectors, greedily selected so as to maximize a certain measure of progress. For greedy quasi-Newton methods, we estabish an explicit non-asymptotic bound on their rate of local superlinear convergence, which contains a contracting factor, depending on the square of the iteration counter. We also show that these methods produce Hessian approximations whose deviation from the exact Hessians linearly convergences to zero.

Keywords: quasi-Newton methods; Broyden family; SR1; DFP; BFGS; superlinear convergence; local convergence; rate of convergence (search for similar items in EconPapers)
JEL-codes: F12 R12 (search for similar items in EconPapers)
Date: 2020-02-10
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2020.html (application/pdf)

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:louvco:2020006

Access Statistics for this paper

More papers in LIDAM Discussion Papers 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 ().