一種新型線搜索下的修正3項(xiàng)LS譜共軛梯度法

王松華，黎 勇*，吳加其

(1.百色學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣西 百色 533000;2.廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧 530004)

考慮求解無約束優(yōu)化問題

min{f(x)|x∈Rn}，

(1)

其中：目標(biāo)函數(shù)f(x):Rn→R連續(xù)可微.非線性共軛梯度法計(jì)算僅用到目標(biāo)函數(shù)的一階導(dǎo)數(shù)信息，具有算法簡(jiǎn)便、存儲(chǔ)量小的優(yōu)點(diǎn)，同時(shí)避免了最速下降法整體收斂速度慢、牛頓法及擬牛頓法需要存儲(chǔ)矩陣以及在計(jì)算搜索方向時(shí)需要求解線性方程組等問題，是求解大規(guī)模無約束優(yōu)化問題最常用也是最高效的方法之一.非線性共軛梯度法的迭代公式為

xk+1=xk+αkdk.

(2)

線搜索型共軛梯度法的每步迭代主要由具有某種性質(zhì)的搜索方向dk和滿足某種線搜索的步長(zhǎng)因子αk兩個(gè)部分組成.搜索方向dk的迭代公式為

(3)

其中：gk表示目標(biāo)函數(shù)f(x)在xk點(diǎn)的梯度函數(shù)f(xk)，βk∈R是搜索方向dk的共軛參數(shù).不同的參數(shù)βk對(duì)應(yīng)著不一樣的共軛梯度法，經(jīng)典的參數(shù)βk公式有：和相應(yīng)的共軛梯度法分別稱為FR(fletcher-reeves)、PRP(polak-Ribière-polyak)、HS(hestenes-stiefel)、CD(conjugatedescent method)和LS(Liu-Storey)方法[1].這些方法在一些線搜索下的全局收斂性和數(shù)值性能已經(jīng)得到廣泛研究.經(jīng)典的LS方法共軛參數(shù)公式為

其中：yk-1=gk-gk-1.

搜索方向是否滿足下降性或者充分下降性是線搜索型共軛梯度法全局收斂的重要條件.為此，有效調(diào)整搜索方向結(jié)構(gòu)成為非線性共軛梯度法的一類重要的研究途徑，這也推進(jìn)了非線性譜共軛梯度法[2-4]和3項(xiàng)共軛梯度法[5-10]的研究.譜共軛梯度法的搜索方向在共軛梯度法的基礎(chǔ)上增加了一個(gè)由某一種預(yù)設(shè)條件確定的譜參數(shù)θk，迭代公式為d0=-g0，dk=-θkgk+βkdk-1.文獻(xiàn)[5-7]通過對(duì)參數(shù)進(jìn)行調(diào)整來獲得充分下降條件，創(chuàng)新了3項(xiàng)共軛梯度法.近來關(guān)于充分下降型的3項(xiàng)共軛梯度法的研究，均取得了很好的成果[8-10].

Zhang等[5]給出充分下降型3項(xiàng)PRP方法的搜索方向公式為

目前，3項(xiàng)譜共軛梯度法成為一類求解大規(guī)模無約束優(yōu)化問題的研究熱點(diǎn)[11-12].文獻(xiàn)[12]提出的3項(xiàng)PRP共軛梯度法，搜索方向不依賴線搜索，具有充分下降性，且在給定的線搜索下具有全局收斂性.其搜索方向公式為

(4)

其中：yk-1=gk-gk-1.

相對(duì)于3項(xiàng)PRP和HS譜共軛梯度法的研究而言，3項(xiàng)LS譜共軛梯度法成果較少.為推廣LS共軛梯度法，根據(jù)文獻(xiàn)[12]的公式(4)，論文提出一個(gè)修正3項(xiàng)LS公式為

(5)

步長(zhǎng)因子αk在實(shí)際計(jì)算中經(jīng)常使用Wolfe、強(qiáng)Wolfe、Armijo、Armijo-Goldstein和Armijo-type等非精確線搜索來計(jì)算.2017年，文獻(xiàn)[13]針對(duì)傳統(tǒng)PRP方法提出了一種修正Wolfe線搜索(論文簡(jiǎn)稱YWL(YUAN Gonglin, WEI Zengxin, LIU Xinwen)型線搜索).初步的數(shù)值實(shí)驗(yàn)結(jié)果表明，該線搜索在適當(dāng)?shù)臈l件下更具有競(jìng)爭(zhēng)性.其線搜索公式為

(6)

和

(7)

其中：δ∈(0,1/2)，δ1∈(0,δ)，σ∈(δ,1).

基于以上討論，論文將對(duì)3項(xiàng)LS譜共軛梯度法做進(jìn)一步討論.采用所提搜索方向式(5)，結(jié)合YWL型線搜索式(6)，(7)，設(shè)計(jì)一種修正3項(xiàng)LS譜共軛梯度法，在適當(dāng)條件下證明新算法的全局收斂性，并對(duì)新算法進(jìn)行初步的數(shù)值實(shí)驗(yàn).論文中fk=f(xk)，gk-1=g(xk-1)，gk=g(xk).

1 算法及一般性假設(shè)

為便于表述，論文將新算法稱為算法1，其相關(guān)步驟說明如下：

步驟2 如果‖gk‖≤ε，算法將停止；

步驟3 使用YWL線搜索(6)，(7)，計(jì)算αk；

步驟4 令xk+1=xk+αkdk；

步驟5 如果‖gk+1‖≤ε成立，則算法停止；

步驟6 通過式(5)計(jì)算搜索方向；

步驟7 令k:=k+1，轉(zhuǎn)到步驟3.

算法1的全局收斂性的證明需要一般性假設(shè)A.

假設(shè)A

(i) 定義的水平集L0={x|f(x)≤f(x0)}是有界的；

(ii) 目標(biāo)函數(shù)f(x)有下界，二次連續(xù)可微，且其梯度函數(shù)g(x)是Lipschitz連續(xù)的，則存在常數(shù)L>0，使得以下不等式成立

‖g(x)-g(y)‖≤L‖x-y‖,x,y∈Rn.

(8)

2 充分下降性和全局收斂性分析

引理1搜索方向dk由式(5)給出，則具有以下性質(zhì)

(9)

其中：η≥1是常數(shù).

(10)

引理1說明算法1的搜索方向dk不依賴線搜索，且搜索具有充分下降性.結(jié)合前面給出的一般性假設(shè)和引理1，分析算法1的全局收斂性.

定理1若假設(shè)A成立，如果當(dāng)常數(shù)c>0時(shí)，有‖dk‖≤c‖gk‖成立，則

(11)

證明根據(jù)線搜索的式(7)和引理1的式(9)，可得

再通過假設(shè)A的式(8)，推導(dǎo)出

(12)

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

為考查論文提出的算法1的數(shù)值表現(xiàn)，將對(duì)算法1與傳統(tǒng)3項(xiàng)LS算法和兩項(xiàng)LS算法在無約束優(yōu)化計(jì)算方面進(jìn)行數(shù)值實(shí)驗(yàn)和比較.在算法1的步驟4中，分別使用式(13)，(14)替代搜索方向dk，其他步驟和算法1的步驟一致，則對(duì)應(yīng)的傳統(tǒng)3項(xiàng)LS算法[5]和LS算法[1]，論文稱之為算法2和算法3.

(13)

(14)

該次數(shù)值實(shí)驗(yàn)測(cè)試的程序由Matlab R 2014a編寫和運(yùn)行，計(jì)算機(jī)配置為：Windows 7操作系統(tǒng)，Intel(R)Xeon(R)CPU，E5507 @ 2.27GHz，內(nèi)存2.00GB.試驗(yàn)選取文獻(xiàn)[14]中共33個(gè)非線性函數(shù)進(jìn)行測(cè)試；終止條件為‖gk‖≤10-5或者迭代次數(shù)小于800；3種算法相應(yīng)的參數(shù)設(shè)置為δ=0.4,δ1=0.36,σ=0.48,η1=0.91,η2=0.63,ε=10-5；維數(shù)范圍為[900，1 500，4 500，9 000].針對(duì)迭代次數(shù)、函數(shù)值的計(jì)算次數(shù)和試驗(yàn)運(yùn)行所需要的時(shí)間等這3個(gè)常用指標(biāo)進(jìn)行測(cè)試.

限于篇幅，論文省略了所選的33個(gè)測(cè)試問題的具體名稱和初步的數(shù)值結(jié)果，直接引用文獻(xiàn)[15]的分析方法，分別畫出了3種算法的迭代次數(shù)、函數(shù)值的計(jì)算次數(shù)和實(shí)驗(yàn)運(yùn)行所需要的時(shí)間比較圖，直觀體現(xiàn)出3種算法的性能差異，如圖1所示.

從圖1可以看出，在計(jì)算精度相同的情況下，算法1計(jì)算出的結(jié)果在迭代次數(shù)、函數(shù)值次數(shù)和計(jì)算機(jī)實(shí)驗(yàn)運(yùn)行時(shí)間等方面明顯優(yōu)于算法2，3.新算法能夠有效解決無約束優(yōu)化問題，且數(shù)值表現(xiàn)要明顯優(yōu)于傳統(tǒng)的兩個(gè)算法，是一種有效的方法.