×

A new class of nonlinear conjugate gradient coefficients with exact and inexact line searches. (English) Zbl 1410.90203

Summary: Conjugate gradient (CG) methods have played an important role in solving large-scale unconstrained optimization. In this paper, we propose a new family of CG coefficients \((\beta_{k})\) that possess sufficient descent conditions and global convergence properties. This new \({\beta}_{k}\) is an extension of the already proven \(\beta_k^{\operatorname{RMIL}}\) from the first author et al. [ibid. 218, No. 22, 11323–11332 (2012; Zbl 1278.65094)]. Global convergence result is established using both exact and inexact line searches. Numerical results show that the performance of the new proposed formula is quite similar to \(\beta_k^{\operatorname{RMIL}}\) and suited to both line searches. Importantly, the performance of this \({\beta}_{k}\) is more efficient and superior than the other well-known \({\beta}_{k}\).

MSC:

90C30 Nonlinear programming
65K10 Numerical optimization and variational techniques
49M37 Numerical methods based on nonlinear programming
90C52 Methods of reduced gradient type

Citations:

Zbl 1278.65094

Software:

CGOPT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goldstein, A. A., On steepest descent, SIAM J. Control, 3, 147-151 (1965) · Zbl 0221.65094
[2] Touati-Ahmed, D.; Storey, C., Efficient hybrid conjugate gradient techniques, J. Optim. Theory Appl, 64, 379-397 (1990) · Zbl 0666.90063
[3] Birgin, E. G.; Martinez, J. M., A spectral conjugate gradient method for unconstrained optimization, J. Appl. Maths. Optim, 43, 117-128 (2001) · Zbl 0990.90134
[4] Dolan, E.; More, J. J., Benchmarking optimization software with performance profile, Maths. Prog, 91, 201-213 (2002) · Zbl 1049.90004
[5] Polak, E.; Ribiere, G., Note sur la convergence de directions conjugees, Rev. Francaise Informat Recherche Operationelle, 3, 35-43 (1969) · Zbl 0174.48001
[6] Yuan, G.; Wei, Z., New line search methods for unconstrained optimization, J. Korean Stat. Soc., 38, 29-39 (2009) · Zbl 1293.65098
[7] Yuan, G.; Lu, S.; Wei, Z., A line search algorithm for unconstrained optimization, J. Soft. Eng. App, 3, 503-509 (2010)
[8] Yuan, G.; Lu, X.; Wei, Z., A conjugate gradient method with descent direction for unconstrained optimization, J. Comp. App. Maths., 233, 519-530 (2009) · Zbl 1179.65075
[9] Zoutendijk, G., Nonlinear programming computational methods, (Abadie, J., Integer and nonlinear programming (1970), North Holland: North Holland Amsterdam) · Zbl 0336.90057
[10] Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 21-42 (1992) · Zbl 0767.90082
[11] Sun, J.; Zhang, J., Global convergence of conjugate gradient methods without line search, Annals. Opr. Rch., 103, 161-173 (2001) · Zbl 1014.90071
[12] Hilstrom, K. E., A simulation test approach to the evaluation of nonlinear optimization algorithms, A.C.M. Trans. Maths. Softw, 3, 305-315 (1977)
[13] Armijo, L., Minimization of functions having Lipschitz continuous partial derivatives, Pacific J. Math., 16, 1-3 (1966) · Zbl 0202.46105
[14] Al-Baali, M., Descent property and global convergence of Fletcher-Reeves method with inexact line search, IMA. J. Numer. Anal., 5, 121-124 (1985) · Zbl 0578.65063
[15] Powell, M. J.D., Restart procedures for the conjugate gradient method, Math. Program, 12, 241-254 (1977) · Zbl 0396.90072
[16] Powell, M. J.D., Nonconvex minimization calculations and the conjugate gradient method in Lecture notes in mathematics, 1066, 122-141 (1984;), Springer-Verlag: Springer-Verlag Berlin · Zbl 0531.65035
[17] Powell, M. J.D., Convergence properties of algorithm for nonlinear optimization, SIAM Rev, 28, 487-500 (1986) · Zbl 0624.90091
[18] Rivaie, M.; Mustafa, M.; Ismail, M.; Fauzi, M., A comparative study of conjugate gradient coefficient for unconstrained optimization, Aus. J. Bas. Appl. Sc., 5, 947-951 (2011)
[19] Rivaie, M.; Mustafa, M.; June, L. W.; Mohd, I., A new class of nonlinear conjugate gradient coefficient with global convergence properties, Appl. Math. Comp., 218, 11323-11332 (2012) · Zbl 1278.65094
[20] Hestenes, M. R.; Steifel, E., Method of conjugate gradient for solving linear equations, J. Res. Nat. Bur. Stand, 49, 409-436 (1952) · Zbl 0048.09901
[21] Andrei, N., An unconstrained optimization test functions collection, Adv. Model. Optim, 10, 147-161 (2008) · Zbl 1161.90486
[22] Andrei, N., Open problems in nonlinear conjugate gradient algorithms for unconstrained optimization, Bull. Malays. Math. Sci. Soc. (2), 34, 2, 319-330 (2011) · Zbl 1225.49030
[23] Andrei, N., Accelerated conjugate gradient algorithm with finite difference Hessian/vector product approximation for unconstrained optimization, J. Comput. Appl. Math., 230, 570-582 (2009) · Zbl 1170.65046
[24] Andrei, N., 40 conjugate gradients algorithms for unconstrained optimization, Bull. Malays. Math. Sci. Soc., 34, 319-330 (2011) · Zbl 1225.49030
[25] Wolfe, P., Convergence conditions for ascent method, SIAM Rev, 11, 226-235 (1969) · Zbl 0177.20603
[26] Fletcher, R., Practical method of optimization, Unconstrained optimization, 1 (1987), John Wiley & Sons: John Wiley & Sons New York · Zbl 0905.65002
[27] Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701
[28] Hager, W. W.; Zhang, H. C., A new conjugate gradient method with guaranteed descent and efficient line search, SIAM J. Optim., 16, 170-192 (2005) · Zbl 1093.90085
[29] Dai, Y. H., Nonlinear conjugate gradient methods (2011), Wiley Encyclopedia of Operation Research: Wiley Encyclopedia of Operation Research New York
[30] Dai, Y. H.; Kou, C. X., A nonlinear conjugate gradient method with an optimal property and an improved Wolfe line search, SIAM J. Optim., 23, 1, 296-320 (2013) · Zbl 1266.49065
[31] Dai, Y. H.; Yuan, Y., Nonlinear Conjugate Gradient Method (1998), Shanghai Scientific and Technical Publishers: Shanghai Scientific and Technical Publishers Beijing · Zbl 0914.90219
[32] Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient with a strong global convergence property, SIAM J. Optim., 10, 177-182 (1999) · Zbl 0957.65061
[33] Dai, Y. H.; Yuan, Y., A note on the nonlinear conjugate gradient method, J. Comput. Appl. Math., 18, 6, 575-582 (2002) · Zbl 1014.65053
[34] Liu, Y.; Storey, C., Efficient generalized conjugate gradient algorithms part 1: Theory, J. Comput. Appl. Math., 69, 129-137 (1992) · Zbl 0702.90077
[35] Yuan, Y.; Sun, W., Theory and Methods of Optimization (1999), Science Press of China: Science Press of China Beijing
[36] Dai, Z. F., Two modified HS type conjugate gradient methods for unconstrained optimization problems, Nonlinear Anal., 74, 927-936 (2011) · Zbl 1203.49049
[37] Shi, Z. J.; Guo, J., A new family of conjugate gradient methods, J. Comput. Appl. Math., 224, 444-457 (2009) · Zbl 1155.65049
[38] Shi, Z. J.; Wang, S.; Xu, Z., The convergence of conjugate gradient method with nonmonotone line search, Appl. Math. Comp., 217, 1921-1932 (2010) · Zbl 1206.65166
[39] Wei, Z.; Li, G.; Qi, L., New nonlinear conjugate gradient method formulas for large- scaled unconstrained optimizations problems, Appl. Math. Comp., 179, 407-430 (2006) · Zbl 1106.65055
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.