×

\(n\)-step quadratic convergence of the MPRP method with a restart strategy. (English) Zbl 1221.65144

Unconstrained minimization of a continuously differentiable function \(f: \mathbb{R}^n\to\mathbb{R}\) is considered. The authors investigate the convergence rate of the modified Polak-Ribière-Pólyak conjugate gradient method (further abbreviated MPRP method). They show that the \(r\)-step restart MPRP method (further abbreviated RMPRP method) with a special choice of the initial step-length with standard Armijo line-search, and under appropriate conditions will be globally convergent for uniformly convex objective functions. Further it is shown that under additional assumptions, \(n\)-step quadratic convergence can be proved. The results of numerical experiments presented in the concluding part of the paper support the theoretically derived convergence properties of the RMPRP method. Besides, the results show a good performance of the method in comparison with the MPRP method and some other methods published in the literature.

MSC:

65K05 Numerical mathematical programming methods

Software:

L-BFGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nocedal, J., Conjugate gradient methods and nonlinear optimization, (Adams, L.; Nazareth, J. L., Linear and Nonlinear Conjugate Gradient-Related Method (1996), SIAM: SIAM Philadelphia), 9-23 · Zbl 0866.65037
[2] Polak, E., Optimization: Algorithms and Consistent Approximations (1997), Springer: Springer New York · Zbl 0899.90148
[3] Fletcher, R., (Practical Methods of Optimization. Practical Methods of Optimization, Unconstrained Optimization, vol. I (1987), Wiley: Wiley New York) · Zbl 0905.65002
[4] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer: Springer New York · Zbl 1104.65059
[5] Yuan, Y.; Sun, W., Optimization Theory and Methods (1997), Science Press: Science Press Beijing, (in Chinese)
[6] Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, J. Comput., 7, 149-154 (1964) · Zbl 0132.11701
[7] Polak, B.; Ribière, G., Note sur la convergence de directions conjugées, Rev. Fr. Imform. Rech. Oper., 16, 35-43 (1969) · Zbl 0174.48001
[8] Polyak, B. T., The conjugate gradient method in extremum problems, USSR Comput. Math. Math. Phys., 9, 94-112 (1969) · Zbl 0229.49023
[9] Hestenes, M. R.; Stiefel, E. L., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[10] Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient with a strong global convergence property, SIAM J. Optim., 10, 177-182 (2000)
[11] Hager, W. W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 170-192 (2005) · Zbl 1093.90085
[12] Y.H. Dai, Y. Yuan, Nonlinear Conjugate Gradient Methods, Shanghai Science and Technology, Shanghai, 2000.; Y.H. Dai, Y. Yuan, Nonlinear Conjugate Gradient Methods, Shanghai Science and Technology, Shanghai, 2000.
[13] Dai, Y. H.; Yuan, Y., A three-parameter family of nonlinear conjugate gradient methods, Math. Comput., 70, 1155-1167 (2000) · Zbl 1030.90141
[14] Hager, W. W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 35-58 (2006) · Zbl 1117.90048
[15] Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 21-42 (1992) · Zbl 0767.90082
[16] Grippo, L.; Luidi, S., A globally convergent version of the Polak-Ribière gradient method, Math. Program., 78, 375-391 (1997) · Zbl 0887.90157
[17] Zhang, L.; Zhou, W.; Li, D. H., A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal., 26, 629-640 (2006) · Zbl 1106.65056
[18] Zhang, L.; Zhou, W.; Li, D. H., Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numer. Math., 104, 561-572 (2006) · Zbl 1103.65074
[19] Crowder, H. P.; Wolfe, P., Linear convergence of the conjugate gradient method, IBM J. Res. Dev., 16, 431-433 (1972) · Zbl 0263.65068
[20] Powell, M. J.D., Some convergence properties of the conjugate gradient method, Math. Program., 11, 42-49 (1976) · Zbl 0356.65056
[21] Burmeister, W., Die Konvergenzordnung des Fletcher-Powell Algorithmus, Z. Angew. Math. Mech., 53, 693-699 (1973) · Zbl 0269.90039
[22] Cohen, A., Rate of convergence of several conjugate gradient algorithms, SIAM J. Numer. Anal., 9, 248-259 (1972) · Zbl 0279.65051
[23] Ritter, K., On the rate of superlinear convergence of a class of variable metric methods, Numer. Math., 35, 293-313 (1980) · Zbl 0459.65043
[24] M.F. McGuire, P. Wolfe, Evaluating a restart procedure for conjugate gradients, Report RC-4382, IBM Research Center, Yorktown Heights, 1973.; M.F. McGuire, P. Wolfe, Evaluating a restart procedure for conjugate gradients, Report RC-4382, IBM Research Center, Yorktown Heights, 1973.
[25] Beale, E. M.L., A derivative of conjugate gradients, (Lootsma, F. A., Numerical Methods for Nonlinear Optimization (1972), Academic Press: Academic Press New York), 39-43 · Zbl 0279.65052
[26] Powell, M. J.D., Restart procedure of the conjugate gradient method, Math. Program., 2, 241-254 (1977) · Zbl 0396.90072
[27] Dai, Y. H.; Yuan, Y., Convergence properties of Beale-Powell restart algorithm, Science in China., 41, 1142-1150 (1998) · Zbl 0919.65042
[28] Dai, Y. H.; Liao, L. Z.; Li, D., On restart procedure for the conjugate gradient method, Numer. Algorithms, 35, 249-260 (2004) · Zbl 1137.90669
[29] Andrei, N., An unconstrained optimization test functions collection, Appl. Math. Optim., 10, 147-161 (2008) · Zbl 1161.90486
[30] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[31] Liu, D. C.; Nocedal, J., On the limited-memory BFGS method for large scale optimization, Math. Program., 45, 503-528 (1989) · Zbl 0696.90048
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.