×

A globally convergent version of the Polak-Ribière conjugate gradient method. (English) Zbl 0887.90157

Summary: We propose a new line search algorithm that ensures global convergence of the Polak-Ribière conjugate gradient method for the unconstrained minimization of nonconvex differentiable functions. In particular, we show that with this line search every limit point produced by the Polak-Ribière iteration is a stationary point of the objective function. Moreover, we define adaptive rules for the choice of the parameters in a way that the first stationary point along a search direction can be eventually accepted when the algorithm is converging to a minimum point with positive definite Hessian matrix. Under strong convexity assumptions, the known global convergence results can be reobtained as a special case. From a computational point of view, we may expect that an algorithm incorporating the step-size acceptance rules proposed here will retain the same good features of the Polak-Ribière method, while avoiding pathological situations.

MSC:

90C52 Methods of reduced gradient type
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with inexact line search,IMA Journal on Numerical Analysis 5 (1985) 121–124. · Zbl 0578.65063 · doi:10.1093/imanum/5.1.121
[2] R. De Leone, M. Gaudioso and L. Grippo, Stopping criteria for line search methods without derivatives,Mathematical Programming 30 (1984) 285–300. · Zbl 0576.90087 · doi:10.1007/BF02591934
[3] L.C.W. Dixon, Nonlinear optimization: A survey of the state of the art, in: D.J. Evans, ed.,Software for numerical mathematics (Academic Press, New York, 1973) pp. 193–216.
[4] R. Fletcher,Practical methods of optimization (John Wiley, New York, 1987). · Zbl 0905.65002
[5] R. Fletcher and C.M. Reeves, Function minimization by conjugate gradients,Computing Journal 7 (1964) 149–154. · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149
[6] J.C. Gilbert and J. Nocedal, Global convergence of conjugate gradient methods for optimization,SIAM Journal on Optimization 2 (1992) 21–42. · Zbl 0767.90082 · doi:10.1137/0802003
[7] L. Grippo, F. Lampariello and S. Lucidi, Global convergence and stabilization of unconstrained minimization methods without derivatives,Journal of Optimization Theory and Applications 56 (1988) 385–406. · Zbl 0619.90063 · doi:10.1007/BF00939550
[8] M.R. Hestenes,Conjugate direction methods in optimization (Springer, New York, 1980). · Zbl 0439.49001
[9] M.R. Hestenes and E.L. Stiefel, Methods of conjugate gradients for solving linear systems,J. Res. Nat. Bur. Standards Sect. 5 49 (1952) 409–36. · Zbl 0048.09901 · doi:10.6028/jres.049.044
[10] K.M. Khoda, Y. Liu and C. Storey, Generalized Polak-Ribiere algorithm,Journal on Optimization Theory and Applications 75 (1992) 345–354. · Zbl 0795.90067 · doi:10.1007/BF00941472
[11] Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, part 1: Theory,Journal on Optimization Theory and Applications 69 (1991) 129–137. · Zbl 0724.90067 · doi:10.1007/BF00940464
[12] E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées,Revue Francaise d’Informatique et de Recherche Opérationnelle 16 (1969) 35–43.
[13] M.J.D. Powell, Nonconvex minimization calculations and the conjugate gradient method, in: Lecture Notes in Mathematics 1066 (Springer, Berlin, 1984) pp. 122–141. · Zbl 0531.65035
[14] M.J.D. Powell, Convergence properties of algorithms for nonlinear optimization,SIAM Review 28 (1986) 487–500. · Zbl 0624.90091 · doi:10.1137/1028154
[15] D.F. Shanno, Globally convergent conjugate gradient algorithms,Mathematical Programming 33 (1985) 61–67. · Zbl 0579.90079 · doi:10.1007/BF01582011
[16] D.F. Shanno, Conjugate gradient methods with inexact searches,Mathematics of Operations Research 3 (1978) 244–2567. · Zbl 0399.90077 · doi:10.1287/moor.3.3.244
[17] D.F. Shanno, On the convergence of a new conjugate gradient algorithm,SIAM Journal on Numerical Analysis 15 (1978) 1247–1257. · Zbl 0408.90071 · doi:10.1137/0715085
[18] G. Zoutendijk, Nonlinear programming computational methods, in: J. Abadie, ed.,Integer and Nonlinear Programming (North-Holland, Amsterdam, 1970) pp. 37–86. · Zbl 0336.90057
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.