On a Faster $R$-Linear Convergence Rate of the Barzilai-Borwein Method
Preprint
Abstract
The Barzilai-Borwein (BB) method has demonstrated great empirical success in nonlinear optimization. However, the convergence speed of BB method is not well understood, as the known convergence rate of BB method for quadratic problems is much worse than the steepest descent (SD) method. Therefore, there is a large discrepancy between theory and practice. To shrink this gap, we prove that the BB method converges $R$-linearly at a rate of $1-1/\kappa$, where $\kappa$ is the condition number, for strongly convex quadratic problems. In addition, an example with the theoretical rate of convergence is constructed, indicating the tightness of our bound.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Achieving geometric convergence for distributed optimization with Barzilai-Borwein step sizesScience China Information Sciences, 2021
- A family of spectral gradient methods for optimizationComputational Optimization and Applications, 2019
- Quadratic regularization projected Barzilai–Borwein method for nonnegative matrix factorizationData Mining and Knowledge Discovery, 2014
- A New Analysis on the Barzilai-Borwein Gradient MethodJournal of the Operations Research Society of China, 2013
- What is the worst case behavior of the simplex algorithm?2009
- Projected Barzilai–Borwein method for large-scale nonnegative image restorationInverse Problems in Science and Engineering, 2007
- On the asymptotic behaviour of some new gradient methodsMathematical Programming, 2005
- Alternate step gradient method*Optimization, 2003
- R-linear convergence of the Barzilai and Borwein gradient methodIMA Journal of Numerical Analysis, 2002
- On the Barzilai and Borwein choice of steplength for the gradient methodIMA Journal of Numerical Analysis, 1993