Greedy quasi-Newton methods with explicit superlinear convergence
From MaRDI portal
(Redirected from Publication:5853572)
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.
Recommendations
- Rates of superlinear convergence for classical quasi-Newton methods
- New results on superlinear convergence of classical quasi-Newton methods
- Global Convergence of a Cass of Quasi-Newton Methods on Convex Problems
- Non-asymptotic superlinear convergence of standard quasi-Newton methods
- Local and Superlinear Convergence for Partially Known Quasi-Newton Methods
Cites work
- A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
- A Family of Variable-Metric Methods Derived by Variational Means
- A new approach to variable metric algorithms
- A Rapidly Convergent Descent Method for Minimization
- A Tool for the Analysis of Quasi-Newton Methods with Application to Unconstrained Minimization
- Conditioning of Quasi-Newton Methods for Function Minimization
- Contracting proximal methods for smooth convex optimization
- Convergence of quasi-Newton matrices generated by the symmetric rank one update
- Generalized self-concordant functions: a recipe for Newton-type methods
- Global Convergence of a Cass of Quasi-Newton Methods on Convex Problems
- scientific article; zbMATH DE number 3597791 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3395301 (Why is no real title available?)
- IQN: an incremental quasi-Newton method with local superlinear convergence rate
- Lectures on convex optimization
- Local and Superlinear Convergence for Partially Known Quasi-Newton Methods
- Local and superlinear convergence of quasi-Newton methods based on modified secant conditions
- LOCAL AND SUPERLINEAR CONVERGENCE OF STRUCTURED QUASI-NEWTON METHODS FOR NONLINEAR OPTIMIZATION
- Local convergence analysis for partitioned quasi-Newton updates
- Nonsmooth optimization via quasi-Newton methods
- On the Convergence of the Variable Metric Algorithm
- On the Local and Superlinear Convergence of Quasi-Newton Methods
- Quasi-Newton Methods and their Application to Function Minimisation
- Quasi-Newton Methods, Motivation and Theory
- Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Superlinear convergence of Broyden's boundedθ-class of methods
- The Convergence of a Class of Double-rank Minimization Algorithms
- The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations
- The superlinear convergence of a modified BFGS-type method for unconstrained optimization
- Variable Metric Method for Minimization
- Variance algorithm for minimization
Cited in
(16)- New results on superlinear convergence of classical quasi-Newton methods
- Rates of superlinear convergence for classical quasi-Newton methods
- Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
- Towards explicit superlinear convergence rate for SR1
- Non-asymptotic superlinear convergence of standard quasi-Newton methods
- Regularized Newton Method with Global \({\boldsymbol{\mathcal{O}(1/{k}^2)}}\) Convergence
- Hessian averaging in stochastic Newton methods achieves superlinear convergence
- Greedy PSB methods with explicit superlinear convergence
- An overview of nonlinear optimization
- Distributed adaptive greedy quasi-Newton methods with explicit non-asymptotic convergence bounds
- Panda: partially approximate Newton methods for distributed minimax optimization with unbalanced dimensions
- Accelerated adaptive cubic regularized quasi-Newton methods
- Convergence analysis of a regularized Newton method with generalized regularization terms for unconstrained convex optimization problems
- Quasi-Newton methods for monotone inclusions: efficient resolvent calculus and primal-dual algorithms
- Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization
- Non-asymptotic global convergence rates of BFGS with exact line search
This page was built for publication: Greedy quasi-Newton methods with explicit superlinear convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853572)
