NEW HYBRID CONJUGATE GRADIENT METHOD AS A CONVEX COMBINATION OF LS AND FR METHODS

doi:10.1007/s10473-019-0117-6

Abstract

Abstract: In this paper, we present a new hybrid conjugate gradient algorithm for unconstrained optimization. This method is a convex combination of Liu-Storey conjugate gradient method and Fletcher-Reeves conjugate gradient method. We also prove that the search direction of any hybrid conjugate gradient method, which is a convex combination of two conjugate gradient methods, satisfies the famous D-L conjugacy condition and in the same time accords with the Newton direction with the suitable condition. Furthermore, this property doesn’t depend on any line search. Next, we also prove that, moduling the value of the parameter t, the Newton direction condition is equivalent to Dai-Liao conjugacy condition.The strong Wolfe line search conditions are used.
The global convergence of this new method is proved.
Numerical comparisons show that the present hybrid conjugate gradient algorithm is the efficient one.

Key words: hybrid conjugate gradient method, convex combination, Dai-Liao conjugacy condition, Newton direction

Snezana S. DJORDJEVIC, . NEW HYBRID CONJUGATE GRADIENT METHOD AS A CONVEX COMBINATION OF LS AND FR METHODS[J].Acta mathematica scientia,Series B, 2019, 39(1): 214-228.

Trendmd

References

[1] Al-Baali M. Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMA J Numer Anal, 1985, 5:121-124
[2] Andrei N. New hybrid conjugate gradient algorithms for unconstrained optimization. Encyclopedia of Optimization, 2009:2560-2571
[3] Andrei N. A hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization as a convex combination of Hestenes-Stiefel and Dai-Yuan algorithms. Studies in Informatics and Control, 2008, 17(4):373-392
[4] Andrei N. A hybrid conjugate gradient algorithm for unconstrained optimization as a convex combination of Hestenes-Stiefel and Dai-Yuan. Studies in Informatics and Control, 2008, 17(1):55-70
[5] Andrei N. Another hybrid conjugate gradient algorithm for unconstrained optimization. Numerical Algorithms, 2008, 47(2):143-156
[6] Andrei N. An unconstrained optimization test functions. Advanced Modeling and Optimization, An Electronic International Journal, 2008, 10:147-161
[7] Andrei N. Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization. Numer Algorithms, 2010, 54:23-46
[8] Dai Y H, Yuan Y. Convergence properties of the Fletcher-Reeves method. IMA J Numer Anal, 1996, 16: 155-164
[9] Dai Y H, Liao L Z. New conjugacy conditions and related nonlinear conjugate gradient methods. Appl Math Optim, 2001, 43:87-101
[10] Dai Y H, Yuan Y. A nonlinear conjugate gradient method with a strong global convergence property. SIAM J Optim, 1999, 10:177-182
[11] 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, 1999, 10:348-358
[12] Dai Y H. A family of hybrid conjugate gradient methods for unconstrained optimization. Math Comp, 2003, 72:1317-1328
[13] Dai Y H, Yuan Y. A class of globally convergent conjugate gradient methods. Sci China Ser A, 2003, 46: 251-262
[14] Dorđević S S. New hybrid conjugate gradient method as a convex combination of FR and PRP methods. Filomat, 2016, 30(11):3083-3100
[15] Dolan E D, Moré J J. Benchmarking optimization software with performance profiles. Math Programming, 2002, 91:201-213
[16] Fletcher R. Practical Methods of Optimization Vol. 1:Unconstrained Optimization. New York:John Wiley and Sons, 1987
[17] Fletcher R, Reeves C. Function minimization by conjugate gradients. Comput J, 1964, 7:149-154
[18] Gilbert J C, Nocedal J. Global convergence properties of conjugate gradient methods for optimization. SIAM J Optim, 1992, 2:21-42
[19] Hager W W, Zhang H. A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J Optim, 2003, 16(1):170-192
[20] Hager W W, Zhang H. CG-DESCENT, a conjugate gradient method with guaranteed descent. ACM Transactions on Mathematical Software, 2006, 32(1):113-137
[21] Hager W W, Zhang H. A survey of nonlinear conjugate gradient methods. Pacific J Optim, 2006, 2:35-58
[22] Hestenes M R, Stiefel E L. Methods of conjugate gradients for solving linear systems. J Research Nat Bur Standards, 1952, 49:409-436
[23] Hu Y F, Storey C. Global convergence result for conjugate gradient methods. J Optim Theory Appl, 1991, 71:399-405
[24] Liu J K, Li S J. New hybrid conjugate gradient method for unconstrained optimization. Appl Math Comput, 2014, 245:36-43
[25] Liu Y, Storey C. Efficient generalized conjugate gradient algorithms, part 1:theory. JOTA, 1991, 69: 129-137
[26] 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, 1995, 10:75-82
[27] Polak E, Ribiére G. Note sur la convergence de méthodes de directions conjugués. Revue Française d'Informatique et de Recherche Opérationnelle, 1969, 16:35-43
[28] Polyak B T. The conjugate gradient method in extreme problems. USSR Comp Math Math Phys, 1969, 9: 94-112
[29] Powell M J D. Restart procedures of the conjugate gradient method. Math Program, 1977, 2:241-254
[30] Touati-Ahmed D, Storey C. Efficient hybrid conjugate gradient techniques. J Optim Theory Appl, 1990, 64:379-397
[31] Wolfe P. Convergence conditions for ascent methods. SIAM Review, 1969, 11:226-235
[32] Wolfe P. Convergence conditions for ascent methods. II:Some corrections. SIAM Review, 1969, 11:226-235
[33] Yang X, Luo Z, Dai X. A global convergence of LS-CD hybrid conjugate gradient method. Adv Numer Anal, 2013, 2013:Article ID 517452, 5 pages
[34] Yuan Y, Stoer J. A subspace study on conjugate gradient algorithm. Z Angew Math Mech, 1995, 75:69-77
[35] Yuan G, Meng Z, Li Y. A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations. J Optim Theory Appl, 2016, 168:129-152
[36] Yuan G, Wei Z, Li G. A modified Polak-Ribière-Polyak conjugate gradient algorithm for nonsmooth convex programs. J Comput Appl Math, 2014, 255:86-96
[37] Yuan G, Wei Z, Lu X. Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search. Appl Math Model, 2017, 47:811-825
[38] Yuan G, Wei Z, Zhao Q. A modified Polak-Ribiére-Polyak conjugate gradient algorithm for large-scale optimization problems. IIE Transactions, 2014, 46:397-413
[39] Yuan G, Zhang M. A three-terms Polak-Ribiére-Polyak conjugate gradient algorithm for large-scale nonlinear equations. J Comput Appl Math, 2015, 286:186-195
[40] Zoutendijk G. Nonlinear programming, computational methods//Abadie J, ed. Integer and Nonlinear Programming. Amsterdam:North-Holland, 1970:37-86