Convergence conditions, line search algorithms and trust region implementations for the Polak-Ribière conjugate gradient method. (English) Zbl 1087.90086

Summary: We study globally convergent implementations of the Polak-Ribière (PR) conjugate gradient method for the unconstrained minimization of continuously differentiable functions. More specifically, first we state sufficient convergence conditions, which imply that limit points produced by the PR iteration are stationary points of the objective function and we prove that these conditions are satisfied, in particular, when the objective function has some generalized convexity property and exact line searches are performed. In the general case, we show that the convergence conditions can be enforced by means of various inexact line search schemes where, in addition to the usual acceptance criteria, further conditions are imposed on the stepsize. Then we define a new trust region implementation, which is compatible with the behavior of the PR method in the quadratic case, and may perform different linesearches in dependence of the norm of the search direction. In this framework, we show also that it is possible to define globally convergent modified PR iterations that permit exact linesearches at every iteration. Finally, we report the results of a numerical experimentation on a set of large problems.


90C52 Methods of reduced gradient type
Full Text: DOI


[1] Hestenes MR, Journal of Reseach Natural Bureau of Standards Section 5 49 pp 409– (1952)
[2] Dixon LCW, Software for Numerical Mathematics pp pp. 193–216– (1973)
[3] Fletcher R, Practical Methods of Optimization (1987)
[4] DOI: 10.1093/comjnl/7.2.149 · Zbl 0132.11701
[5] DOI: 10.1137/0802003 · Zbl 0767.90082
[6] Hestenes MR, Conjugate Direction Methods in Optimization (1980)
[7] DOI: 10.1007/BF00941472 · Zbl 0795.90067
[8] DOI: 10.1007/BF00940464 · Zbl 0702.90077
[9] Polak E, Revue Francaise d’Informatique et de Recherche Opérationnelle 16 pp 35– (1969)
[10] DOI: 10.1007/BF01582011 · Zbl 0579.90079
[11] DOI: 10.1287/moor.3.3.244 · Zbl 0399.90077
[12] DOI: 10.1137/0715085 · Zbl 0408.90071
[13] Zoutendijk G, Integer and Nonlinear Programming pp pp. 37–86– (1970)
[14] DOI: 10.1093/imanum/5.1.121 · Zbl 0578.65063
[15] Powell MJD, Lecture Notes in Mathematics 1066 pp pp. 122–141– (1984)
[16] DOI: 10.1137/1028154 · Zbl 0624.90091
[17] DOI: 10.1137/S1052623494268443 · Zbl 0957.65062
[18] Grippo L, Mathematical Programming 78 pp 375– (1997)
[19] DOI: 10.1007/s102550200010 · Zbl 1114.90479
[20] Ortega JM, Iterative Solution of Nonlinear Equations in Several Variables (1970)
[21] Polijak BT, Introduction to Optimization (1987)
[22] Bazaraa MS, Nonlinear Programming (1993)
[23] Bertsekas DP, Nonlinear Programming (1999)
[24] DOI: 10.1007/BF02591934 · Zbl 0576.90087
[25] DOI: 10.1007/BF00939550 · Zbl 0619.90063
[26] DOI: 10.1137/S1052623494266365 · Zbl 0898.90119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.