×

Accelerated adaptive Perry conjugate gradient algorithms based on the self-scaling memoryless BFGS update. (English) Zbl 1365.65158

Summary: An accelerated adaptive class of nonlinear conjugate gradient algorithms is suggested. The search direction in these algorithms is given by symmetrization of the scaled A. Perry conjugate gradient direction [Oper. Res. 26, 1073–1078 (1978; Zbl 0419.90074)], which depends on a positive parameter. The value of this parameter is determined by minimizing the distance between the symmetrical scaled Perry conjugate gradient search direction matrix and the self-scaling memoryless BFGS update by Oren in the Frobenius norm. Two variants of the parameter in the search direction are presented as those given by S. S. Oren and D. G. Luenberger [Manage. Sci., Theory 20, 845–862 (1974; Zbl 0316.90064); S. S. Oren and E. Spedicato, Math. Program. 10, 70–90 (1976; Zbl 0342.90045)]. The corresponding algorithm, ACGSSV, is equipped with a very well known acceleration scheme of conjugate gradient algorithms. The global convergence of the algorithm is given both for uniformly convex and general nonlinear functions under the exact or the Wolfe line search. Using a set of 800 unconstrained optimization test problems, of different structure and complexity, we prove that selection of the scaling parameter in self-scaling memoryless BFGS update leads to algorithms which substantially outperform the CG-DESCENT, SCALCG, and CONMIN conjugate gradient algorithms, being more efficient and more robust. However, the conjugate gradient algorithm ADCG based on clustering the eigenvalues of the iteration matrix defined by the search direction is more efficient and slightly more robust than our ACGSSV algorithm. By solving five applications from the MINPACK-2 test problem collection with \(10^6\) variables, we show that the adaptive Perry conjugate gradient algorithms based on the self-scaling memoryless BFGS update, endowed with the acceleration scheme, is top performer versus CG_DESCENT.

MSC:

65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Andrei, N., Criticism of the unconstrained optimization algorithms reasoning, (2009), Editura Academiei Române Bucureşti
[2] Wolfe, P., Convergence conditions for ascent methods, SIAM Rev., 11, 226-235, (1969) · Zbl 0177.20603
[3] Wolfe, P., Convergence conditions for ascent methods. II: some corrections, SIAM Rev., 13, 185-188, (1971) · Zbl 0216.26901
[4] Hager, W. W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 35-58, (2006) · Zbl 1117.90048
[5] Perry, A., A modified conjugate gradient algorithm, Oper. Res., 26, 1073-1078, (1978) · Zbl 0419.90074
[6] 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
[7] 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
[8] Sherali, H. D.; Ulular, O., Conjugate gradient methods using quasi-Newton updates with inexact line search, J. Math. Anal. Appl., 150, 359-377, (1990) · Zbl 0711.65046
[9] Shanno, D. F., Conjugate gradient methods with inexact searches, Math. Oper. Res., 3, 244-256, (1978) · Zbl 0399.90077
[10] Andrei, N., Scaled conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl., 38, 401-416, (2007) · Zbl 1168.90608
[11] Shanno, D. F., Globally convergent conjugate gradient algorithms, Math. Program., 33, 61-67, (1985) · Zbl 0579.90079
[12] Shanno, D. F., On the convergence of a new conjugate gradient algorithm, SIAM J. Numer. Anal., 15, 1247-1257, (1978) · Zbl 0408.90071
[13] Powell, M. J.D., (Nonconvex Minimization Calculations and the Conjugate Gradient Method, Lecture Notes in Mathematics, vol. 1066, (1984), Springer-Verlag Berlin), 122-141 · Zbl 0531.65035
[14] Babaie-Kafaki, S., A note on the global convergence theorem of the scaled conjugate gradient algorithms proposed by andrei, Comput. Optim. Appl., 52, 409-414, (2012) · Zbl 1269.90105
[15] Yu, G. H., Nonlinear self-scaling conjugate gradient methods for large-scale optimization problems, (2007), Sun Yat-Sen University, (Ph.D. thesis)
[16] Yu, G. H.; Guan, L.; Chen, W., Spectral conjugate gradient methods with sufficient descent property for large-scale unconstrained optimization, Optim. Methods Softw., 23, 2, 275-293, (2008) · Zbl 1279.90166
[17] Oren, S. S., Self-scaling variable metric (SSVM) algorithms. II. implementation and experiments, Manage. Sci., 20, 863-874, (1974) · Zbl 0316.90065
[18] Oren, S. S.; Luenberger, D. G., Self-scaling variable metric (SSVM) algorithms. I. criteria and sufficient conditions for scaling a class of algorithms, Manage. Sci., 20, 845-862, (1973/74) · Zbl 0316.90064
[19] Oren, S. S.; Spedicato, E., Optimal conditioning of self-scaling variable metric algorithms, Math. Program., 10, 70-90, (1976) · Zbl 0342.90045
[20] 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
[21] Shanno, D. F.; Phua, K. H., Algorithm 500, minimization of unconstrained multivariate functions, ACM Trans. Math. Software, 2, 87-94, (1976) · Zbl 0319.65042
[22] Andrei, N., An adaptive conjugate gradient algorithm for large-scale unconstrained optimization, J. Comput. Appl. Math., 292, 83-91, (2016) · Zbl 1321.90124
[23] Nocedal, J.; Wright, S. J., (Numerical Optimization, Springer Series in Optimizations Research, (2006), Springer Science+Business Media New York)
[24] Meyer, C. D., Matrix analysis and applied linear algebra, (2000), SIAM Philadelphia
[25] Nocedal, J., Conjugate gradient methods and nonlinear optimization, (Adams, L.; Nazareth, J. L., Linear and Nonlinear Conjugate Gradient Related Methods, (1996), SIAM), 9-23 · Zbl 0866.65037
[26] Andrei, N., Acceleration of conjugate gradient algorithms for unconstrained optimization, Appl. Math. Comput., 213, 361-369, (2009) · Zbl 1172.65027
[27] Powell, M. J.D., Restart procedures of the conjugate gradient method, Math. Program., 2, 241-254, (1977) · Zbl 0396.90072
[28] 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
[29] Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 21-42, (1992) · Zbl 0767.90082
[30] Dai, Y.; Han, J.; Liu, G.; Sun, D.; Yin, H.; Yuan, Y.-X., Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim., 10, 345-358, (1999) · Zbl 0957.65062
[31] Zoutendijk, G., Nonlinear programming, computational methods, (Abadie, J., Integer and Nonlinear Programming, (1970), North-Holland), 37-86 · Zbl 0336.90057
[32] Sun, W.; Yuan, Y. X., Optimization theory and methods. nonlinear programming, (2006), Springer Science +Business Media New York
[33] Andrei, N., An unconstrained optimization test functions collection, Adv. Model. Optim., 10, 147-161, (2008) · Zbl 1161.90486
[34] Gould, N. I.M.; Orban, D.; Toint, P. L., Cuter: A constrained and unconstrained testing environment, revised, ACM Trans. Math. Software, 29, 373-394, (2003) · Zbl 1068.90526
[35] Hager, W. W.; Zhang, H., Algorithm 851: CG-DESCENT, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Software, 32, 113-137, (2006) · Zbl 1346.90816
[36] Dolan, E.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[37] Andrei, N., Eigenvalues versus singular values study in conjugate gradient algorithms for large-scale unconstrained optimization, Optim. Methods Softw., 32, 534-551, (2017) · Zbl 1368.49057
[38] B.M. Averick, R.G. Carter, J.J. Moré, G.L. Xue, The MINPACK-2 test problem collection, Mathematics and Computer Science Division, Argonne National Laboratory, Preprint MCS-P153-0692, June 1992.
[39] Glowinski, R., Numerical methods for nonlinear variational problems, (1984), Springer-Verlag Berlin · Zbl 0575.65123
[40] Cimatti, G., On a problem of the theory of lubrication governed by a variational inequality, Appl. Math. Optim., 3, 227-242, (1977) · Zbl 0404.76036
[41] Goodman, J.; Kohn, R.; Reyna, L., Numerical study of a relaxed variational problem from optimal design, Comput. Methods Appl. Mech. Engrg., 57, 107-127, (1986) · Zbl 0591.73119
[42] R. Aris, The Mathematical Theory of Diffusion and Reaction in Permeable Catalysts, Oxford, 1975. · Zbl 0315.76051
[43] Bebernes, J.; Eberly, D., (Mathematical Problems from Combustion Theory, Applied Mathematical Sciences, vol. 83, (1989), Springer-Verlag) · Zbl 0692.35001
[44] Nitsche, J. C.C., Lectures on minimal surfaces, vol. 1, (1989), Cambridge University Press · Zbl 0202.20601
[45] Babaie-Kafaki, S., A modified scaling parameter for the memoryless BFGS updating formula, Numer. Algorithms, 72, 425-433, (2016) · Zbl 1342.90227
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.