Two modified scaled nonlinear conjugate gradient methods. (English) Zbl 1278.65086
Summary: Following the scaled conjugate gradient methods proposed by Andrei, we hybridize the memoryless BFGS preconditioned conjugate gradient method suggested by D. F. Shanno [Math. Oper. Res. 3, 244–256 (1978; Zbl 0399.90077)] and the spectral conjugate gradient method suggested by E. G. Birgin and J. M. Martínez [Appl. Math. Optimization 43, No. 2, 117–128 (2001; Zbl 0990.90134)] based on a modified secant equation suggested by Yuan, and propose two modified scaled conjugate gradient methods. The interesting features of our methods are applying the function values in addition to the gradient values and satisfying the sufficient descent condition for the generated search directions which leads to the global convergence for uniformly convex functions. Numerical comparisons between the implementations of one of our methods which generates descent search directions for general functions and an efficient scaled conjugate gradient method proposed by Andrei are made on a set of unconstrained optimization test problems from the CUTEr collection, using the performance profile introduced by E. D. Dolan and J. J. Moré [Math. Program. 91, No. 2 (A), 201–213 (2002; Zbl 1049.90004)].
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C53 | Methods of quasi-Newton type |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
unconstrained optimization; scaled nonlinear conjugate gradient method; BFGS update; modified secant equation; sufficient descent condition; global convergence; CUTErReferences:
| [1] | Dai, Y. H.; Han, J. Y.; Liu, G. H.; Sun, D. F.; Yin, H. X.; Yuan, Y. X., Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim., 10, 2, 348-358 (1999) · Zbl 0957.65062 |
| [2] | Han, J. Y.; Liu, G. H.; Sun, D. F.; Yin, H. X., Two fundamental convergence theorems for nonlinear conjugate gradient methods and their applications, Acta Math. Appl. Sin., 17, 2, 38-46 (2001) · Zbl 0973.65048 |
| [3] | Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer: Springer New York · Zbl 1104.65059 |
| [4] | Sun, W.; Yuan, Y. X., Optimization Theory and Methods: Nonlinear Programming (2006), Springer: Springer New York · Zbl 1129.90002 |
| [5] | Wolfe, P., Convergence conditions for ascent methods, SIAM Rev., 11, 2, 226-235 (1969) · Zbl 0177.20603 |
| [6] | Wolfe, P., Convergence conditions for ascent methods, II. Some corrections, SIAM Rev., 13, 2, 185-188 (1971) · Zbl 0216.26901 |
| [7] | Hager, W. W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 1, 35-58 (2006) · Zbl 1117.90048 |
| [8] | Andrei, N., Numerical comparison of conjugate gradient algorithms for unconstrained optimization, Stud. Inform. Control, 16, 4, 333-352 (2007) |
| [9] | Dai, Y. H.; Ni, Q., Testing different conjugate gradient methods for large-scale unconstrained optimization, J. Comput. Math., 22, 3, 311-320 (2003) · Zbl 1041.65048 |
| [10] | Powell, M. J.D., Nonconvex minimization calculations and the conjugate gradient method, (Griffiths, D. F., Numerical Analysis (Dundee, 1983). Numerical Analysis (Dundee, 1983), Lecture Notes in Math., vol. 1066 (1984), Springer: Springer Berlin), 122-141 · Zbl 0531.65035 |
| [11] | Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 6, 409-436 (1952) · Zbl 0048.09901 |
| [12] | Babaie-Kafaki, S.; Ghanbari, R.; Mahdavi-Amiri, N., Two new conjugate gradient methods based on modified secant equations, J. Comput. Appl. Math., 234, 5, 1374-1386 (2010) · Zbl 1202.65071 |
| [13] | Perry, A., A modified conjugate gradient algorithm, Oper. Res., 26, 6, 1073-1078 (1976) · Zbl 0419.90074 |
| [14] | Shanno, D. F., Conjugate gradient methods with inexact searches, Math. Oper. Res., 3, 3, 244-256 (1978) · Zbl 0399.90077 |
| [15] | Broyden, C. G., The convergence of a class of double-rank minimization algorithms. II. The new algorithm, J. Inst. Math. Appl., 6, 3, 222-231 (1970) · Zbl 0207.17401 |
| [16] | Fletcher, R., A new approach to variable metric algorithms, Comput. J., 13, 3, 317-322 (1970) · Zbl 0207.17402 |
| [17] | Goldfarb, D., A family of variable metric methods derived by variational means, Math. Comp., 24, 109, 23-26 (1970) · Zbl 0196.18002 |
| [18] | Shanno, D. F., Conditioning of quasi-Newton methods for function minimization, Math. Comp., 24, 1, 647-656 (1970) · Zbl 0225.65073 |
| [19] | Nazareth, J. L., A relationship between the BFGS and conjugate gradient algorithms and its implications for the new algorithms, SIAM J. Numer. Anal., 16, 5, 794-800 (1979) · Zbl 0424.65030 |
| [20] | Buckley, A. G., Extending the relationship between the conjugate gradient and BFGS algorithms, Math. Program., 15, 1, 343-348 (1978) · Zbl 0393.90075 |
| [21] | Birgin, E.; Martínez, J. M., A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 2, 117-128 (2001) · Zbl 0990.90134 |
| [22] | Barzilai, J.; Borwein, J. M., Two-point stepsize gradient methods, IMA J. Numer. Anal., 8, 1, 141-148 (1988) · Zbl 0638.65055 |
| [23] | Oren, S. S.; Spedicato, E., Optimal conditioning of self-scaling variable metric algorithms, Math. Program., 10, 1, 70-90 (1976) · Zbl 0342.90045 |
| [24] | Andrei, N., A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Appl. Math. Lett., 20, 6, 645-650 (2007) · Zbl 1116.90114 |
| [25] | Andrei, N., Scaled conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl., 38, 3, 401-416 (2007) · Zbl 1168.90608 |
| [26] | Andrei, N., Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Optim. Methods Softw., 22, 4, 561-571 (2007) · Zbl 1270.90068 |
| [27] | Andrei, N., A scaled nonlinear conjugate gradient algorithm for unconstrained optimization, Optimization, 57, 4, 549-570 (2008) · Zbl 1338.90457 |
| [28] | Andrei, N., Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, European J. Oper. Res., 204, 3, 410-420 (2010) · Zbl 1189.90151 |
| [29] | Polak, E.; Ribière, G., Note sur la convergence de méthodes de directions conjuguées, Rev. Fr. Inform. Rech. Oper., 3, 16, 35-43 (1969) · Zbl 0174.48001 |
| [30] | Polyak, B. T., The conjugate gradient method in extreme problems, USSR Comput. Math. Math. Phys., 9, 4, 94-112 (1969) · Zbl 0229.49023 |
| [31] | Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 2, 149-154 (1964) · Zbl 0132.11701 |
| [32] | Raydan, M., The Barzilai and Borwein gradient method for the large-scale unconstrained minimization problem, SIAM J. Optim., 7, 1, 26-33 (1997) · Zbl 0898.90119 |
| [33] | Shanno, D. F.; Phua, K. H., Algorithm 500: minimization of unconstrained multivariate functions, ACM Trans. Math. Software, 2, 1, 87-94 (1976) · Zbl 0319.65042 |
| [34] | Babaie-Kafaki, S., A note on the global convergence theorem of the scaled conjugate gradient algorithms proposed by Andrei, Comput. Optim. Appl., 52, 2, 409-414 (2012) · Zbl 1269.90105 |
| [35] | Shanno, D. F.; Phua, K. H., Matrix conditioning and nonlinear optimization, Math. Program., 14, 2, 149-160 (1978) · Zbl 0371.90109 |
| [36] | Hager, W. W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 1, 170-192 (2005) · Zbl 1093.90085 |
| [37] | Hager, W. W.; Zhang, H., Algorithm 851: CG_Descent, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Software, 32, 1, 113-137 (2006) · Zbl 1346.90816 |
| [38] | Yuan, Y. X.; Byrd, R. H., Non-quasi-Newton updates for unconstrained optimization, J. Comput. Math., 13, 2, 95-107 (1995) · Zbl 0823.65062 |
| [39] | Yuan, Y. X., A modified BFGS algorithm for unconstrained optimization, IMA J. Numer. Anal., 11, 3, 325-332 (1991) · Zbl 0733.65039 |
| [40] | Wei, Z.; Li, G.; Qi, L., New quasi-Newton methods for unconstrained optimization problems, Appl. Math. Comput., 175, 2, 1156-1188 (2006) · Zbl 1100.65054 |
| [41] | Wei, Z.; Yu, G.; Yuan, G.; Lian, Z., The superlinear convergence of a modified BFGS-type method for unconstrained optimization, Comput. Optim. Appl., 29, 3, 315-332 (2004) · Zbl 1070.90089 |
| [42] | Li, G.; Tang, C.; Wei, Z., New conjugacy condition and related new conjugate gradient methods for unconstrained optimization, J. Comput. Appl. Math., 202, 2, 523-539 (2007) · Zbl 1116.65069 |
| [43] | Babaie-Kafaki, S., A modified BFGS algorithm based on a hybrid secant equation, Sci. China Math., 54, 9, 2019-2036 (2011) · Zbl 1401.90268 |
| [44] | Andrei, N., Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization, Numer. Algorithms, 54, 1, 23-46 (2010) · Zbl 1192.65074 |
| [45] | Babaie-Kafaki, S.; Fatemi, M.; Mahdavi-Amiri, N., Two effective hybrid conjugate gradient algorithms based on modified BFGS updates, Numer. Algorithms, 58, 3, 315-331 (2011) · Zbl 1277.90149 |
| [46] | Dai, Y. H.; Yuan, J.; Yuan, Y. X., Modified two-point stepsize gradient methods for unconstrained optimization, Comput. Optim. Appl., 22, 1, 103-109 (2002) · Zbl 1008.90056 |
| [47] | Gould, N. I.M.; Orban, D.; Toint, P. L., CUTEr: a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software, 29, 4, 373-394 (2003) · Zbl 1068.90526 |
| [48] | Dai, Y. H.; Liao, L. Z.; Li, D., On restart procedures for the conjugate gradient method, Numer. Algorithms, 35, 2-4, 249-260 (2004) · Zbl 1137.90669 |
| [49] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program. Ser. A, 91, 2, 201-213 (2002) · Zbl 1049.90004 |
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.
