Advances in Applied Mathematics
Vol.
08
No.
04
(
2019
), Article ID:
29859
,
8
pages
10.12677/AAM.2019.84076
A Modified Nonlinear Conjugate Gradient Algorithm Using Secant Conditions
Jing Liang*, Guodong Ma#, Yuting Shi, Zhimei Lin, Wenting Zou, Liuna Li
School of Mathematics and Statistics, Yulin Normal University, Yulin Guangxi
Received: Apr. 2nd, 2019; accepted: Apr. 17th, 2019; published: Apr. 24th, 2019
ABSTRACT
In this paper, based on the idea of Ref. [1] , we propose a modified conjugate gradient method using secant conditions for unconstrained optimization problems. The proposed algorithm improves the method in Ref. [1] , which possesses the following properties: the search direction has the sufficient descent property; the global convergence of the given algorithm will be established under suitable assumptions; numerical results are reported to test its efficiency.
Keywords:Conjugate Gradient Method, Sufficient Descent Property, Global Convergence
基于拟牛顿方程一个改进的非线性共轭梯度 算法
梁静*,马国栋#,时瑜婷,林志梅,邹文婷,李柳娜
玉林师范学院,数学与统计学院,广西 玉林
收稿日期:2019年4月2日;录用日期:2019年4月17日;发布日期:2019年4月24日
摘 要
基于拟牛顿方程,借鉴文 [1] 的思想,本文给出一个改进的具有全局收敛非线性共轭梯度算法。该文的算法对文 [1] 中算法进行了改进,所产生的搜索方向具有充分下降性。在温和的假设下,新算法具有全局收敛性。最后,数值结果检验其有效性。
关键词 :共轭梯度法,充分下降性,全局收敛性
Copyright © 2019 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文考虑求解如下无约束优化问题
(1.1)
其中 连续可微,此问题在经济管理、生产运作、工程设计等领域具有广泛的应用背景。共轭梯度法是求解问题(1.1)的有效方法之一,该方法具有算法结构简单、计算存储量少、数值效果明显的优点,其迭代公式的一般形式为:
其中 为第 次迭代点, 为搜索步长, 为搜索方向且其更新方式为
(1.2)
其中 是方向调控参数。数值优化方法是根据搜索方向的选择来定义其方法类型,从上式可以看出,搜索方向 是由参数 决定的,所以根据 的选取方式可以定义不同的共轭梯度公式,下面给出几个著名的公式:
[2] [3] , [4] , [5] ,
[6] , [7] , [8] ,
其中 和 表示函数 在 和 的梯度值, 是欧氏向量范数。众多优化专家都希望能找到理论性质良好且数值表现又好的算法,已取得众多成果(见 [9] - [25] ),其中Yuan [9] 给出如下PRP修改公式:
其中 是常数, ,同时又将此公式推广到了其它5个公式中,得到了修改的FR公式、修改的HS公式、修改的DY公式、修改的CD公式和修改的LS公式,其中文 [1] 修改的LS为:
, (1.3)
其中 , 。
本文将在此公式的基础上进一步研究,从上式可以看出公式中不含函数值信息,这势必影响此方法的有效性。众所周知,拟牛顿方法不仅含有梯度值信息也含有函数值信息,且具有更好的理论和实际表现 [10] [11] 。也有许多学者将拟牛顿法的技术思想应用到共轭梯度公式中,从而获得更好的理论性质和实际数值效果 [12] [13] 。Zhang等 [11] 给出了一个如下形式的拟牛顿方程
, (1.4)
其中 , 及
此公式包含有梯度值信息和函数值信息,理论上能更高阶地近似目标函数的Hesse矩阵。基于公式(1.3),(1.4)和文 [12] [13] 的思想,本文给出如下修改的LS共轭梯度公式
,(1.5)
其中 。相对于原LS方法,本文的创新点主要有:1) 新公式能保证方向调控参数 ;2) 新方法具有充分下降性;3) 新方法不仅使用了梯度值信息还有函数值信息。
2. 算法的描述
基于搜索方向,给出一个基于拟牛顿方程改进的非线性共轭梯度算法。
算法1:
步骤0:给定 , ,令 ,置 。
步骤1:若 ,停止。否则,进入步骤2。
步骤2:利用弱Wolfe-Powell(WWP)线搜索技术产生步长
(2.1)
(2.2)
步骤3:令 。如果 ,停止。
步骤4:利用公式(1.5)计算 ,并按如下公式计算搜索方向
(2.3)
步骤5:置 ,转步骤2。
3. 算法的充分下降性和全局收敛性
引理3.1:对所有 ,搜索方向 满足下面两式
(3.1)
和
(3.2)
是常数。
证明:首先证明(3.1)成立。根据算法1,如果 ,则 ,式(3.1)显然成立。下面利用归纳法,当 ,假如公式(2.3)满足(3.1),对 ,有
(3.3)
由 取 。下面我们分两种情形分别讨论(3.3)式:
情形I:如果 ,显然 成立。
情形II:如果 ,(3.3)式可化为
上述不等式利用了 的关系。取 ,则(3.1)成立。根据线搜索技术(2.2)可推出(3.2)也成立。证毕。
我们将采用反证法来证明算法1的全局收敛性,假设存在常数 满足
(3.4)
根据(3.4)导出矛盾,从而证明 成立。
为证明算法1的收敛性,还需要下面的常规假设条件。
假设A:1) 定义水平集 且有界,存在 满足
2) 目标函数 在水平集 上连续可微并有下界,目标函数梯度满足Lipschitz条件,所谓Lipschitz条件就是存在常数 满足下式
。 (3.5)
下面引理3.2和引理3.3在共轭梯度算法文献中有类似的结论,本文只给出引理3.3证明过程。
引理3.2:设假设A成立,序列 和 由算法1产生,则 及 ,其中 。
Gilbert和Nocedal [14] 给出下面性质(P),具体内容是:
性质(P)对于两参数 ,且满足
。 (3.6)
若对所有 ,存在常数 和 满足 和 ,有 成立。
引理3.3:如果假设A满足且序列 和 由算法1产生,且存在常数 使得 成立,则 满足性质(P)。
证明:对于公式(2.3),如果 成立,结论显然成立。否则,利用假设A(1),可推出存在常数 使下式
(3.7)
成立。利用 ,(3.1),(3.2),(3.5)~(3.7),有
取 和
利用(3.8), 和 ,则 和
因此公式(2.3)满足性质(P),引理得证。
利用假设A,引理3.1~3.3,与文献 [15] 中的定理3.2的证明类似,可得到算法1的全局收敛性定理,定理的证明请参照文献 [15] 中的定理3.2完成。
定理3.1:序列 由算法产生,若假设A成立,则 成立。
4. 数值结果
这部分将给出数值检验,Benchmar问题 [16] 在工程领域具有广泛应用背景。
1) Sphere函数:
2) Schwefel’s函数:
3) Rastrigin函数:
4) Griewank函数:
参数选取如下: ,停止准则采用Himmeblau准则:如果 ,令 ;否则,令 。如果 或者 满足,算法终止, 。若迭代次数超过1000次,程序也将终止。为比较算法1的有效性,也给出通常LS方法的数值检验,并进行比较。以下是各代码含义:
:初始点;Dim:问题的维数;NI:迭代次数;NFG:函数值与梯度值迭代次数和;Time:以秒为单位的计算机CPU时间; :算法终止时的函数值。
为比较算法1与原LS算法的效率,我们采用下述技术即两算法的所有NFG的乘积的比值再开二十四分之一(结果的总个数)次方,以通常LS算法作为底,定义为1,比值见表2,此技术见文献 [17] 。
Table 1. Numerical results
表1. 数值结果
Table 2. The Efficiency of NFG
表2. NFG的效率
从表1的结果可看,算法1和LS算法对上述4个问题都能有效地求解,迭代次数可以接受,最终函数值很接近最优函数值,新算法的CPU时间相对少一些,更具竞争力。表2的效率表明,算法1相对于原LS算法,效率提高2%。
基金项目
2017年国家级大学生创新创业训练计划项目(201710606041),广西自然科学基金(2018JJA110039)和玉林师范学院校级科研项目(2019YJKY16)。
文章引用
梁 静,马国栋,时瑜婷,林志梅,邹文婷,李柳娜. 基于拟牛顿方程一个改进的非线性共轭梯度算法
A Modified Nonlinear Conjugate Gradient Algorithm Using Secant Conditions[J]. 应用数学进展, 2019, 08(04): 676-683. https://doi.org/10.12677/AAM.2019.84076
参考文献
- 1. 陈海. 一个修改的LS非线性共轭梯度算法[J]. 应用数学进展, 2013(2): 48-54.
- 2. Polak, E. and Ribiere, G. (1969) Note sur la xonvergence de directions conjugees. Rev. Francaise informat Recherche Operatinelle, 3e Annee, 16, 35-43.
- 3. Polyak, B.T. (1969) The Conjugate Gradient Method in Extreme Problems. USSR Computational Mathematics and Mathematical Physics, 9, 94-112
- 4. Hestenes, M.R. and Stiefel, E. (1952) Method of Conjugate Gradient for Solving Linear Equations. Journal of Research of the National Bureau of Standards, 49, 409-436. https://doi.org/10.6028/jres.049.044
- 5. Fletcher, R. and Reeves, C. (1964) Function Minimization bu Conjugate Gradients. Compute Journal, 7, 149-154.
- 6. Dai, Y. and Yuan, Y. (1999) A Nonlinear Conjugate Gradient with a Strong Global Convergence Properties. SIAM Journal on Optimization, 10, 177-182. https://doi.org/10.1137/S1052623497318992
- 7. Fletcher, R. (1980) Practical Method of Optimization, Vol. I: Unconstrained Optimization. 2nd Edition, Wiley, Hoboken.
- 8. Liu, Y. and Storey, C. (1992) Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory. Journal of Optimization Theory and Application, 69, 17-41.
- 9. Yuan, G. (2009) Modified Nonlinear Conjugate Gradient Methods with Sufficient Descent Property for Large-Scale Optimization Problems. Optimization Letters, 3, 11-21. https://doi.org/10.1007/s11590-008-0086-5
- 10. Yuan, G. and Wei, Z. (2010) Convergence Analysis of a Modified BFGS Method on Convex Minimizations. Computational Optimization and Applications, 47, 237-255. https://doi.org/10.1007/s10589-008-9219-0
- 11. Zhang, J., Deng, N. and Chen, L. (1999) New Quasi-Newton Equation and Related Methods for Unconstrained Optimization. Journal of Optimization Theory and Application, 102, 147-167. https://doi.org/10.1023/A:1021898630001
- 12. Yuan, G., Wei, Z. and Zhao, Q. (2014) A Modified Polak-Ribière-Polyak Conjugate Gradientalgorithm for Large-Scale Optimization Problems. IIE Transactions, 46, 397-413. https://doi.org/10.1080/0740817X.2012.726757
- 13. Yuan, G. and Zhang, M. (2013) A Modified Hestenes-Stiefel Conjugate Gradient Algorithm for Large-Scale Optimization. Numerical Functional Analysis and Optimization, 34, 914-937. https://doi.org/10.1080/01630563.2013.777350
- 14. Gilbert, J.C. and Nocedal, J. (1992) Global Convergence Properties of Conjugate Gradient Methods for Optimization. SIAM Journal on Optimization, 2, 21-42. https://doi.org/10.1137/0802003
- 15. Hager, W.W. and Zhang, H. (2005) A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search. SIAM Journal on Optimization, 16, 170-192. https://doi.org/10.1137/030601880
- 16. Yao, S., He, D. and Shi, L. (2018) An Improved Perry Conjugate Gradient Method with Adaptive Parameter Choice. Numerical Algorithms, 78, 1255-1269. https://doi.org/10.1007/s11075-017-0422-x
- 17. Yuan, G. and Lu, X. (2009) A Modified PRP Conjugate Gradient Method. Annals of Operations Research, 66, 73-90. https://doi.org/10.1007/s10479-008-0420-4
- 18. Dai, Y. and Liao, L. (2001) New Conjugacy Conditions and Re-lated Nonlinear Conjugate Methods. Applied Mathematics and Optimization, 43, 87-101. https://doi.org/10.1007/s002450010019
- 19. Hager, W.W. and Zhang, H. (2006) Algorithm 851: CGDESENT, A Conjugate Gradient Method with Guaranteed Descent. ACM Transactions on Mathematical Software, 32, 113-137. https://doi.org/10.1145/1132973.1132979
- 20. Li, G., Tang, C. and Wei, Z. (2007) New Conjugacy Condition and Related New Conjugate Gradient Methods for Unconstrained Optimization Problems. Journal of Computational and Applied Mathemathics, 202, 532-539.
- 21. Wei, Z., Li, G. and Qi, L. (2006) New Nonlinear Conjugate Gradient Formulas for Large-Scale Unconstrained Optimization Problems. Applied Mathematics and Computation, 179, 407-430. https://doi.org/10.1016/j.amc.2005.11.150
- 22. Wei, Z., Li, G. and Qi, L. (2008) Global Convergence of the PRP Conjugate Gradient Methods with Inexact Line Search for Nonconvex Unconstrained Optimization Problems. Mathematics of Computation, 77, 2173-2193. https://doi.org/10.1090/S0025-5718-08-02031-0
- 23. Wei, Z., Yao, S. and Lin, L. (2006) The Convergence Properties of Some New Conjugate Gradient Methods. Applied Mathematics and Computation, 183, 1341-1350. https://doi.org/10.1016/j.amc.2006.05.150
- 24. Yuan, G., Lu, X. and Wei, Z. (2009) A Conjugate Gradient Method with Descent Direction for Unconstrained Optimization. Journal of Computational and Applied Mathematics, 102, 519-530. https://doi.org/10.1016/j.cam.2009.08.001
- 25. 李向荣. 修改的DY和HS共轭梯度算法及其全局收敛性[J]. 理论数学, 2011(1): 1-7.
NOTES
*第一作者。
#通讯作者。