A class of conjugate gradient algorithm with sufficient descent property
-
摘要: 在一些著名的共轭梯度算法基础之上,提出一类新的共轭梯度算法,用于求解无约束优化问题.该方法在不依赖于任何线搜索的情况下能够保证充分下降性,且在Wolfe线搜索下证明了算法具有全局收敛性.数值结果表明新提出的算法是有效的.Abstract: On the basis of some famous conjugate gradient algorithms, a class of new nonlinear conjugate gradient algorithm is proposed for solving unconstrained optimization problems, which can generate sufficient descent directions at each iteration regardless of any line search. Under the Wolfe line searches, the global convergence of the proposed algorithm is proved. Numerical experiment results show that the proposed method is promising.
-
3-1 数值实验结果
3-1 Test results of the DPRP method, HCG method and XW method
Problem/Dim DPRP
Iter/CPU/NGHCG
Iter/CPU/NGXW
Iter/CPU/NGExtended Himmelblau 4 18/27.7395/4.4017e-007 39/54.8418/6.9045e-007 18/27.7933/1.5703e-007 Sine 2 11/3.5638/3.9185e-007 8/2.5639/1.8520e-007 7/2.3352/1.2779e-007 Cosine 10 51/141.8444/5.7644e-007 -/-/- 24/56.392/2.4799e-007 Diagonal2 10 28/29.1365/7.9397e-007 24/25.278/2.6109e-007 23/23.9026/9.7986e-007 Extended Tridiagonal1 10 5/113.2767/3.30369e-007 2/48.2954/0 2/4.5546/0 Extended Tridiagonal1 100 5/101.4521/3.0369e-007 2/43.6037/0 2/43.5109 /0 Hager 10 27/48.065/7.8171e-007 25/43.0894/7.6331e-007 22/38.9669/8.6375e-007 Diagonal7 50 36/221.4287/4.0673e-007 36/215.9832/4.0673e-007 11/64.5762/8.3333e-008 Diagonal7 100 35/143.776/8.4795e-007 35/480.9685/8.4795e-007 9/128.4588/2.3888e-007 Diagonal7 200 34/1496/4.6344e-007 35/1575/4.6344e-007 9/415.2523/3.3782e-007 Generalized Tridiagonal1 3 42/39.009/9.2207e-007 41/38.3766/7.2432e-007 18/16.4119/4.9465e-007 Power 2 19/5.654/4.7577e-007 4/1.3975/0 7/2.2804/1.0401e-007 Extended Penalty 20 19/296.1026/2.2950e-007 28/416.5727/5.8271e-007 22/343.7406/6.6437e-007 Generalized white and holst 2 -/-/- 518/653.1484/9.5548e-007 761/901.6873/6.6998e-007 Raydan2 100 6/44.9154/3.9990e-012 6/45.0149/4.0001e-012 4/30.5587/4.2707e-008 Raydan2 200 6/146.4836/5.6570e-012 6/147.9547/5.6570e-012 4/98.8073/6.0397e-008 Raydan2 1000 5/4383.6971/2.8284e-005 4/3613.2339/0.0423 4/3498.1344/1.3505e-007 -
[1] HESTENES M R, STIEFEL E L. Methods of conjugate gradients for solving linear systems[J]. Journal of Research of the National Bureau of Standards, 1952, 49(6):409-436. doi: 10.6028/jres.049.044 [2] FLETCHER R, REEVES C M. Function minimization by conjugate gradients[J]. Computer Journal, 1964, 7(2):149-154. doi: 10.1093/comjnl/7.2.149 [3] POLYAK B T. The conjugate gradient method in extremal problems[J]. USSR Computational Mathematics and Mathematical Physics, 1969, 9(4):94-112. doi: 10.1016/0041-5553(69)90035-4 [4] POLAK E, RIBIÊRE G. Note sur la convergence de methodes de directions conjuguées[J]. Rev Franaise de Informat Recherche Opérationnelle, 1969, 16(1):35-43. [5] FLETCHER R. Practical Methods of Optimization, Vol Ⅰ:Unconstrained Optimization[M]. New York:Wiley and Sons, 1987. [6] LIU Y, STOREY C. Efficient generalized conjugate gradient algorithms, part 1:Theory[J]. Journal of Optimization Theory and Applications, 1991, 69(1):129-137. doi: 10.1007/BF00940464 [7] DAI Y H, YUAN Y. A nonlinear conjugate gradient method with a strong global convergence property[J]. Siam Journal on Optimization, 1999, 10(1):177-182. doi: 10.1137/S1052623497318992 [8] ZOUTENDIJK G. Nonlinear programming, computational methods[M]//Integer and Nonlinear Programming. Amsterdam:North-Holland Publishing Company, 1970. [9] AL-BAALI M. Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J]. IMA Journal of Numerical Analysis. 2010, 5(1):121-124. https://www.researchgate.net/profile/Mehiddin_Al-Baali/publication/264556443_On_the_Fletcher-Reeves_Method/links/53f446c20cf256ab87b7a802/On-the-Fletcher-Reeves-Method.pdf [10] GILBERT J C, NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992, 2(1):21-42. doi: 10.1137/0802003 [11] WEI Z, YAO S, LIU L. The convergence properties of some new conjugate gradient methods[J]. Applied Mathematics and Computation, 2006, 183(2):1341-1350. doi: 10.1016/j.amc.2006.05.150 [12] HUANG H, WEI Z, YAO S. The proof of the sufficient descent condition of the Wei-Yao-Liu conjugate gradient method under the strong Wolfe-Powell line search[J]. Applied Mathematics and Computation, 2007, 189(2): 1241-1245. doi: 10.1016/j.amc.2006.12.006 [13] TOUATI-AHMED D, STOREY C. Efficient hybrid conjugate gradient techniques[J]. Journal of Optimization Theory and Applications, 1990, 64(2):379-397. doi: 10.1007/BF00939455 [14] 莫降涛, 顾能柱, 韦增欣.修正, PRP, 共轭梯度法的全局收敛性及其数值结果[J].数值计算与计算机应用, 2007, 28(1):56-62. http://www.cnki.com.cn/Article/CJFDTOTAL-SZJS200701007.htm [15] DAI Z, WEN F. Another improved WeiõYaoõLiu nonlinear conjugate gradient method with sufficient descent property[J]. Applied Mathematics and Computation, 2012, 218(14):7421-7430. doi: 10.1016/j.amc.2011.12.091 [16] 戴彧虹.非线性共轭梯度法[M].上海:上海科学技术出版社, 2000. [17] ANDREI N. An unconstrained optimization test functions collection[J]. Adv Model Optim, 2008, 10(1):147-161.