Back to Search
Start Over
On the worst case performance of the steepest descent algorithm for quadratic functions.
- Source :
- Mathematical Programming; Nov2016, Vol. 160 Issue 1/2, p307-320, 14p
- Publication Year :
- 2016
-
Abstract
- The existing choices for the step lengths used by the classical steepest descent algorithm for minimizing a convex quadratic function require in the worst case $$ \mathcal{{O}}(C\log (1/\varepsilon )) $$ iterations to achieve a precision $$ \varepsilon $$ , where C is the Hessian condition number. We show how to construct a sequence of step lengths with which the algorithm stops in $$ \mathcal{{O}}(\sqrt{C}\log (1/\varepsilon )) $$ iterations, with a bound almost exactly equal to that of the Conjugate Gradient method. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 160
- Issue :
- 1/2
- Database :
- Complementary Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 118668995
- Full Text :
- https://doi.org/10.1007/s10107-016-0984-8