×

Two new conjugate gradient methods based on modified secant equations. (English) Zbl 1202.65071

Two new nonlinear conjugate gradient methods for the solution of unconstrained optimization problems are presented and evaluated. They are based on the guidelines of Dai and Liao and take into account both the gradient and function values. A modified version of the secant equation proposed by Zhang, Deng and Chen, and Zhang and Xu, characterizes the first method. The second method is based on the modified BFGS update proposed by Yuan. It is shown that one of the proposed methods is globally convergent for general functions and the other is globally convergent for uniformly convex functions, under proper conditions. For the enhancement of the performance of the line search procedure, a new approach for the computation of the initial steplength for initiating the procedure is obtained. A comparison of the proposed methods with the efficient conjugate gradient methods proposed by Dai and Liao and Hestenes and Stiefel is implemented and the numerical results demonstrate the efficiency of the two methods.

MSC:

65K05 Numerical mathematical programming methods

Software:

SCALCG; minpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer: Springer New York · Zbl 0930.65067
[2] Sun, W.; Yuan, Y. X., Optimization Theory and Methods: Nonlinear Programming (2006), Springer
[3] Fletcher, R.; Revees, C. M., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701
[4] Polak, E.; Ribière, G., Note sur la convergence de méthodes directions conjugées, Rev. Francaise êInform. Rech. Opér., 16, 35-43 (1969) · Zbl 0174.48001
[5] Polyak, B. T., The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys., 9, 94-112 (1969) · Zbl 0229.49023
[6] Hestenes, M. R.; Stiefel, E. L., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49, 5, 409-436 (1952) · Zbl 0048.09901
[7] Liu, Y.; Storey, C., Efficient generalized conjugate gradient algorithms, part 1: Theory, J. Optim. Theory Appl., 69, 129-137 (1991) · Zbl 0702.90077
[8] Dai, Y. H.; Yuan, Y. X., A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10, 177-182 (1999) · Zbl 0957.65061
[9] Al-Baali, A., Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA J. Numer. Anal., 5, 121-124 (1985) · Zbl 0578.65063
[10] 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)
[11] Dai, Y. H.; Yuan, Y. X., Convergence properties of the Fletcher-Reeves method, IMA J. Numer. Anal., 16, 2, 155-164 (1996) · Zbl 0851.65049
[12] Grippo, L.; Lucidi, S., A globally convergent version of the Polak-Ribière conjugate gradient method, Math. Program., 78, 375-391 (1997) · Zbl 0887.90157
[13] Liu, G. H.; Han, J. Y.; Yin, H. X., Global convergence of the Fletcher-Reeves algorithm with an inexact line search, Appl. Math. J. Chinese Univ. Ser. B, 10, 75-82 (1995) · Zbl 0834.90122
[14] Powell, M. J.D., Nonconvex minimization calculations and the conjugate gradient method, (Lecture Notes in Mathematics, vol. 1066 (1984), Springer: Springer Berlin), 122-141 · Zbl 0531.65035
[15] Shi, Z. J.; Shen, J., Convergence of the Polak-Ribière-Polyak conjugate gradient method, Nonlinear Anal., 66, 1428-1441 (2007) · Zbl 1120.49027
[16] Zoutendijk, G., Nonlinear programming computational methods, (Abadie, J., Integer and Nonlinear Programming (1970), North-Holland: North-Holland Amsterdam), 37-86 · Zbl 0336.90057
[17] Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 1, 21-42 (1992) · Zbl 0767.90082
[18] Nazareth, J. L., A view of conjugate gradient-related algorithms for nonlinear optimization, (Adams, L.; Nazareth, J. L., Linear and Nonlinear Conjugate Gradient-Related Methods (1996), SIAM: SIAM Philadelphia), 149-163 · Zbl 0866.65038
[19] Andrei, N., A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Appl. Math. Lett., 20, 645-650 (2007) · Zbl 1116.90114
[20] 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
[21] Dai, Y. H.; Yuan, Y. X., An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. Oper. Res., 103, 33-47 (2001) · Zbl 1007.90065
[22] Ford, J. A.; Narushima, Y.; Yabe, H., Multi-step nonlinear conjugate gradient methods for unconstrained minimization, Comput. Optim. Appl., 40, 191-216 (2008) · Zbl 1181.90221
[23] 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
[24] Perry, A., A modified conjugate gradient algorithm, Oper. Res., 26, 6, 1073-1078 (1976) · Zbl 0419.90074
[25] Powell, M. J.D., Updating conjugate directions by the BFGS formula, Math. Program., 38, 29-46 (1987) · Zbl 0642.90086
[26] Shanno, D. F., Conjugate gradient methods with inexact searches, Math. Oper. Res., 3, 3, 244-256 (1978) · Zbl 0399.90077
[27] Yabe, H.; Takano, M., Global convergence properties of nonlinear conjugate gradient methods with modified secant condition, Comput. Optim. Appl., 28, 203-225 (2004) · Zbl 1056.90130
[28] Zhou, W.; Zhang, L., A nonlinear conjugate gradient method based on the MBFGS secant condition, Optim. Methods Softw., 21, 5, 707-714 (2006) · Zbl 1112.90096
[29] Huang, H. Y., Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl., 5, 405-423 (1970) · Zbl 0184.20202
[30] Ford, J. A.; Moghrabi, I. A., Multi-step quasi-Newton methods for optimization, J. Comput. Appl. Math., 50, 305-323 (1994) · Zbl 0807.65062
[31] Ford, J. A.; Moghrabi, I. A., Using function-values multi-step quasi-Newton methods, J. Comput. Appl. Math., 66, 201-211 (1996) · Zbl 0856.65073
[32] Li, D. H.; Fukushima, M., A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129, 15-35 (2001) · Zbl 0984.65055
[33] Zhang, J. Z.; Deng, N. Y.; Chen, L. H., New quasi-Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl., 102, 147-167 (1999) · Zbl 0991.90135
[34] Zhang, J. Z.; Xu, C. X., Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equation, J. Comput. Appl. Math., 137, 269-278 (2001) · Zbl 1001.65065
[35] Yabe, H.; Ogasawara, H.; Yoshino, M., Local and super linear convergence of quasi-Newton methods based on modified secant conditions, J. Comput. Appl. Math., 205, 1, 617-632 (2007) · Zbl 1124.65054
[36] 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
[37] Yuan, Y. X., A modified BFGS algorithm for unconstrained optimization, IMA J. Numer. Anal., 11, 325-332 (1991) · Zbl 0733.65039
[38] Andrei, N., An unconstrained optimization test functions collection, Adv. Model. Optim., 10, 1, 147-161 (2008) · Zbl 1161.90486
[39] Dai, Y. H.; Yuan, Y. J.; Yuan, Y. X., Modified two-point stepsize gradient methods for unconstrained optimization, Comput. Optim. Appl., 22, 1, 103-109 (2002) · Zbl 1008.90056
[40] Morè, J. J.; Garbow, B. S.; Hillstrome, K. E., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 17-41 (1981) · Zbl 0454.65049
[41] Powell, M. J.D., Restart procedures for the conjugate gradient method, Math. Program., 12, 241-245 (1977) · Zbl 0396.90072
[42] Birgin, E. G.; Martínez, J. M., A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 117-128 (2001) · Zbl 0990.90134
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.