一类具有充分下降性的修正的DL共轭梯度法(修改稿)
张莉林
【摘 要】基于DL共轭梯度方法,提出了一类修正的DL方法来解决无约束优化问题.该方法相对于DL共轭梯度方法具有一个更好的性质,即在强Wolfe线搜索条件下搜索方向具有充分下降性;证明了该方法在强Wolfe线搜索条件具有全局收敛性. 【期刊名称】《重庆工商大学学报（自然科学版）》 【年(卷),期】2017(034)006 【总页数】5页(P41-45)
【关键词】共轭梯度法;强Wolfe线搜索;充分下降性;全局收敛性 【作 者】张莉林
【作者单位】重庆师范大学数学科学学院,重庆 401331 【正文语种】中 文 考虑无约束极小化问题： 其中,f:Rn→R是连续可微函数.
共轭梯度法是求解大规模无约束优化问题的一个重要方法，其迭代公式为 其中步长αk通过某种线搜索计算得到,dk为搜索方向,gk=▽f(xk),βk∈R为共轭参数,选取不同βk产生不同的共轭梯度法.
经典的共轭梯度法有FR[1]方法, HS[2]方法, PRP[3]方法和LS[4]方法, 其表示方法如下:
其中‖·‖表Euclidean数,yk-1=gk-gk-1.
在文献[5]中戴彧虹和廖立志提出了截断形式DL方法: 其中常数t>0,sk-1=xk-xk-1.
在文献[6]中程云龙等人基于文献[5,7]提出了一类共轭梯度方法：
可视为一个修正的DL方法,通过文献[7]中修正的LS方法来代替式(4)中取大的部分.
在文献[8]中杜学武等人提出了一个修正的LS方法:
本文受文献[6,8]的启发,提出了一类新的修正的DL共轭梯度公式: 记由式(2)(3)(7)构成的共轭梯度法为NVLS*DL方法. 为了分析该方法的全局收敛性，采用强 Wolfe 线搜索： 其中0<δ<σ<1.
假设A 水平集Ω={x∈Rnfx≤fx1}有界, 即存在一个常数B>0, 使得‖x‖≤B，x∈Ω, 其中x1是初始点.
假设B 在水平集Ω的邻域Ν中,f连续可微且梯度函数g是Lipschitz连续的, 即存在一个常数L>0, 使得∀x,y∈Ω，
由假设A,假设B知存在常数使得对任意的k≥1都有： 搜索方向dk具有下降性和充分下降性分别为 其中常数c>0.
引理1[8] 考虑NVLS*方法式(2)和式(3),其中假设αk满足强Wolfe线搜索式(8)和式(9)且0<σ<,则∀k≥1有
引理2 考虑NVLS*DL方法式(2)和式(3),其中假设αk满足强Wolfe 线搜索条件式(8)和式(9)且0<σ<, 则‖gk‖2，∀k≥1即搜索方向dk具有充分下降性即式(13)成立.
证明‖g1‖2≤-1-2σ‖g1‖2,假设1-2σ‖gk-1‖2,由强Wolfe线搜索条件式(9)有 及引理1得：
‖ -‖
-‖1-2σ‖gk‖2
取式(13)中的c=1-2σ<1 , 则充分下降条件式(13)成立.
引理3[9] 若目标函数fx满足假设A,假设B,考虑迭代公式为式(2)(3)的任意共轭梯度法, 其中dk是下降方向, αk满足强Wolf线搜索.若则
由引理2和引理3, 参照文献[6,10]中类似的证明方法可以证明下面的引理4. 引理4 若目标函数fx满足假设A，假设B,考虑NVLS*DL方法式(2)和式(3),其中满足强 Wolfe 线搜索且0<σ<，如果存在常数γ>0, 使得 则dk≠0且‖uk-uk-1‖2<+∞,其中uk=. 证明 令
则由式(3)对∀k≥2, 有：
显然，有‖uk‖=‖uk-1‖=1, 由γk的定义以及可得： 则有：
‖uk-uk-1‖≤‖1+δkuk-1+δkuk-1‖≤‖uk-δkuk-1‖+‖δkuk-uk-1‖=2‖γk‖ 由强Wolfe线搜索条件(9)式和式(15)可得：
由假设A有‖sk-1‖=‖xk-xk-1‖≤‖xk‖+‖xk-1‖≤2B,以及式(11)(22)可得： ‖-gk+dk-1‖≤‖gk‖+t‖dk-1‖≤‖gk‖+t‖sk-1‖≤+ 由式(21)和式(23)以及引理3则有： ‖‖γk‖2=
性质*[6] 考虑迭代公式为式(2)式(3)的共轭梯度法, 假设对∀k≥1都有 若对任意k, 都存在常数b>1,λ>0使得 以及
则称该方法具有性质*
下面将证明本文提出的NVLS*DL方法具有性质* 由式(15)以及引理2可知： c(1-σ)‖gk-1‖2≥(1-σ)cγ2 文献[8]中引理4.1证明了
再由式(10)(11)(28)以及引理2证得的充分下降条件成立可得： ≤+=
可以定义b=>1和λ=>0, 若 ‖sk-1‖≤λ, 则有 则NVLS*DL方法具有性质*[6].
设Ν*定义为正整数集合, 对于λ>0和正整数Δ，定义 ‖sk-1‖>λ}
将定义为中元素的个数, 由性质*可以证明下面的引理.
引理5 若假设A成立,考虑NVLS*DL方法,其中αk满足强 Wolfe 线搜索，0<σ<.若式(18)成立,则存在λ>0使得对任意Δ∈Ν*和任意指标集k0，存在指标集k≥k0，使得
该引理的证明与文献[5]中的引理3.5类似.文献[5]中假设了满足充分下降条件(13), 本文不需要这个假设，在强Wolfe线搜索下NVLS*DL方法产生的搜索方向dk具有充分下降性.
根据上面的引理，下面来证明NVLS*DL方法的全局收敛性.
定理1 若目标函数f(x)满足假设A,假设B,考虑NVLS*DL方法,若αk满足强Wolfe 线搜索条件式(8)(9)且 0<σ<,则
证明 假设gk>0，则式(18)成立,从而引理4和引理5中的结论成立.定义uk=，∀k≥1, 对任意指标l,k, 其中l≥k， ‖si-1‖‖si-1‖ui-1-uk-1 由式(33)，uk=1和假设A可得:
‖si-1‖≤‖xl-xk-1‖+‖si-1‖‖ui-1-uk-1‖≤2B+‖si-1‖‖ui-1-uk-1‖
设λ>0和引理5，定义是不小于的最小整数,由引理5可知存在指标k0≥1使得 对于这样的Δ和k0，由引理5给出的指标k≥k0，使得
对任何指标i∈k,k+Δ-1,由Cauchy-Schwartz不等式和式(35)可得: ‖ui-uk-1‖≤‖uj-uj-1‖≤(i-k+1≤=
由式(35)和式(36)，在式(34)中令l=k+Δ-1，可得： ‖si-1‖
这与定义中的Δ≥矛盾，故假设不成立.
【相关文献】
[1] FLETCHER R, REEVES C. Function Minimization by Conjugate Gradients[J]. Computation, 19,7(2): 149-154
[2] HESTENES M R, STIEFEL E L. Methods of Conjugate Gradients for Solving Linear Systems[J]. J Res Nat Bur Standards, 1952 (49): 409-436
[3] POLAK E, RIBIRE G. Note Sur La Convergence De Methods de Directions Conjugées[J]. Rev Fr Inf Recherche Opertionelle, 1969(3): 35-43
[4] LIU Y, STOREY C. Efficient Generalized Conjugate Gradient Algorithms(part 1)[J]. J Optim Theory Appl, 1991,69(7):129-137
[5] DAI Y H , LIAO L Z. New Conjugacy Conditions and Related Nonlinear Conjugate Gradient Methods[J] Appl Math Optim, 2001 (43): 87-101
[6] CHENG Y L , MOU Q , PAN X B. A Sufficient Descent Conjugate Gradient Method and Global Convergence [J]. Optimization Methods and Software, 2016(31): 577-590 [7] WEI Y S , WEI Z X, HUANG H. A Note About WYL’s Conjugate Gradient Method and Its Applications[J]. Applied Mathematics and Computation, 2007(2): 381-388 [8] XUEWU D, PEMG Z, WENYA M. Some Modified Conjugate Gradient Methods for Unconstrained[J]. Journal of Computational and Applied Mathematics, 2016,305:92-114 [9] DAI Y H , HAN J , LIU G. Convergence Properties of Nonlinear Conjugate Gradient Methods[J]. SIAM Journal on Optimization, 1999,10(2) 345-358
[10] AO W B. Global Convergence for a Modified DY Conjngate Gradient
Algorithm[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2013,30(10):17-20