×

Hybrid conjugate gradient algorithm for unconstrained optimization. (English) Zbl 1168.90017

Summary: A new hybrid conjugate gradient algorithm is proposed and analyzed. The parameter \(\beta _{k }\) is computed as a convex combination of the Polak-Ribière-Polyak and the Dai-Yuan conjugate gradient algorithms, i.e. \(\beta^N_k =(1 - \theta _{k })\beta^PRP_k +\theta _{k } \beta^DY_k \). The parameter \(\theta _{k }\) in the convex combination is computed in such a way that the conjugacy condition is satisfied, independently of the line search. The line search uses the standard Wolfe conditions. The algorithm generates descent directions and when the iterates jam the directions satisfy the sufficient descent condition. Numerical comparisons with conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that this hybrid computational scheme outperforms the known hybrid conjugate gradient algorithms.

MSC:

90C52 Methods of reduced gradient type
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2, 35–58 (2006) · Zbl 1117.90048
[2] Fletcher, R., Reeves, C.: Function minimization by conjugate gradients. Comput. J. 7, 149–154 (1964) · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149
[3] 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
[4] Fletcher, R.: Unconstrained Optimization. Practical Methods of Optimization, vol. 1. Wiley, New York (1987) · Zbl 0905.65002
[5] Polak, E., Ribière, G.: Note sur la convergence de directions conjuguée. Rev. Fr. Inf. Rech. Oper. 3e Année 16, 35–43 (1969) · Zbl 0174.48001
[6] Poliak, B.T.: The conjugate gradient method in extreme problems. USSR Comput. Math. Math. Phys. 9, 94–112 (1969) · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4
[7] 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
[8] Liu, Y., Storey, C.: Efficient generalized conjugate gradient algorithms, Part 1: Theory. J. Optim. Theory Appl. 69, 129–137 (1991) · Zbl 0724.90067 · doi:10.1007/BF00940464
[9] Touati-Ahmed, D., Storey, C.: Efficient hybrid conjugate gradient techniques. J. Optim. Theory Appl. 64, 379–397 (1990) · Zbl 0687.90081 · doi:10.1007/BF00939455
[10] Hu, Y.F., Storey, C.: Global convergence result for conjugate gradient methods. J. Optim. Theory Appl. 71, 399–405 (1991) · Zbl 0794.90063 · doi:10.1007/BF00939927
[11] Gilbert, J.C., Nocedal, J.: Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2, 21–42 (1992) · Zbl 0767.90082 · doi:10.1137/0802003
[12] Dai, Y.H., Yuan, Y.: An efficient hybrid conjugate gradient method for unconstrained optimization. Ann. Oper. Res. 103, 33–47 (2001) · Zbl 1007.90065 · doi:10.1023/A:1012930416777
[13] 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
[14] Bongartz, I., Conn, A.R., Gould, N.I.M., Toint, P.L.: CUTE: constrained and unconstrained testing environments. ACM Trans. Math. Softw. 21, 123–160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043
[15] Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10, 147–161 (2008) · Zbl 1161.90486
[16] Powell, M.J.D.: Restart procedures of the conjugate gradient method. Math. Program. 2, 241–254 (1977) · Zbl 0396.90072 · doi:10.1007/BF01593790
[17] Yuan, Y.: Analysis on the conjugate gradient method. Optim. Methods Softw. 2, 19–29 (1993) · doi:10.1080/10556789308805532
[18] Powell, M.J.D.: Nonconvex minimization calculations and the conjugate gradient method. In: Numerical Analysis, Dundee, 1983. Lecture Notes in Mathematics, vol. 1066, pp. 122–141. Springer, Berlin (1984)
[19] Dai, Y.H.: Analysis of conjugate gradient methods. Ph.D. Thesis, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Science (1997)
[20] Dai, Y.H.: New properties of a nonlinear conjugate gradient method. Numer. Math. 89, 83–98 (2001) · Zbl 1006.65063 · doi:10.1007/PL00005464
[21] Dai, Y.H., Liao, L.Z., Li, D.: On restart procedures for the conjugate gradient method. Numer. Algorithms 35, 249–260 (2004) · Zbl 1137.90669 · doi:10.1023/B:NUMA.0000021761.10993.6e
[22] Shanno, D.F., Phua, K.H.: Algorithm 500, Minimization of unconstrained multivariate functions. ACM Trans. Math. Softw. 2, 87–94 (1976) · Zbl 0319.65042 · doi:10.1145/355666.355673
[23] Birgin, E., Martínez, J.M.: A spectral conjugate gradient method for unconstrained optimization. Appl. Math. Optim. 43, 117–128 (2001) · Zbl 0990.90134 · doi:10.1007/s00245-001-0003-0
[24] 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
[25] Andrei, N.: Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization. Optim. Methods Softw. 22, 561–571 (2007) · Zbl 1270.90068 · doi:10.1080/10556780600822260
[26] Andrei, N.: A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization. Appl. Math. Lett. 20, 645–650 (2007) · Zbl 1116.90114 · doi:10.1016/j.aml.2006.06.015
[27] Kiwiel, K.C., Murty, K.: Convergence of the steepest descent method for minimizing quasiconvex functions. J. Optim. Theory Appl. 89(1), 221–226 (1996) · Zbl 0866.90094 · doi:10.1007/BF02192649
[28] Dai, Y.H., Han, J.Y., Liu, G.H., Sun, D.F., Yin, X., Yuan, Y.: Convergence properties of nonlinear conjugate gradient methods. SIAM J. Optim. 10, 348–358 (1999) · Zbl 0957.65061 · doi:10.1137/S1052623497318992
[29] Dai, Y.H., Liao, L.Z.: New conjugacy conditions and related nonlinear conjugate gradient methods. Appl. Math. Optim. 43, 87–101 (2001) · Zbl 0973.65050 · doi:10.1007/s002450010019
[30] 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
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.