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

• 成果类型: Article
• 署名作者: Gonzaga, Clovis C.
• 署名单位: Universidade Federal de Santa Catarina (UFSC)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0984-8
• 发表日期: 2016
• 页码: 307-320
• 关键词: optimum gradient-method; barzilai

摘要

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 iterations to achieve a precision , where C is the Hessian condition number. We show how to construct a sequence of step lengths with which the algorithm stops in iterations, with a bound almost exactly equal to that of the Conjugate Gradient method.