×

A new three-term conjugate gradient algorithm for unconstrained optimization. (English) Zbl 1321.65092

The authors present a new three-term conjugate gradient algorithm for unconstrained optimization by minimization of the one-parametric quadratic model of the objective function. Under certain assumptions, the global convergence analysis of the proposed algorithm for uniformly convex functions is established. Some preliminary numerical results on a collection of 800 large-scale unconstrained optimization test problems are provided to compare the proposed algorithm with other existing ones and show that the considered algorithm is indeed more efficient and more robust.

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C25 Convex programming
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Bayati, A.Y., Sharif, W.H.: A new three-term conjugate gradient method for unconstrained optimization. Can. J. Sci. Eng. Math. 1(5), 108-124 (2010)
[2] Andrei, N.: Scaled conjugate gradient algorithms for unconstrained optimization. Comput. Optim. Appl. 38, 401-416 (2007) · Zbl 1168.90608 · doi:10.1007/s10589-007-9055-7
[3] Andrei, N.: Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization. Optimi. Methods Softw. 22, 561-571 (2007) · Zbl 1270.90068 · doi:10.1080/10556780600822260
[4] Andrei, N.: Another Collection of Large-scale Unconstrained Optimization Test Functions. ICI Technical Report, January 30 (2013)
[5] Andrei, N.: Acceleration of conjugate gradient algorithms for unconstrained optimization. Appl. Math. Comput. 213, 361-369 (2009) · Zbl 1172.65027 · doi:10.1016/j.amc.2009.03.020
[6] Andrei, N.: A modified Polak-Ribière-Polyak conjugate gradient algorithm for unconstrained optimization. Optimization 60, 1457-1471 (2011) · Zbl 1233.90255 · doi:10.1080/02331931003653187
[7] Andrei, N.: On three-term conjugate gradient algorithms for unconstrained optimization. Appl. Math. Comput. 219, 6316-6327 (2013) · Zbl 1274.90372 · doi:10.1016/j.amc.2012.11.097
[8] Andrei, N.: A simple three-term conjugate gradient algorithm for unconstrained optimization. J. Comput. Appl. Math. 241, 19-29 (2013) · Zbl 1258.65056 · doi:10.1016/j.cam.2012.10.002
[9] Beale, E.M.L.: A derivative of conjugate gradients In: Lootsma, F.A (ed.) Numerical Methods for Nonlinear Optimization, pp. 39-43. Academic, London (1972)
[10] Cheng, W.: A two-term PRP-based descent method. Numer. Funct. Anal. Optim. 28, 1217-1230 (2007) · Zbl 1138.90028 · doi:10.1080/01630560701749524
[11] Dai, Y.H., Kou, C.X.: A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAMJ. Optim. 23(1), 296-320 (2013) · Zbl 1266.49065
[12] Dai, Y.H., Liao, L.Z.: New conjugate conditions and related nonlinear conjugate gradient methods. Appl. Math. Optim. 43, 87-101 (2001) · Zbl 0973.65050 · doi:10.1007/s002450010019
[13] Dai, Y.H., Yuan, Y.: A nonlinear conjugate gradient method with a strong global convergence property. SIAM J. Optim. 10, 177-182 (1999) · Zbl 0957.65061 · doi:10.1137/S1052623497318992
[14] Deng, N.Y., Li, Z.: Global convergence of three terms conjugate gradient methods. Optim. Method Softw. 4, 273-282 (1995) · doi:10.1080/10556789508805593
[15] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[16] Gilbert, J.C., Lemaréchal, C.: Some numerical experiments with variable storage quasi-Newton algorithm. Math. Program. 45, 407-435 (1989) · Zbl 0694.90086 · doi:10.1007/BF01589113
[17] 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 · doi:10.1137/030601880
[18] Hestenes, M.R., Stiefel, E.L.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[19] Liu, D.C., Nocedal, J.: On the limited BFGS method for large scale optimization. Math. Program. 45, 503-528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116
[20] Liu, D., Xu, G.: Symmetric Perry conjugate gradient method. Comput. Optim. Appl. 56, 317-341 (2013) · Zbl 1312.90088 · doi:10.1007/s10589-013-9558-3
[21] McGuire, M.F., Wolfe, P.: Evaluating a Restart Procedure for Conjugate Gradients. Report RC-4382, IBM Research Center, Yorktown Heights (1973) · Zbl 0696.90048
[22] Moré, J.J., Thuente, D.J.: On Linesearch Algorithms with Guaranteed Sufficient Decrease. Mathematics and Computer Science Division Preprint MCS-P153-0590. Argonne National Laboratory, Argonne, IL (1990) · Zbl 0694.90086
[23] Narushima, Y., Yabe, H., Ford, J.A.: A three-term conjugate gradient method with sufficient descent property for unconstrained optimization. SIAM J. Optim. 21, 212-230 (2011) · Zbl 1250.90087 · doi:10.1137/080743573
[24] Nash, S.G.: User’s Guide for TN-TNBC: Fortran Routines for Nonlinear Optimization. Report 397, Mathematical Sciences Department, The John Hopkins University, Baltimore · Zbl 1049.90004
[25] Nash, S.G., Nocedal, J.: A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization. SIAM J. Optim. 1, 358-372 (1991) · Zbl 0756.65091 · doi:10.1137/0801023
[26] Nazareth, L.: A conjugate direction algorithm without line search. J. Optim. Theor. Appl. 23, 373-387 (1977) · Zbl 0348.65061 · doi:10.1007/BF00933447
[27] Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comp. 35, 773-782 (1980) · Zbl 0464.65037 · doi:10.1090/S0025-5718-1980-0572855-7
[28] Nocedal, J.: Conjugate gradient methods and nonlinear optimization. In: Adams, L., Nazareth, J.L. (eds.) Linear and Nonlinear Conjugate Gradient Related Methods, pp. 9-23. SIAM (1996) · Zbl 0866.65037
[29] Perry, A.: A modified conjugate gradient algorithm. Oper. Res. Tech. Notes 26(6), 1073-1078 (1978) · Zbl 0419.90074 · doi:10.1287/opre.26.6.1073
[30] Powell, M.J.D.: Nonconvex minimization calculations and the conjugate gradient method. Numerical Analysis (Dundee, 1983), Lecture Notes in Mathematics, vol. 1066, pp. 122-141. Springer, Berlin (1984) · Zbl 0531.65035
[31] Shanno, D.F., Phua, K.H.: Algorithm 500, Minimization of unconstrained multivariate functions. ACM Trans. Math. Soft. 2, 87-94 (1976) · Zbl 0319.65042 · doi:10.1145/355666.355673
[32] Sugiki, K., Narushima, Y., Yabe, H.: Globally convergent three-term conjugate gradient methods that use secant conditions and generate descent search directions for unconstrained optimization. J. Optim. Theory Appl. 153(3), 733-757 (2012) · Zbl 1262.90170 · doi:10.1007/s10957-011-9960-x
[33] Wolfe, P.: Convergence conditions for ascent methods. SIAM Rev. 11, 226-235 (1968) · Zbl 0177.20603 · doi:10.1137/1011036
[34] Wolfe, P.: Convergence conditions for ascent methods, (II): some corrections. SIAM Rev. 13, 185-188 (1971) · Zbl 0216.26901 · doi:10.1137/1013035
[35] 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 · doi:10.1093/imanum/drl016
[36] Zhang, L., Zhou, W., Li, D.H.: Some descent three-term conjugate gradient methods and their global convergence. Optim. Methods Softw. 22, 697-711 (2007) · Zbl 1220.90094 · doi:10.1080/10556780701223293
[37] Zhang, J., Xiao, Y., Wei, Z.: Nonlinear conjugate gradient methods with sufficient descent condition for large-scale unconstrained optimization. Math. Probl. Eng. 2009 (2009). Article ID 243290 doi:10.1155/2009/243290 · Zbl 1184.65066
[38] Zoutendijk, G.: Nonlinear programming, computational methods. In: Abadie, J. (ed.) Integer and Nonlinear Programming, pp. 38-86. North-Holland, Amsterdam (1970) · 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.