一類修正的DL共軛梯度法

謝 麗

(重慶師范大學 數(shù)學科學學院，重慶 401331)

考慮以下的無約束優(yōu)化問題：

minf(x)，x∈Rn

(1)

其中，f:Rn→R是連續(xù)可微的.

共軛梯度法是求解這類大規(guī)模無約束優(yōu)化問題的重要方法，它的迭代格式如下：

xk+1=xk+αkdk

(2)

其中步長αk通過某種線搜索得到，搜索方向dk滿足：

(3)

其中gk=f(xk)，βk∈R為共軛參數(shù)，βk選取的不同代表著不同的共軛梯度法. 其中著名的βk公式有：FR[1]方法、HS[2]方法、PRP[3]方法和DY[4]方法，它們的表達式分別為：

其中‖.‖表示范數(shù)，yk-1=gk-gk-1.

在以上四個公式所對應的方法中，其中PRP方法和HS方法數(shù)值效果比較好，而FR方法和DY方法的理論收斂性比較好. 近些年來，為了得到數(shù)值效果及理論收斂性都較為理想的方法，許多學者對共軛梯度法進行了深入研究.

2001年在文獻[5]中Dai等人提出了截斷形式DL方法：

(4)

其中常數(shù)t>0，sk-1=xk-xk-1.

2013年在文獻[6]中Yao等人基于文獻[5,7]提出了一類共軛梯度法：

(5)

以上方法可以看作是一個修正的DL方法，通過文獻[7]中修正的HS方法去代替式(4)中的截斷部分.

2014年江羨珍等人在文獻[8]中提出一個修正的HS方法：

(6)

其中參數(shù)μ>2.

1 一類新的DL共軛梯度法

本文受文獻[6,8]的啟發(fā)，提出了一類新的DL共軛梯度方法，其共軛參數(shù)公式為：

(7)

其中參數(shù)μ>2,將由式(2)(3)(7)組成的方法稱作JHSDL共軛梯度方法.

f(xk+αkdk)-f(xk)

(8)

(9)

0<δ<σ<1

2 收斂性分析

假設gk≠0，對所有k成立. 為了證明JHSDL方法的全局收斂性，本文做如下兩個假設：

(A)水平集Ω={x∈Rn:f(x)

(B)目標函數(shù)f在Ω的某個領域N是連續(xù)可微的，且梯度g是Lipschitz連續(xù)的，即存在常數(shù)L>0使得：

(10)

假設(A)保證了存在一個常數(shù)c有‖sk‖2c，對?k≥0成立. 假設(B)意味著‖g‖γ -對?x∈Ω成立，其中γ -=2cL+‖g0‖.

引理1 考慮JHSDL方法，如果αk是由標準Wolfe線搜索得到且σ∈[0,1]，則?k有：

(11)

證用歸納法證明：

當k=0時，goTd0=-‖g0‖2

(12)

其中μ>2，則式(11)成立.

引理1意味著JHSDL方法在標準Wolfe條件下滿足充分下降條件，以下的定理說明了JHSDL方法對一致凸函數(shù)是強收斂的.

定理1 假設f是一致凸函數(shù)且假設(A)(B)成立，考慮JHSDL方法，如果αk是由標準Wolfe線搜索計算得到且σ∈[0,1]，則：

(13)

(14)

‖dk‖

(15)

結合Zoutendijk條件和式(12)(15)有：

(16)

則顯然式子(13)成立.

現(xiàn)證明JHSDL方法對一般函數(shù)是全局收斂的，在證明之前先給出Gilbert和Nocedal在文獻[9]敘述的性質(*).

性質(*)考慮方法(2)(3)，假設0<γ1‖gk‖γ2，對?k≥1成立. 就說方法(2)(3)具有性質(*)，如果存在常數(shù)b>1和λ>0，對?k≥1，都有：

|βk|b

(17)

以及

‖sk-1‖λ?|βk|

(18)

引理2 假設(A)(B)成立，考慮JHSDL共軛梯度方法(2)(3)，其中βk由(7)給出，若存在一個常數(shù)γ>0有‖gk‖≥γ，對所有k≥1成立且αk滿足Wolfe條件，那么共軛梯度法JHSDL滿足性質(*).

證由假設知‖gk‖滿足

0<γ‖gk‖

(19)

由Wolfe條件和定理1，則有

(20)

由式(19)(20)和‖sk‖的有界性：

(21)

(22)

同時有‖sk-1‖λ成立，則由式(14)(19)(20)有：

|βkJHSDL|

(23)

因此，JHSDL方法具有性質(*).

(24)

由引理1和引理3，參照文獻[6]中類似的證明方法可以得到以下引理4.

引理4 假設(A)(B)成立，考慮JHSDL方法，其中αk滿足Wolfe線搜索，如果存在常數(shù)γ>0，使得：

‖gk‖≥γ,?k≥1

(25)

證令

則由式(3)對?k≥2，有：

μk=γk+δkμk-1

(26)

利用‖μk‖=‖μk-1‖=1和式(26)，以及βk(1)≥0可得：

‖γk‖=‖μk-δkμk-1‖=‖δkμk-μk-1‖

(27)

‖μk-μk-1‖‖(1+δ)μk-(1+δ)μk-1‖‖μk-δkμk-1‖+‖δkμk-μk‖=2‖γk‖

(28)

(29)

由假設有‖sk‖2c，‖gk‖以及式(29)可得：

‖-gk+βk(2)dk-1‖

(30)

因此有：

(31)

設N*定義為正整數(shù)集合，對于λ>0以及正整數(shù)Δ和k，定義：

Kλk, Δ:={i∈N*:kik+Δ-1,‖sk-1‖>λ}

(32)

將|Kλk, Δ|定義為Kλk, Δ中元素的個數(shù)，由性質(*)可以證明以下的引理.

引理5 假設(A)成立，考慮JHSDL方法，其中αk滿足Wolfe線搜索，如果式(25)成立，則存在λ>0使得對任意Δ∈N*和任意指標集k0，存在一個指標集k≥k0，使得：

(33)

該引理的證明與文獻[5]中的引理3.5類似，文獻[5]中假設搜索方向滿足充分下降條件，本文不需要做出這個假設，在Wolfe線搜索下，JHSDL方法產生的搜索方向具有充分下降性.

根據(jù)以上的引理，接下來證明JHSDL方法的全局收斂性.

定理2 若目標函數(shù)f(x)滿足假設(A)(B)，考慮JHSDL方法，若步長αk由Wolfe得到，則：

(34)

(35)

由式(35)，‖μk‖=1和假設(A)有：

(36)

(37)

‖μi-μk-1‖

(38)

由式(37)和(38)，在式(36)中令l=k+Δ-1，可得：

(39)

3 結束語

本文在DL方法和JHS方法基礎上提出了一類修正的DL共軛梯度法—JHSDL方法. 該方法相對于DL共軛梯度法具有一個更好的性質，即在標準Wolfe線搜索條件下具有充分下降性和全局收斂性.