Greedy-quasi Newton methods with explicit superlinear convergence
(2020) , 27 pages
Files
coredp2020_06web.pdf
Open Access - Adobe PDF
- 2.07 MB
Details
- Authors
- 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.
- Affiliations
Citations
Rodomanov, A., & Nesterov, Y. (2020). Greedy-quasi Newton methods with explicit superlinear convergence (CORE Discussion Papers 2020/06). https://hdl.handle.net/2078.5/94434