王松華,黎勇,黃必昌
(百色學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,廣西 百色 533000)
本文考慮如下非線性單調(diào)方程組
F(x)=0,x∈Rn,
(1)
其中函數(shù)F是連續(xù)可微且單調(diào)的,對?x,y∈Rn,有
〈F(x)-F(y),x-y〉≥0。
(2)
minQ(x),x∈Rn,
(3)
一般地,好的共軛梯度法取決于好的共軛梯度方向和一個非精確線搜索技術(shù)。搜索方向在很大程度上決定了搜索效率,而搜索方向的充分下降和信賴域性質(zhì)對共軛梯度法的全局收斂性起到積極作用[7-8]。M.V.Solodov等[9]提出將投影技術(shù)應(yīng)用于大型非線性方程,取得了有效成果。目前,結(jié)合投影技術(shù),將共軛梯度法應(yīng)用到大規(guī)模非線性方程組成為最優(yōu)化領(lǐng)域研究的一個熱點(diǎn)[10-14]。同時,針對單調(diào)非線性問題,文獻(xiàn)[15]給出著名的線搜索技術(shù),能有效解決非線性大規(guī)模問題,其公式為
(4)
其中αk=max{s,ρs,ρ2s,…},σ>0,s>0,ρ∈(0,1)。
本文在文獻(xiàn)[5]的基礎(chǔ)上,設(shè)計一個新的搜索方向,采用M.V.Solodov等[9]的投影技術(shù),結(jié)合文獻(xiàn)[15]線搜索方法,提出一個求解大規(guī)模非線性單調(diào)方程組的修正HS投影算法。
共軛梯度法迭代公式的一般形式為
xk+1=xk+αkdk,
(5)
式中:xk為當(dāng)前迭代點(diǎn);xk+1為下一個迭代點(diǎn);αk為步長,由某種線搜索確定;dk為搜索方向,迭代公式定義為
(6)
其中,βk為一個共軛參數(shù),F(xiàn)k為F(xk)的簡寫。
令zk=xk+αkdk,有F(zk)T(x-zk)>0。如果對某個點(diǎn)x*滿足f(x*)=0,由函數(shù)F的單調(diào)性質(zhì)有F(zk)T(x-zk)≤0。則通過超平面
Hk={x∈Rn|F(zk)T(x-zk)=0}
嚴(yán)格將當(dāng)前迭代點(diǎn)xk從式(1)的解中分離出來,M.V.Solodovy等[9]建議將當(dāng)前點(diǎn)xk投影到超平面Hk方便確定下一個迭代點(diǎn),即
(7)
式(7)是有效的,不僅得到了較好的數(shù)值結(jié)果,而且具有較好的理論性質(zhì)。
針對大規(guī)模無約束優(yōu)化問題,經(jīng)典共軛梯度法有PRP、HS、FR、CD、DY和LS等[16]。經(jīng)典的PRP方法、HS方法和LS方法在數(shù)值結(jié)果表現(xiàn)上非常有效,但是其全局收斂性并不令人滿意。文獻(xiàn)[5]在文獻(xiàn)[17]的基礎(chǔ)上修正了βPRP公式,該公式具有充分下降性,在標(biāo)準(zhǔn)WWP線搜索上算法全局收斂,數(shù)值結(jié)果良好,但該βPRP公式不具有信賴域性質(zhì)。同時文獻(xiàn)[5]給出了修正βHS公式,并給出了相應(yīng)算法的初步數(shù)值試驗結(jié)果和分析,但是沒有證明該算法的充分下降性和全局收斂性。修正βHS公式[5]定義為
受此啟發(fā),本文在文獻(xiàn)[5]的基礎(chǔ)上,結(jié)合文獻(xiàn)[7]和[14]關(guān)于共軛參數(shù)的修正方法,設(shè)計一個新的搜索方向dk+1,
dk+1=
(8)
其中,μ>1/4,λ≥2,γ≥2。
算法1
步驟3 采用線搜索式(4)計算步長αk;通過式(8)計算搜索方向dk。
步驟4 令迭代公式為zk=xk+αkdk。
步驟6 令k:=k+1,轉(zhuǎn)步驟2。
首先證明算法1的搜索方向dk具有充分下降和信賴域性質(zhì)。
引理1 搜索方向dk由式(8)定義,則存在c2>c1>0,使得下式成立:
(9)
(10)
首先證明不等式(9)成立。
證明k=0時,不等式(9)成立。以下證明k≥1時,不等式(9)成立。
根據(jù)式(8),結(jié)合范數(shù)性質(zhì),得到
由式(9)可直接推導(dǎo)出式(10)的左半部分,下面證明式(10)的右半部分。
假設(shè)1
(1)式(1)的解集非空,且水平集Ω={x∈Rn:F(x)≤F(x1)}有界。
(2)函數(shù)F:Rn→Rn是Lipschitz連續(xù)的,即?L>0,使得
(11)
即存在一個常數(shù)?=2ωL>0,使得
(12)
以下給出引理2和引理3。引理2說明線搜索能夠保證得到一個正數(shù)步長,使得算法1在有限步內(nèi)停止,從而說明提出的算法1是有意義的。
引理2 若假設(shè)(1)和假設(shè)(2)成立,則MMHS算法有意義。
證明假設(shè)不成立,或者M(jìn)LS算法不停止,那么,使得
‖gk‖≥η,?k∈N∪{0}。
(13)
下面證明滿足式(4)的步長αk存在下界。
由式(9)和假設(shè)1的(2)有
(14)
由式(10)和式(12)可得
(15)
結(jié)合式(10)、(14)和(15),可得
引理3 如果假設(shè)1成立,且{xk}是由MHS算法生成。設(shè)x*是式(1)的解,則有
(17)
成立。
證明因為F是單調(diào)的,x*是式(1)的解,結(jié)合超平面Hk的定義,得到
〈F(zk)-F(x*),x*-zk〉=
〈F(zk),x*-zk〉≤0,
(18)
容易驗證xk+1是xk在半平面Mk={x∈Rn|〈F(zk)T,x-zk〉≤0}上的投影。如果x*處在半平面Mk空間里,根據(jù)投影算子基本性質(zhì),得到〈xk-xk+1,xk+1-x*〉≥0。則有
由此得出式(16)成立。
再將式(16)移項,整理得
將上式累加,令k→+∞,推出式(17)成立。
由式(4)和(7),可得
聯(lián)合式(17),可得到
因此,有
(19)
由引理1、引理2和引理3,結(jié)合假設(shè)1和式(19),利用反證法,可以得到算法1全局收斂性的結(jié)論。
(20)
成立。
證明采用反證法。假設(shè)式(20)不成立,則存在一個常數(shù)ν>0,使
由式(12),有
(21)
根據(jù)式(10)和(15)得到
聯(lián)合式(19),可得
當(dāng)k→∞時,對?k∈N2,上式兩邊取極限,即有
而式(11)兩邊同取極限,得到
顯然矛盾。所以假設(shè)不成立,即式(20)成立。證畢。
本節(jié)通過對算法1與經(jīng)典HS、三項HS算法在求解大規(guī)模非線性單調(diào)方程組問題上進(jìn)行數(shù)值試驗和比較分析,檢驗算法1的有效性。在算法1的步驟3中,分別使用式(22)和式(23)替代搜索方向dk,其他步驟和算法1的步驟一致,則對應(yīng)為經(jīng)典HS算法和三項HS算法,在文中分別稱之為算法2和算法3。
其中yk=Fk+1-Fk。
具有固定初始點(diǎn)的函數(shù)來自于文獻(xiàn)[7,14],具體的函數(shù)名稱與初始點(diǎn),如表1所示。
表1 測試函數(shù)
表2 數(shù)值計算結(jié)果
續(xù)表2
從表2可以看出,在精度相同條件下,NI、NF和CPU運(yùn)行時間3個測試指標(biāo)中,算法1最好,算法2其次,算法3最差。為直觀反映3種算法的性能差異,本文采用文獻(xiàn)[17]的曲線分析比較方法,分別作出3種算法關(guān)于NI、NF和CPU運(yùn)行時間的曲線比較圖,見圖1~3。由圖1~3可知,總體上算法1比算法2和算法3更優(yōu),魯棒性更好,是一種有效的算法。
圖1 迭代次數(shù)比較圖
圖2 目標(biāo)函數(shù)值計算次數(shù)比較圖
圖3 CPU運(yùn)行時間比較圖
(1)修正的HS投影算法不僅繼承了YUAN搜索方向自動充分下降的特點(diǎn),而且還具有信賴
域的性質(zhì),使得本文所提算法對一般函數(shù)的全局收斂性變得更為容易。
(2)測試問題的最大維數(shù)有45 000個變量,數(shù)值計算結(jié)果表明,對給定的測試函數(shù),本文提出的算法比經(jīng)典HS方法和3項HS方法魯棒性更優(yōu)、更具有競爭力。未來將進(jìn)行更多的試驗證明所提出算法的性能,并嘗試將算法進(jìn)一步推廣到實際的大規(guī)模非線性問題。