非精確線搜索條件下共軛梯度法的收斂性分析

鞠靜潔，龐德艷，杜守強(qiáng)

（青島大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山東 青島 266071）

0 引言

討論無約束最優(yōu)化問題

其中f為RN上的可微函數(shù).本文中‖·‖為歐幾里得范數(shù).

共軛梯度法自創(chuàng)立以來就被廣泛應(yīng)用于解無約束最優(yōu)化問題，是求解大規(guī)模無約束優(yōu)化問題的一種很有效的方法［1－11］，原因在于它在計(jì)算過程中只需要目標(biāo)函數(shù)值和梯度函數(shù)值，不需要矩陣存儲(chǔ)，卻比最速下降法有更好的數(shù)值效果，如由Hideaki與Yasushi提出的使用目標(biāo)函數(shù)值的共軛梯度法.

傳統(tǒng)的求解問題（1）的共軛梯度法的迭代公式為

其中g(shù)k＝▽f（xk），αk＞0是步長，dk是搜索方向，βk是一個(gè)參數(shù).

本文將介紹兩種改進(jìn)的共軛梯度法，它們的步長都是由一種新的Wolfe線搜索方法［5］

與

本文結(jié)構(gòu)為：在第1、2部分中將分別給出在新的Wolfe型線搜索條件下的兩種算法，并詳細(xì)介紹其收斂性質(zhì)；第3部分給出這兩種算法在其它的非精確線搜索條件下的一些討論；最后，分別給出這幾種算法的數(shù)值實(shí)例以說明它們的有效性.

1 算法Ⅰ及其收斂性分析

算法Ⅰ

步驟0：選取初始點(diǎn)x1∈RN，給定參數(shù)0＜ρ＜，0＜σ＜1且ρ＜σ，容許誤差0＜ε?1，令d1＝－g1，k＝1.

步驟1：給定xk，dk∈RN，計(jì)算滿足不等式（4），（5）的αk＞0.由（2）式計(jì)算xk＋1∈RN.

步驟2：若gk＋1＝0，停止.否則轉(zhuǎn)第3步.

步驟3：由（6）式計(jì)算βk＋1∈R，計(jì)算搜索方向

步驟4：令k＝k＋1.轉(zhuǎn)到步驟1.

為了建立算法Ⅰ的全局收斂性，先給出如下假設(shè)及引理.

假設(shè)1 A1）f：RN→R在水平集Γ＝｛x∈RN：f（x）≤f（x1）｝中有下界，x1∈RN為初始點(diǎn).A2）▽f：RN→RN在Γ的某個(gè)鄰域N中是Lipsichitz連續(xù)的，即存在L＞0滿足

引理1 若假設(shè)1成立，則Wolfe型線搜索方法（4）和（5）可行.

引理1的證明見文獻(xiàn)［5］.

引理2 算法Ⅰ中的序列（dk）k∈N滿足下降條件，即gkTdk＜0（k∈N）.

證 顯然d＝－g∈RN滿足gTd＜0.設(shè)gTd ＜0對(duì)任意n∈N成立，則由不等式（4）知1111nn

若gTn＋1dn≤0，則

因此，由歸納法可知gTkdk＜0（k∈N）.

引理3 設(shè)假設(shè)1成立，并結(jié)合等式（2）的任意方法，這里αk滿足不等式（4），（5），則

證 由線搜索（4），（5）及假設(shè)1可知（2σ＋L）αk‖dk‖2≥－gTkdk，從而有

對(duì)上式兩邊同時(shí)平方可得

由（4）式可知

引理得證.

由假設(shè)1和引理3可推出如下引理.

引理4 設(shè)假設(shè)1成立，且βk滿足

則由等式（2）和（3）產(chǎn)生的（xk）k∈N在穩(wěn)定點(diǎn)停止或者在收斂點(diǎn)停止，即

證 若‖gk0‖＝0（k0∈N），則立即可得結(jié)果.考慮‖gk‖≠0（k∈N）的情形.由等式（3），有

從而

因此，對(duì)于?k∈N，有

從而有

假設(shè)存在c1＞0，對(duì)?k∈N，有‖gk‖≥c1，則可得

這證明了

定理1 設(shè)假設(shè)1成立，則算法Ⅰ在一個(gè)穩(wěn)定點(diǎn)停止或者收斂，即

證 不等式（4）和引理2說明對(duì)?k∈N，有

因此可得βk＞0（?k∈N）.再由引理2，對(duì)?k∈N，有

搜索方向的定義及（6）式保證了

因此，對(duì)?k∈N，有

這確保了（βk＋1）k≥1滿足引理4中的條件.因此算法Ⅰ全局收斂.

2 算法Ⅱ及其收斂性分析

算法Ⅱ

步驟0：選取初始點(diǎn)x1∈RN，給定參數(shù)，容許誤差0＜ε?1，令d1＝－g1，k＝1.

步驟1：給定xk，dk∈RN，由不等式（4），（5）計(jì)算步長αk＞0.由（2）式計(jì)算xk＋1∈RN.

步驟2：若gk＋1＝0，停止.否則轉(zhuǎn)第3步.

步驟3：由（7）式計(jì)算βk＋1∈R，再由（8）計(jì)算搜索方向dk＋1.

步驟4：令k＝k＋1.轉(zhuǎn)到步驟1.

同算法Ⅰ一樣，在給出算法Ⅱ的全局收斂性之前先給出一些假設(shè)與性質(zhì).

假設(shè)2 A3）水平集Γ?RN在初始點(diǎn)有界.

引理5［7］結(jié)合等式（2），（3）的方法，設(shè)γ＞0，且對(duì)任意k∈N，存在，使得γ≤‖gk‖≤.若b＞1，且存在λ＞0，使得｜β｜≤b，且‖s‖≤λ（s＝x－x），則｜β｜≤.kkkk＋1kk

由引理5可以推出如下定理.

定理2 結(jié)合（2），（3）的方法，同時(shí)

i）對(duì)?k∈N，βk≥0；

ii）假設(shè)1和假設(shè)2及引理5都滿足；

iii）（dk）k∈N滿足充分下降條件，則全局收斂到問題（1）的穩(wěn)定點(diǎn)或者至少存在一個(gè)聚點(diǎn)是問題（1）的穩(wěn)定點(diǎn).

定理3 在假設(shè)1和引理5的條件下，設(shè)算法Ⅱ中的（dk）k∈N滿足充分下降條件，則算法Ⅱ在一個(gè)穩(wěn)定點(diǎn)停止或收斂，即

證 由（7）式可知，對(duì)?k∈N，βk≥0，只需證算法滿足引理5即可.

不等式（4），（5）及定理2中的條件確保了?c＞0，使得對(duì)?k∈N，有

另一方面，假設(shè)2確保了?M1，＞0使得‖sk‖≤M1，且‖gk‖≤（k∈N）.因此，有

假設(shè)?M＞0，滿足‖gk＋1‖≥M（k∈N），有，并令.若‖sk‖≤λ（?k∈N），由不等式（9）可知，對(duì)?k∈N，有

這證明引理5是滿足的，因此定理3確保了算法Ⅱ的全局收斂性.

3 討論

除了由（4），（5）定義的線搜索方法以外，還有許多種非精確線搜索方法可以應(yīng)用于這兩種新的共軛梯度算法中，如

其中0＜δ＜σ＜1，0＜γ＜1.

下面將給出使用由（10），（11）定義的線搜索方法的兩種新的共軛梯度算法.

3.1 算法Ⅲ

步驟0：選取初始點(diǎn)x1∈RN，給定參數(shù)0＜δ＜σ＜1，0＜γ＜1，容許誤差0＜ε?1，令d1＝－g1，k＝1.

步驟1：給定xk，dk∈RN，計(jì)算滿足（10），（11）的αk＞0.由（2）式計(jì)算xk＋1∈RN.

步驟2：若gk＋1＝0，停止.否則轉(zhuǎn)第3步.

步驟3：由（6）式計(jì)算βk＋1∈R，由（8）式計(jì)算搜索方向dk＋1.步驟4：令k＝k＋1.轉(zhuǎn)到步驟1.

3.2 算法Ⅳ

步驟0：選取初始點(diǎn)x1∈RN，給定參數(shù)0＜δ＜σ＜1，0＜γ＜1，容許誤差0＜ε?1，令d1＝－g1，k＝1.

步驟1：給定xk，dk∈RN，由不等式（10），（11）計(jì)算步長αk＞0.由（2）式計(jì)算xk＋1∈RN.

步驟2：若gk＋1＝0，停止.否則轉(zhuǎn)第3步.

步驟3：由（7）式計(jì)算βk＋1∈R，再由（8）式計(jì)算搜索方向dk＋1.

步驟4：令k＝k＋1.轉(zhuǎn)到步驟1.

4 數(shù)值試驗(yàn)

分別給出算法Ⅰ，Ⅱ，Ⅲ，Ⅳ的一些數(shù)值試驗(yàn)結(jié)果，比較它們的性能.從CUTE測(cè)試函數(shù)庫中選擇了無約束優(yōu)化問題完成本次試驗(yàn).表1中列出了本次數(shù)值實(shí)驗(yàn)的測(cè)試問題及結(jié)果，其中Problem表示測(cè)試問題的名稱，NI為迭代次數(shù)，NF為函數(shù)值計(jì)算次數(shù)，NG為梯度值計(jì)算次數(shù)，g為最終得到的梯度的范數(shù).所有算法均采用 Matlab編程，在程序中參數(shù)設(shè)置為：ρ＝0.4，δ＝0.5，σ＝0.6，γ＝0.8，且ε＝10－4.

表1 算法Ⅰ，Ⅱ，Ⅲ，Ⅳ的數(shù)值結(jié)果Tab.1 The numerical results of the Algorithm Ⅰ，Ⅱ，Ⅲ，Ⅳ

由表1可知，算法Ⅰ，Ⅱ，Ⅲ，Ⅳ在不同的函數(shù)上性能表現(xiàn)有很大差異.因此，并沒有一種算法適應(yīng)于所有的函數(shù).對(duì)于不同的函數(shù)應(yīng)該進(jìn)行大量的實(shí)驗(yàn)以找出最適合函數(shù)自身的一種或幾種算法.因此，對(duì)于共軛梯度算法進(jìn)行全面的研究是很有必要的.

［1］Yuan Yaxiang.Analysis on the conjugate gradient method［J］.Optim Methods softw，1993，2（1）：19.

［2］Yu Gaohang，Zhao Yalin，Wei Zengxin.A descent nonlinear conjugate gradient method for large－scale unconstrained optimization［J］.Appl Math Comput，2007，187（2）：636.

［3］Dai Yuhong，Yuan Yaxiang.A nonlinear conjugate gradient method with a strong global convergence property［J］.SIAM J Optim，1999，10（1）：177.

［4］Dai Yuhong.Further insight into the convergence of the Fletcher－Reeves method［J］.Sci China：Ser A，1999，42（9）：905.

［5］Du Shouqiang，Chen Yuanyuan.Global convergence of a modified spectral FR conjugate gradient method［J］.Appl Math Comput，2008，202（2）：766.

［6］Hideaki I，Yasushi N.Conjugate gradient methods using value of objective function for unconstrained optimization［J］.Optim Lett，2012，6（5）：914.

［7］Gilbert J C，Nocedal J.Global convergence properties of conjugate gradient method for optimization［J］.SIAM J Optim，1992，2（1）：21.

［8］馬昌鳳.最優(yōu)化方法及其 Matlab程序設(shè)計(jì)［M］.北京：科學(xué)出版社，2010：47.

［9］張秀軍，徐安農(nóng).一種新的非線性共軛梯度法的全局收斂性［J］.廣西科學(xué)，2005，12（4）：283.

［10］李敏，屈愛平.一種充分下降的PRP共軛梯度法的全局收斂性［J］.高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào)，2013，35（2）：148.

［11］Qian Weiyi，Cui Haijuan.A new method with sufficient sescent property for unconstrained optimization［J］.Abstr Appl Anal，to be published.