基于Wolfe線搜索的修正共軛梯度算法

林穗華

(廣西民族師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院， 廣西 崇左 532200)

共軛梯度法是1952年由Hestence等[1]作為求解線性方程組的方法而提出，1964年Fletcher等[2]將其推廣用于求解無約束非線性函數(shù)極小值.因具算法存儲量小、收斂速度較快等優(yōu)點，現(xiàn)已成為解決經(jīng)濟(jì)、工程應(yīng)用等領(lǐng)域大型線性方程組和大型無約束非線性優(yōu)化問題的有效方法之一.設(shè)目標(biāo)函數(shù)f:n→連續(xù)可微，求解min{f(x)|x∈n}的共軛梯度法迭代格式為

xk+1=xk+αkdk,

(1)

(2)

其中:xk為第k個迭代點，dk為搜索方向，αk為步長因子，gk=f(xk)，βk為共軛參數(shù).不同的共軛參數(shù)對應(yīng)不同的共軛梯度法.著名的HS(Hestence-Stiefel)、DY(Dai-Yuan)共軛參數(shù)公式如下

其中:yk-1=gk-gk-1，‖·‖為歐氏范數(shù).

HS方法數(shù)值性能較好，但一般非凸目標(biāo)函數(shù)即使采用精確線搜索HS方法也不一定收斂[3]，DY方法收斂性好但數(shù)值表現(xiàn)一般. 為挖掘收斂性質(zhì)和數(shù)值表現(xiàn)好的算法，類似PRP+(Polak-Ribiere-Polyak)方法和HS+方法的思想[3]，文[4-8]從不同角度對經(jīng)典的參數(shù)公式進(jìn)行非負(fù)性修改，如

MHS(modified HS)方法和VMHS(variant MHS)方法均在強(qiáng)Wolfe線搜索條件下收斂且數(shù)值表現(xiàn)良好；MDY(modified DY)方法只需弱Wolfe線搜索條件就能收斂；WC(Wang-Chen)方法不依賴線搜索條件滿足充分下降性，且在假設(shè)條件αk≥α*>0下收斂.論文結(jié)合上述方法的優(yōu)點，考慮新的修正方向調(diào)控參數(shù)，分析算法在弱Wolfe線搜索條件下的收斂性，并用數(shù)值實驗檢驗其有效性.

1 參數(shù)與算法

受文[4-9]啟發(fā)，考慮修正共軛參數(shù)如下

(3)

其中調(diào)比因子

(4)

基于參數(shù)βk，采用弱Wolfe-Powell線搜索WWP(weak Wolfe-Powell)，求解無約束優(yōu)化問題min{f(x)|x∈n}的修正共軛梯度算法如算法1.

算法1

步驟1給定初值x1∈n，δ∈(0,0.5)，σ∈(δ,1)，μ≥1，ε≥0，d1:=-g1，k:=1.若‖gk‖≤ε，停止.

步驟2計算步長αk滿足WWP線搜索準(zhǔn)則

(5)

(6)

步驟3由(1)式計算xk+1.若‖gk+1‖≤ε，停止.

步驟4由(3)、(4)式計算βk+1，由(2)式計算dk+1.

步驟5k:=k+1，轉(zhuǎn)步驟2.

受文[10-13]的啟發(fā)，考慮結(jié)合譜梯度法形式的搜索方向，建立求解min{f(x)|x∈n}的修正譜共軛梯度算法如算法2.

算法2

算法1中步驟4改為：由(3)、(4)式計算共軛參數(shù)βk+1，由下式計算搜索方向dk+1

dk+1=-θk+1gk+1+βk+1dk，

(7)

其中譜參數(shù)

(8)

2 全局收斂性

為證明算法1、2的全局收斂性，對目標(biāo)函數(shù)作如下假設(shè)

(i) 設(shè)水平集Ω={x∈n|f(x)≤f(x1)}有界, 其中x1為初始點.

(ii)f(x)在Ω上連續(xù)可微且導(dǎo)數(shù)滿足Lipschitz條件，即存在常數(shù)L>0，使得

‖g(x)-g(y)‖≤L‖x-y‖，?x,y∈Ω.

論文以下算法的收斂性分析中均假設(shè)‖gk‖≠0，否則目標(biāo)函數(shù)的穩(wěn)定點已獲得，算法自動終止.

引理1算法1產(chǎn)生的搜索方向序列{dk}滿足下降性：?k≥1，有

(9)

證明由Cauchy-Schwarz 不等式可知

(10)

當(dāng)k=1時,

(11)

結(jié)合(3)、(4)式可得βk≥0.

(12)

(13)

結(jié)合(10)～(12)式可得

(14)

綜上，由數(shù)學(xué)歸納法，引理1得證.由引理1的證明過程可得引理2.

引理2設(shè){βk}為算法1產(chǎn)生的共軛參數(shù)序列，則?k>1，有

(15)

由引理1及文[3]引理1.4.1,可得引理3.

‖gk‖≥r, ?k≥1.

(16)

由(2)式可得dk+gk=βkdk-1，兩邊取模平方，并移項可得

(17)

由(17)式遞推，并結(jié)合(16)式可得

從而可得

這與引理3矛盾，由反證法知定理1得證.

引理4設(shè){dk,βk}為算法2產(chǎn)生的序列,則?k≥1，有

(18)

則

(19)

(20)

由歸納法知,?

引理4說明算法2產(chǎn)生的搜索方向dk滿足下降性.根據(jù)文[3]引理1.4.1,易得引理5.

證明由(7)式可得dk+θkgk=βkdk-1，兩邊取模平方，并移項可得

類似定理1，用反證法可得定理2結(jié)論.

3 數(shù)值實驗

為測試論文提出的修正HS共軛梯度算法的有效性,用文[14]的測試函數(shù)進(jìn)行數(shù)值實驗，結(jié)果如表1所示.其中NI(number of iterations)表示算法迭代次數(shù),time表示CPU時間(單位：s),目標(biāo)函數(shù)為ROSE(Rosenbrock)、FROTH(Freudenstein and Roth)、BADSCP(Powell badly scaled)、JENSAM(Jennrich and Sampson)、HELIX(helical valley)、GULF(Gulf research and development)、SING(Powell singular)、WOOD、KOWOSB(Kowalik and Osborne)、BIGGS(biggs EXP6)、OSB2(Osborne 2)、ROSEX(extended Rosenbrock)、SINGX(extended Powell singular)、PEN1(penalty I)、PEN2(penalty II)、VARDIM(variably dimensioned)、TRIG(trigonometric)、BV(discrete boundary value)、IE(discrete integral equation)、TRID(Broyden tridiagonal)、BAND(Broyden banded)、LIN(linear-full rank) 、LIN1(linear-rank 1)、LIN0(linear-rank 1 with zero cols. & rows). 算法運行環(huán)境為Windows7+Matlab2011b. 算法Wolfe線搜索參數(shù)為δ=0.1，σ=0.9，終止條件為‖gk‖≤10-6，或迭代次數(shù)超過9 999.圖1為迭代次數(shù)比較.圖2為CPU時間比較.

表1 數(shù)值實驗結(jié)果

續(xù)表1

圖1 迭代次數(shù)比較 圖2 CPU時間比較

參考文獻(xiàn)：

[1] HESTENES M R, STIEFEL E L. Methods of conjugate gradients for solving linear systems[J]. J Res Nat Bur Standards, 1952, 49 (6): 409-436.

[2] FLETCHER R, REEVES C. Function minimization by conjugate gradients[J]. Comput J, 1964, 7 (2): 149-154.

[3] 戴彧虹, 袁亞湘. 非線性共軛梯度法[M]. 上海: 上海科學(xué)技術(shù)出版社, 2001: 30-51.

[4] YAO S W, WEI Z X, HUANG H. A note about WYL’s conjugate gradient method and its application[J]. Appl Math Comput, 2007, 183 (1): 1341-1350.

[5] DU X W, ZHANG P, MA W Y. Some modified conjugate gradient methods for unconstrained optimization[J]. J Comput Appl Math, 2016, 305: 92-114.

[6] 黃海. 非線性無約束優(yōu)化問題的新共軛梯度法[J]. 河南大學(xué)學(xué)報 (自然科學(xué)版), 2014, 44 (2): 141-145.

[7] 王安平, 陳忠. Wolfe線搜索下一種修正的HS共軛梯度法及其全局收斂性[J]. 安徽大學(xué)學(xué)報 (自然科學(xué)版), 2015, 39 (4): 16-19.

[8] 李燦. 一種修正PRP共軛梯度法的全局收斂性[J]. 安徽大學(xué)學(xué)報 (自然科學(xué)版), 2013, 37 (2): 41-44.

[9] JIANG X Z, JIAN J B. Two modified nonlinear conjugate gradient methods with disturbance fators for unconstrained optimization[J]. Nonlinear Dyn, 2014, 77 (1/2): 387-394.

[10] 賽·鬧爾再, 吳曉云. 譜Hestenes-Stiefel共軛梯度算法及其收斂性[J]. 數(shù)學(xué)的實踐與認(rèn)識, 2015, 45 (18): 261-270.

[11] 林穗華, 黃海. 一個新的譜共軛梯度法[J]. 工程數(shù)學(xué)學(xué)報, 2014, 31 (6): 837-846.

[12] 林穗華. Wolfe線搜索下的修正FR譜共軛梯度法[J]. 山東大學(xué)學(xué)報 (理學(xué)版), 2017, 52 (4): 6-12.

[13] ZHANG Y, DAN B. An efficient adaptive scaling parameter for the spectral conjugate gradient method[J]. Optim Lett, 2016, 10: 119-136.