×

New accelerated conjugate gradient algorithms as a modification of Dai-Yuan’s computational scheme for unconstrained optimization. (English) Zbl 1407.65060

Summary: New accelerated nonlinear conjugate gradient algorithms which are mainly modifications of Dai and Yuan’s for unconstrained optimization are proposed. Using the exact line search, the algorithm reduces to the Dai and Yuan conjugate gradient computational scheme. For inexact line search the algorithm satisfies the sufficient descent condition. Since the step lengths in conjugate gradient algorithms may differ from 1 by two orders of magnitude and tend to vary in a very unpredictable manner, the algorithms are equipped with an acceleration scheme able to improve the efficiency of the algorithms. Computational results for a set consisting of 750 unconstrained optimization test problems show that these new conjugate gradient algorithms substantially outperform the Dai-Yuan conjugate gradient algorithm and its hybrid variants, Hestenes-Stiefel, Polak-Ribière-Polyak, CONMIN conjugate gradient algorithms, limited quasi-Newton algorithm LBFGS and compare favorably with CG_DESCENT. In the frame of this numerical study the accelerated scaled memoryless BFGS preconditioned conjugate gradient ASCALCG algorithm proved to be more robust.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C52 Methods of reduced gradient type
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] N. Andrei, 40 conjugate gradient algorithms for unconstrained optimization. A survey on their definition, ICI Technical Report No. 13/08, March 14, 2008.
[2] Hager, W.W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pacific J. optim., 2, 35-58, (2006) · Zbl 1117.90048
[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
[4] Dai, Y.H.; Yuan, Y., An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. oper. res., 103, 33-47, (2001) · Zbl 1007.90065
[5] 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
[6] Polak, E.; Ribière, G., Note sur la convergence de méthodes de directions conjuguée, Rev. fr. autom. inform. rech. oper., 3e Année 16, 35-43, (1969) · Zbl 0174.48001
[7] Polyak, B.T., The conjugate gradient method in extreme problems, USSR comput. math. math. phys., 9, 94-112, (1969) · Zbl 0229.49023
[8] 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
[9] Shanno, D.F.; Phua, V., Algorithm 500, minimization of unconstrained multivariate functions, ACM trans. math. software, 2, 87-94, (1976) · Zbl 0319.65042
[10] Liu, D.C.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. program., 45, 503-528, (1989) · Zbl 0696.90048
[11] Bongartz, I.; Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., CUTE: constrained and unconstrained testing environments, ACM trans. math. software, 21, 123-160, (1995) · Zbl 0886.65058
[12] Andrei, N., An unconstrained optimization test functions collection, Adv. model. optim., 10, 147-161, (2008) · Zbl 1161.90486
[13] Dolan, E.D.; Moré, J.J., Benchmarking optimization software with performance profiles, Math. program., 91, 201-213, (2002) · Zbl 1049.90004
[14] Andrei, N., Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, European J. oper. res., 204, 410-420, (2010) · Zbl 1189.90151
[15] Wolfe, P., Convergence conditions for ascent methods, SIAM rev., 11, 226-235, (1969) · Zbl 0177.20603
[16] Wolfe, P., Convergence conditions for ascent methods II: some corrections, SIAM rev., 13, 185-188, (1971) · Zbl 0216.26901
[17] Dai, Y.H., New properties of a nonlinear conjugate gradient method, Numer. math., 89, 83-98, (2001) · Zbl 1006.65063
[18] 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
[19] Zoutendijk, G., Nonlinear programming computational methods, (), 37-86 · Zbl 0336.90057
[20] 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)
[21] Nocedal, J., Conjugate gradient methods and nonlinear optimization, (), 9-23 · Zbl 0866.65037
[22] Andrei, N., Performance profiles of conjugate gradient algorithms for unconstrained optimization, (), 2938-2953
[23] Andrei, N., Acceleration of conjugate gradient algorithms for unconstrained optimization, Appl. math. comput., 213, 361-369, (2009) · Zbl 1172.65027
[24] Powell, M.J.D., Restart procedures for the conjugate gradient method, Math. program., 12, 241-254, (1977) · Zbl 0396.90072
[25] Birgin, E.; Martínez, J.M., A spectral conjugate gradient method for unconstrained optimization, Appl. math. comput., 43, 117-128, (2001) · Zbl 0990.90134
[26] Dai, Y.H.; Ni, Q., Testing different conjugate gradient methods for large-scale unconstrained optimization, J. comput. math., 21, 311-320, (2003) · Zbl 1041.65048
[27] Oren, S.S.; Spedicato, E., Optimal conditioning of self-scaling variable metric algorithms, Math. program., 10, 70-90, (1976) · Zbl 0342.90045
[28] J.M. Perry, A class of conjugate gradient algorithms with a two step variable metric memory, Discussion Paper 269, Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1977.
[29] Shanno, D.F., Conjugate gradient methods with inexact searches, Math. oper. res., 3, 244-256, (1978) · Zbl 0399.90077
[30] Shanno, D.F., On the convergence of a new conjugate gradient algorithm, SIAM J. numer. anal., 15, 1247-1257, (1978) · Zbl 0408.90071
[31] Moré, J.J.; Thuente, D.J., Line search algorithms with guaranteed sufficient decrease, ACM trans. math. softw., 20, 286-307, (1994) · Zbl 0888.65072
[32] Hansen, P.C., Rank deficient and discrete ill-posed problems, (1998), SIAM Philadelphia
[33] Alekseev, A.K.; Navon, I.M.; Steward, J.L., Comparison of advanced large-scale minimization algorithms for the solution of inverse ill-posed problems, Optim. methods softw., 24, 1, 63-87, (2009) · Zbl 1189.90221
[34] N. Andrei, Another accelerated conjugate gradient algorithm with guaranteed descent and conjugacy conditions for large-scale unconstrained optimization, ICI Technical Report No. 7/2010, January 29, 2010.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.