Greedy Quasi-Newton Methods with Explicit Superlinear Convergence
Preprint
Abstract
In this paper, we study greedy variants of quasi-Newton methods. They are based on the updating formulas from a certain subclass of the Broyden family. In particular, this subclass includes the well-known DFP, BFGS and 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 establish an explicit non-asymptotic bound on their rate of local superlinear convergence, which contains a contraction 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
All Related Versions
This publication has 21 references indexed in Scilit:
- Minimizing Uniformly Convex Functions by Cubic Regularization of Newton MethodJournal of Optimization Theory and Applications, 2021
- Quasi-Newton methods: superlinear convergence without line searches for self-concordant functionsOptimization Methods and Software, 2018
- Generalized self-concordant functions: a recipe for Newton-type methodsMathematical Programming, 2018
- Nonsmooth optimization via quasi-Newton methodsMathematical Programming, 2012
- Local and superlinear convergence of quasi-Newton methods based on modified secant conditionsJournal of Computational and Applied Mathematics, 2007
- The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained OptimizationComputational Optimization and Applications, 2004
- Convergence of quasi-Newton matrices generated by the symmetric rank one updateMathematical Programming, 1991
- Local convergence analysis for partitioned quasi-Newton updatesNumerische Mathematik, 1982
- A new approach to variable metric algorithmsThe Computer Journal, 1970
- A Rapidly Convergent Descent Method for MinimizationThe Computer Journal, 1963