×

Globally convergent Polak-Ribière-Polyak conjugate gradient methods under a modified Wolfe line search. (English) Zbl 1185.65100

It is well known that global convergence has not been established for the Polak-Ribiere-Polyak (PRP) conjugate gradient method using the standard Wolfe conditions. In this paper some global convergence results for the PRP-type conjugate gradient method are established, where the step-length is computed by a modified Wolfe line search. Some efficient choices for \(\beta_k\) which can ensure the descent property of the search direction are also discussed. Preliminary numerical experiments on a set of a large-scale problems show that the computational efficiency of the PRP method is not deteriorated.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming
65Y20 Complexity and performance of numerical algorithms

Software:

minpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, T.; Storey, D., Efficient hybrid conjugate gradient techniques, Journal of Optimization Theory and Application, 64, 379-394 (1990) · Zbl 0666.90063
[2] Al-Baali, A., Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA Journal of Numerical Analysis, 5, 121-124 (1985) · Zbl 0578.65063
[3] Dai, Y., Conjugate gradient methods with Armijo-type line searches, Acta Mathematicae Applicatae Sinica, English Series, 18, 1, 123-130 (2002) · Zbl 1114.90479
[4] Dai, Y.; Han, J.; Liu, G.; Sun, D.; Yin, H.; Yan, Y., Convergence properties of nonlinear conjugate methods, SIAM Journal On Optimization, 2, 345-358 (1999) · Zbl 0957.65062
[5] Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Mathematical Programming Series A, 91, 201-213 (2002) · Zbl 1049.90004
[6] Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, Computer Journal, 7, 149-154 (1964) · Zbl 0132.11701
[7] Gibert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM Journal on Optimization, 2, 21-42 (1992) · Zbl 0767.90082
[8] Grippo, L.; Lucidi, S., A globally convergent version of the Polak-Ribière gradient method, Mathematics Programming, 78, 375-391 (1997) · Zbl 0887.90157
[9] Grippo, L.; Lucidi, S., Convergence conditions, line search algorithms and trust region implementations for the Polak-Ribière conjugate gradient method, Optimization Methods and Software, 20, 1, 71-98 (2005) · Zbl 1087.90086
[10] Hager, W. W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16, 170-192 (2005) · Zbl 1093.90085
[11] Hestenes, M. R.; Stiefel, E., Method of conjugate gradient for solving linear equations, Journal of Research of the National Bureau of Standards, 49, 409-436 (1952) · Zbl 0048.09901
[12] Hu, Y. F.; Storey, C., Global convergence result for conjugate gradient method, Journal of Optimization Theory and Application, 71, 399-405 (1991) · Zbl 0794.90063
[13] Morè, J. J.; Garbow, B. S.; Hillstrome, K. E., Testing unconstrained optimization software, Transactions of the ACM on Mathematical Software, 7, 17-41 (1981) · Zbl 0454.65049
[14] Nocedal, J.; Wright, S. J., Numerical optimization, (Springer Series in Operations Research (1999), Springer: Springer New York) · Zbl 1104.65059
[15] E. Polak, G. Ribière, Note Sur la convergence de directions conjugèes, Rev. Francaise Informat Recherche Operationelle, 3e Annèe 16 (1969) 35-43.; E. Polak, G. Ribière, Note Sur la convergence de directions conjugèes, Rev. Francaise Informat Recherche Operationelle, 3e Annèe 16 (1969) 35-43.
[16] Polyak, B. T., The conjugate gradient method in extreme problems, USSR Computational Mathematics and Mathematical Physics, 9, 94-112 (1969) · Zbl 0229.49023
[17] Powell, M. J.D., Nonconvex minimization calculations and the conjugate gradient method, (Lecture Notes in Mathematics, vol. 1066 (1984), Springer-Verlag: Springer-Verlag Berlin), 122-141 · Zbl 0531.65035
[18] Wei, Z.; Li, G.; Qi, L., Global convergence of the Polak-Ribière-Polyak conjugate gradient method with inexact line searches for nonconvex unconstrained optimization problems, Mathematics of Computation, 77, 2173-2193 (2008) · Zbl 1198.65091
[19] Yu, G.; Guan, L.; Wei, Z., A globally convergent Polak-Ribière-Polyak conjugate gradient method with Armijo-type line search, Numerical Mathematics: A Journal of Chinese Universities English Series, 15, 357-367 (2006) · Zbl 1132.65059
[20] Yu, G.; Zhao, Y.; Wei, Z., A descent nonlinear conjugate gradient method for large-scale unconstrained optimization, Applied Mathematics and Computations, 187, 636-643 (2007) · Zbl 1117.65097
[21] Yuan, G., Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems, Optimization Letters, 3, 11-21 (2009) · Zbl 1154.90623
[22] Zoutendijk, G., Nonlinear programming computational methods, (Abadie, J., Integer and Nonlinear Programming (1970), North-Holland: North-Holland Amsterdam), 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.