×

Convergence of the Polak-Ribiére-Polyak conjugate gradient method. (English) Zbl 1120.49027

In this paper, an new kind of Armijo-type line search has been proposed for guaranteeing the global convergence of the Polak-Ribiére-Polyak conjugate gradient method for unconstrained minimizing functions that have Lipschitz continouous partial derivatives. The global convergence and linear convergence rate were analyzed under some mild conditions. Numerical results show that the proposed method with the new Armijo-type line search is more efficient than other similar methods in practical computation.

MSC:

49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Software:

minpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armijo, L., Minimization of functions having Lipschits continuous partial derivatives, Pacific J. Math., 16, 1-3 (1966) · Zbl 0202.46105
[2] Birgin, E. G.; Martinez, J. M., A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 117-128 (2001) · Zbl 0990.90134
[3] Cohen, A., Rate of convergence of several conjugate gradient algorithms, SIAM J. Numer. Anal., 9, 248-259 (1972) · Zbl 0279.65051
[4] Dai, Y. H., New properties of a nonlinear conjugate gradient method, Numer. Math., 89, 83-98 (2001) · Zbl 1006.65063
[5] Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10, 1, 177-182 (1999) · Zbl 0957.65061
[6] Dai, Y. H.; Ni, Q., Testing different conjugate gradient methods for large-scale unconstrained optimization, J. Comput. Math., 21, 3, 311-320 (2003) · Zbl 1041.65048
[7] Dai, Y. H.; Fletcher, R., On the asymptotic behaviour of some new gradient methods, Math. Prog., 103, 541-559 (2005) · Zbl 1099.90038
[8] Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701
[9] Grippo, L.; Lucidi, S., Convergence conditions, line search algorithms and trust region implementations for the Polak Ribiére conjugate gradient method, Optim. Methods Softw., 20, 1, 71-98 (2005) · Zbl 1087.90086
[10] Grippo, L.; Lucidi, S., A globally convergent version of the Polak-Ribiére conjugate gradient method, Math. Prog., 78, 375-391 (1997) · Zbl 0887.90157
[11] Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 1, 21-42 (1992) · Zbl 0767.90082
[12] Goldstein, A. A., On steepest descent, SIAM J. Control, 3, 147-151 (1965) · Zbl 0221.65094
[13] Hestenes, M. R.; Stiefel, E., Method of conjugate gradient for solving linear systems, J. Res. Nat. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[14] Khoda, K. M.; Liu, Y.; Storey, C., Generalized Polak-Ribiére algorithm, J. Optim. Theory Appl., 75, 345-354 (1992) · Zbl 0795.90067
[15] Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 17-41 (1981) · Zbl 0454.65049
[16] Nocedal, J.; Wright, J. S., Numerical Optimization (1999), Springer-Verlag: Springer-Verlag New York, Inc. · Zbl 0930.65067
[17] Nocedal, J., Theory of algorithm for unconstrained optimization, Acta Numer., 1, 199-242 (1992) · Zbl 0766.65051
[18] Polak, E.; Ribiére, G., Note sur la convergence de directions conjuguées, Rev. Francaise Infomat Recherche Operatonelle, 3e Année, 16, 35-43 (1969) · Zbl 0174.48001
[19] Polyak, B. T., The conjugate gradient method in extreme problems, USSR Comput. Math. Math. Phys., 9, 94-112 (1969) · Zbl 0229.49023
[20] Sun, J.; Zhang, J. P., Convergence of conjugate gradient methods without line search, Ann. Oper. Res., 103, 161-173 (2001) · Zbl 1014.90071
[21] Sun, J.; Yang, X. Q.; Chen, X. D., Quadratic cost flow and the conjugate gradient method, European J. Oper. Res., 164, 104-114 (2005) · Zbl 1132.90374
[22] Shanno, D. F., Conjugate gradient methods with inexact line searches, Math. Oper. Res., 3, 244-256 (1978) · Zbl 0399.90077
[23] Shanno, D. F., On the convergence of a new conjugate gradient algorithm, SIAM J. Numer. Anal., 15, 1247-1257 (1978) · Zbl 0408.90071
[24] Shi, Z. J., Restricted PR conjugate gradient method and its global convergence, Adv. Math., 31, 1, 47-55 (2002), (in Chinese) · Zbl 1264.90179
[25] Shi, Z. J.; Shen, J., Convergence of descent method without line search, Appl. Math. Comput., 167, 94-107 (2005) · Zbl 1084.65064
[26] Shi, Z. J.; Shen, J., Step-size estimation for unconstrained optimization methods, Comput. Appl. Math., 24, 3, 1-18 (2005)
[27] Wolfe, P., Convergence conditions for ascent methods, SIAM Rev., 11, 226-235 (1969) · Zbl 0177.20603
[28] Yuan, Y., Numerical Methods for Nonlinear Programming (1993), Shanghai Scientific & Technical Publishers
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.