Optimization Online


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

Clovis Gonzaga (ccgonzaga1***at***gmail.com)

Abstract: \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}

Keywords: Steepesd descent, complexity

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Federal University of Santa Catarina, Brazil, September 2014.

Download: [PDF]

Entry Submitted: 09/11/2014
Entry Accepted: 09/11/2014
Entry Last Modified: 07/09/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society