Convergence properties of nonlinear conjugate gradient methods

Y. Dai, J. Han, G. Liu, Defeng Sun, H. Yin, Y.-X. Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

150 Citations (Scopus)

Abstract

Recently, important contributions on convergence studies of conjugate gradient methods were made by Gilbert and Nocedal [SIAM J. Optim., 2 (1992), pp. 21-42]. They introduce a "sufficient descent condition" to establish global convergence results. Although this condition is not needed in the convergence analyses of Newton and quasi-Newton methods, Gilbert and Nocedal hint that the sufficient descent condition, which was enforced by their two-stage line search algorithm, may be crucial for ensuring the global convergence of conjugate gradient methods. This paper shows that the sufficient descent condition is actually not needed in the convergence analyses of conjugate gradient methods. Consequently, convergence results on the Fletcher-Reeves-and Polak-Ribière-type methods are established in the absence of the sufficient descent condition. To show the differences between the convergence properties of Fletcher-Reeves-and Polak-Ribière-type methods, two examples are constructed, showing that neither the boundedness of the level set nor the restriction ?k ? 0 can be relaxed for the Polak-Ribière-type methods.
Original languageEnglish
Pages (from-to)345-358
Number of pages14
JournalSIAM Journal on Optimization
Volume10
Issue number2
Publication statusPublished - 1 Jan 1999
Externally publishedYes

Keywords

  • Conjugate gradient method
  • Descent condition
  • Global convergence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software

Cite this