On the worst case performance of the steepest descent algorithm for quadratic functions

\begin{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 $ \Or(C\log(1/\eps)) $ iterations to achieve a precision $ \eps $, where $ C $ is the Hessian condition number. We show how to construct a sequence of step lengths with which the algorithm stops in $ \Or(\sqrt{C}\log(1/\eps)) $ iterations, with a bound almost exactly equal to that of the Krylov space methods. \end{abstract}

Citation

Federal University of Santa Catarina, Brazil, September 2014.