Convergence properties of nonlinear conjugate gradient methods

Recently, important contributions on convergence studies of conjugate gradi ent methods were made by Gilbert and Nocedal [SIAM J. Optim., 2 (1992), pp. 21-42]. They introduce a "sufficient descent condition" to establish globa l convergence results. Although this condition is not needed in the converg ence analyses of Newton and quasi-Newton methods, Gilbert and Nocedal hint that the sufficient descent condition, which was enforced by their two-stag e line search algorithm, may be crucial for ensuring the global convergence of conjugate gradient methods. This paper shows that the sufficient descen t condition is actually not needed in the convergence analyses of conjugate gradient methods. Consequently, convergence results on the Fletcher-Reeves - and Polak-Ribiere-type methods are established in the absence of the suff icient descent condition. To show the differences between the convergence properties of Fletcher-Reev es- and Polak-Ribiere-type methods, two examples are constructed, showing t hat neither the boundedness of the level set nor the restriction beta(k) gr eater than or equal to 0 can be relaxed for the Polak-Ribiere-type methods.