AAM  >> Vol. 8 No. 4 (April 2019)

    基于拟牛顿方程一个改进的非线性共轭梯度算法
    A Modified Nonlinear Conjugate Gradient Algorithm Using Secant Conditions

  • 全文下载: PDF(531KB) HTML   XML   PP.676-683   DOI: 10.12677/AAM.2019.84076  
  • 下载量: 244  浏览量: 350   科研立项经费支持

作者:  

梁 静,马国栋,时瑜婷,林志梅,邹文婷,李柳娜:玉林师范学院,数学与统计学院,广西 玉林

关键词:
共轭梯度法充分下降性全局收敛性Conjugate Gradient Method Sufficient Descent Property Global Convergence

摘要:

基于拟牛顿方程,借鉴文[1]的思想,本文给出一个改进的具有全局收敛非线性共轭梯度算法。该文的算法对文[1]中算法进行了改进,所产生的搜索方向具有充分下降性。在温和的假设下,新算法具有全局收敛性。最后,数值结果检验其有效性。

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.

1. 引言

本文考虑求解如下无约束优化问题

min x R n f ( x ) , (1.1)

其中 f ( x ) : R n R 连续可微,此问题在经济管理、生产运作、工程设计等领域具有广泛的应用背景。共轭梯度法是求解问题(1.1)的有效方法之一,该方法具有算法结构简单、计算存储量少、数值效果明显的优点,其迭代公式的一般形式为:

x k + 1 = x k + α k d k , k = 0 , 1 , 2 ,

其中 x k 为第 k 次迭代点, α k > 0 为搜索步长, d k 为搜索方向且其更新方式为

d k = { g k + β k d k 1 , k 1 , g k , k = 0 , (1.2)

其中 β k 是方向调控参数。数值优化方法是根据搜索方向的选择来定义其方法类型,从上式可以看出,搜索方向 d k 是由参数 β k 决定的,所以根据 β k 的选取方式可以定义不同的共轭梯度公式,下面给出几个著名的公式:

β k P R P = g k + 1 T ( g k + 1 g k ) g k 2 [2] [3] , β k H S = g k + 1 T ( g k + 1 g k ) ( g k + 1 g k ) T d k [4] , β k F R = g k + 1 T g k + 1 g k 2 [5] ,

β k D Y = g k + 1 T g k + 1 ( g k + 1 g k ) T d k [6] , β k C D = g k + 1 T g k + 1 d k T g k [7] , β k L S = g k + 1 T ( g k + 1 g k ) g k T d k [8] ,

其中 g k = f ( x k ) g k + 1 = f ( x k + 1 ) 表示函数 f ( x ) x k x k + 1 的梯度值, . 是欧氏向量范数。众多优化专家都希望能找到理论性质良好且数值表现又好的算法,已取得众多成果(见 [9] - [25] ),其中Yuan [9] 给出如下PRP修改公式:

β k M P R P = β k P R P min { β k P R P , μ y k 2 g k 4 g k + 1 T d k } ,

其中 μ > 1 4 是常数, y k = g k + 1 g k ,同时又将此公式推广到了其它5个公式中,得到了修改的FR公式、修改的HS公式、修改的DY公式、修改的CD公式和修改的LS公式,其中文 [1] 修改的LS为:

β k M M L S + = β k M M L S min { β k M M L S , μ y k m 2 ( d k T g k ) 2 g k + 1 T d k } (1.3)

其中 y k m = g k + 1 g k + 1 g k g k β k M M L S = g k + 1 T y k m d k T g k

本文将在此公式的基础上进一步研究,从上式可以看出公式中不含函数值信息,这势必影响此方法的有效性。众所周知,拟牛顿方法不仅含有梯度值信息也含有函数值信息,且具有更好的理论和实际表现 [10] [11] 。也有许多学者将拟牛顿法的技术思想应用到共轭梯度公式中,从而获得更好的理论性质和实际数值效果 [12] [13] 。Zhang等 [11] 给出了一个如下形式的拟牛顿方程

B k + 1 S k = y k m (1.4)

其中 y k m = y k + γ k 1 s k s k = x k + 1 x k

γ k 1 = 3 ( g k + 1 + g k ) T s k + 6 ( f ( x k ) f ( x k + 1 ) ) s k 2 ,

此公式包含有梯度值信息和函数值信息,理论上能更高阶地近似目标函数的Hesse矩阵。基于公式(1.3),(1.4)和文 [12] [13] 的思想,本文给出如下修改的LS共轭梯度公式

β k M M L S * = β k M M L S min { β k M M L S , μ y k m 2 ( d k T g k ) 2 g k + 1 T d k } (1.5)

其中 β k M M L S = g k + 1 T y k m d k T g k 。相对于原LS方法,本文的创新点主要有:1) 新公式能保证方向调控参数 β k M M L S * 0 ;2) 新方法具有充分下降性;3) 新方法不仅使用了梯度值信息还有函数值信息。

2. 算法的描述

基于搜索方向,给出一个基于拟牛顿方程改进的非线性共轭梯度算法。

算法1:

步骤0:给定 x 0 n , δ ( 0 , 1 / 2 ) , σ ( δ , 1 ) ε > 0 ,令 d 0 = g 0 = f ( x 0 ) ,置 k : = 0

步骤1:若 g k ε ,停止。否则,进入步骤2。

步骤2:利用弱Wolfe-Powell(WWP)线搜索技术产生步长 α k

f ( x k + α k d k ) f k + δ α k g k T d k , (2.1)

g ( x k + α k d k ) T d k σ g k T d k . (2.2)

步骤3:令 x k + 1 = x k + α k d k 。如果 g k + 1 ε ,停止。

步骤4:利用公式(1.5)计算 β k M M L S * ,并按如下公式计算搜索方向

d k + 1 = g k + 1 + β k M M L S * d k , (2.3)

步骤5:置 k : = k + 1 ,转步骤2。

3. 算法的充分下降性和全局收敛性

引理3.1:对所有 k 0 ,搜索方向 d k 满足下面两式

d k T g k c g k 2 (3.1)

d k T y k c ( 1 σ ) g k 2 (3.2)

c > 0 是常数。

证明:首先证明(3.1)成立。根据算法1,如果 k = 0 ,则 g 0 T d 0 = g 0 2 ,式(3.1)显然成立。下面利用归纳法,当 k 1 ,假如公式(2.3)满足(3.1),对 k + 1 ,有

g k + 1 T d k + 1 = g k + 1 2 + β k M M L S * d k T g k + 1 = g k + 1 2 + [ g k + 1 T y k m d k T g k min { g k + 1 T y k m d k T g k , μ y k m 2 ( d k T g k ) 2 g k + 1 T d k } ] d k T g k + 1 (3.3)

d k T g k > 0. u = d k T g k 2 μ g k + 1 , v = 2 μ g k + 1 T d k d k T g k y k m 。下面我们分两种情形分别讨论(3.3)式:

情形I:如果 g k + 1 T y k m d k T g k < μ y k m 2 ( d k T g k ) 2 g k + 1 T d k ,显然 g k + 1 T d k + 1 = g k + 1 2 成立。

情形II:如果 g k + 1 T y k m d k T g k μ y k m 2 ( d k T g k ) 2 g k + 1 T d k ,(3.3)式可化为

g k + 1 T d k + 1 = g k + 1 2 + ( g k + 1 T y k m d k T g k μ y k m 2 ( d k T g k ) 2 g k + 1 T d k ) d k T g k + 1 = d k T g k + 1 g k + 1 T y k m g k + 1 2 ( d k T g k ) μ y k m 2 d k T g k ( g k + 1 T d k ) 2 d k T g k = u T v 1 2 ( u 2 + v 2 ) d k T g k + ( 1 1 4 μ ) g k + 1 2 d k T y k m d k T g k ( 1 1 4 μ ) g k + 1 2 ,

上述不等式利用了 u T v 1 2 ( u 2 + v 2 ) 的关系。取 c = 1 1 4 μ ,则(3.1)成立。根据线搜索技术(2.2)可推出(3.2)也成立。证毕。

我们将采用反证法来证明算法1的全局收敛性,假设存在常数 ε 0 > 0 满足

g k ε 0 , k 0. (3.4)

根据(3.4)导出矛盾,从而证明 g k 0 , k 成立。

为证明算法1的收敛性,还需要下面的常规假设条件。

假设A:1) 定义水平集 Ω = { x n : f ( x ) f ( x 0 ) } 且有界,存在 L 0 > 0 满足

2 f ( x ) L 0 , x Ω .

2) 目标函数 f 在水平集 Ω 上连续可微并有下界,目标函数梯度满足Lipschitz条件,所谓Lipschitz条件就是存在常数 L > 0 满足下式

g ( x ) g ( y ) L x y , x , y Ω (3.5)

下面引理3.2和引理3.3在共轭梯度算法文献中有类似的结论,本文只给出引理3.3证明过程。

引理3.2:设假设A成立,序列 { g k } { d k } 由算法1产生,则 d k 0 k = 0 u k + 1 u k 2 < ,其中 u k = d k d k

Gilbert和Nocedal [14] 给出下面性质(P),具体内容是:

性质(P)对于两参数 γ 1 , γ 2 > 0 ,且满足

0 < γ 1 g k γ 2 (3.6)

若对所有 k ,存在常数 b > 1 λ > 0 满足 | β k | b s k λ ,有 | β k | 1 2 b 成立。

引理3.3:如果假设A满足且序列 { g k } { d k } 由算法1产生,且存在常数 M > 0 使得 d k M 成立,则 β k M M L S * 满足性质(P)。

证明:对于公式(2.3),如果 g k + 1 T y k m d k T g k μ y k m 2 ( d k T g k ) 2 g k + 1 T d k 成立,结论显然成立。否则,利用假设A(1),可推出存在常数 M 1 > 0 使下式

s k M 1 (3.7)

成立。利用 d k M ,(3.1),(3.2),(3.5)~(3.7),有

| β k M M L S * | | g k + 1 T y k m d k T g k | + μ y k m 2 ( d k T g k ) 2 | g k + 1 T d k | g k + 1 g k + 1 g k + 3 [ g k + 1 g k + 2 f ( ς k ) s k ] c g k 2 + μ g k + 1 d k g k + 1 g k + 3 [ g k + 1 g k + 2 f ( ς k ) s k ] 2 c 2 g k 4 [ L γ 2 + 3 ( L + L 0 ) ] s k c γ 1 2 + [ μ γ 2 M ( L + 3 ( L + L 0 ) ) 2 M 1 ] s k c 2 γ 1 4 = ( [ L γ 2 + 3 ( L + L 0 ) ] c γ 1 2 + [ μ γ 2 M ( L + 3 ( L + L 0 ) ) 2 M 1 ] c 2 γ 1 4 ) s k ,

b = max { 2 , [ L γ 2 + 3 ( L + L 0 ) ] c γ 1 2 + [ μ γ 2 M ( L + 3 ( L + L 0 ) ) 2 M 1 ] c 2 γ 1 4 }

λ = c 2 γ 1 4 b { [ L γ 2 + 3 ( L + L 0 ) ] c γ 1 2 + [ μ γ 2 M ( L + 3 ( L + L 0 ) ) 2 M 1 ] } .

利用(3.8), λ b > 1 ,则 | β k M M L S * | b

| β k M M L S * | [ L γ 2 + 3 ( L + L 0 ) ] c γ 1 2 + [ μ γ 2 M ( L + 3 ( L + L 0 ) ) 2 M 1 ] c 2 γ 1 4 s k [ L γ 2 + 3 ( L + L 0 ) ] c γ 1 2 + [ μ γ 2 M ( L + 3 ( L + L 0 ) ) 2 M 1 ] c 2 γ 1 4 λ = 1 2 b .

因此公式(2.3)满足性质(P),引理得证。

利用假设A,引理3.1~3.3,与文献 [15] 中的定理3.2的证明类似,可得到算法1的全局收敛性定理,定理的证明请参照文献 [15] 中的定理3.2完成。

定理3.1:序列 { d k , g k } 由算法产生,若假设A成立,则 lim k inf g k = 0 成立。

4. 数值结果

这部分将给出数值检验,Benchmar问题 [16] 在工程领域具有广泛应用背景。

1) Sphere函数: f S p h ( x ) = i = 1 n x i 2 , x i [ 5.12 , 5.12 ] , f S p h ( x * ) = 0.

2) Schwefel’s函数: f S c h D S ( x ) = i = 1 n ( j = 1 i x j ) 2 , x i [ 65.536 , 65.536 ] , f S c h D S ( x * ) = 0.

3) Rastrigin函数: f R a s ( x ) = 10 n + i = 1 n ( x i 2 10 cos ( 2 π x i ) ) , x i [ 5.12 , 5.12 ] , f R a s ( x * ) = 0.

4) Griewank函数: f G r i ( x ) = 1 + i = 1 n x i 2 4000 i = 1 n cos x i i , x i [ 600 , 600 ] , f G r i ( x * ) = 0.

参数选取如下: ε = 10 5 , δ = 0.1 , σ = 0.9 ,停止准则采用Himmeblau准则:如果 | f ( x k ) | > e 1 ,令 stop 1 = | f ( x k ) f ( x k + 1 ) | | f ( x k ) | ;否则,令 stop 1 = | f ( x k ) f ( x k + 1 ) | 。如果 g ( x ) < ε 或者 stop 1 < e 2 满足,算法终止, e 1 = e 2 = 10 5 。若迭代次数超过1000次,程序也将终止。为比较算法1的有效性,也给出通常LS方法的数值检验,并进行比较。以下是各代码含义:

x 0 :初始点;Dim:问题的维数;NI:迭代次数;NFG:函数值与梯度值迭代次数和;Time:以秒为单位的计算机CPU时间; f ( x ) :算法终止时的函数值。

为比较算法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)。

NOTES

*第一作者。

#通讯作者。

文章引用:
梁静, 马国栋, 时瑜婷, 林志梅, 邹文婷, 李柳娜. 基于拟牛顿方程一个改进的非线性共轭梯度算法[J]. 应用数学进展, 2019, 8(4): 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.