求解大規(guī)模非線性單調(diào)方程組的修正HS投影算法

王松華，黎勇，黃必昌

(百色學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 百色 533000)

0 引 言

本文考慮如下非線性單調(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投影算法。

1 修正的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。

2 充分下降性和信賴域性質(zhì)

首先證明算法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)的右半部分。

3 全局收斂性分析

假設(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)成立。證畢。

4 數(shù)值試驗

本節(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)行時間比較圖

5 結(jié) 論

(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ī)模非線性問題。