求解非線性方程組的修正Fletcher-Reeves共軛梯度法

黎勇,羅丹,王松華

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

1.引言

考慮如下非線性方程組問題:

式中g: Rn →Rn連續(xù)可微.非線性方程組問題在壓縮感知[1],以及化學平衡、經(jīng)濟平衡、電力系統(tǒng)領域等實際工程問題上有著較強的應用背景[2],一直得到了廣泛的研究,出現(xiàn)了牛頓算法、擬牛頓算法、高斯牛頓算法等收斂性理論較好的算法.然后這些算法普遍因為存儲量大、算法較為復雜等因素限制,不適合求解大規(guī)模非線性方程組問題.共軛梯度算法存儲量需求小、算法結構簡單,是求解大規(guī)模無約束優(yōu)化問題最有效的算法之一,近年來被推廣到大規(guī)模非線性方程組問題,并成為最優(yōu)化領域研究的一個熱點[3?7].令f(x)=是歐幾里得范數(shù),則問題(1.1)與式(1.2)等價,非線性方程組問題(1.1)轉化為如下無約束優(yōu)化問題:

求解無約束優(yōu)化問題(1.2)的共軛梯度法迭代公式如下:

式中dk是搜索方向,αk是搜索步長,βk+1是控制參數(shù),不同的控制參數(shù)βk+1對應不同的共軛梯度法.FR算法[8]、PRP算法[9]和HS算法[10]等經(jīng)典共軛梯度法已廣泛被人們所熟知,其中FR方法的控制參數(shù)公式如下:

FR算法收斂性質較好,但因為可能會連續(xù)產(chǎn)生小步長而導致數(shù)值表現(xiàn)一般[8].PRP算法和HS算法數(shù)值表現(xiàn)較好的一個原因之一,是其搜索方向dk能夠自動靠近負梯度方向[9?10],克服了FR算法的不足.因此,從PRP算法或HS算法中尋找更有效的FR方法的修正技術,理論上是有可能的.

在非精確線搜索分析中,設計具有不依賴任何線搜索自動滿足充分下降條件[11?13]和信賴域性質[14?15]的搜索方向,所構建算法在更溫和的條件下的全局收斂理論性質更好,數(shù)值結果表現(xiàn)更優(yōu).所謂的充分下降條件是:=?c‖gk‖2,?k ∈N,c <0,信賴域性質是‖dk‖≤?c0‖gk‖,?k ∈N,c0>0.近來,一類具有自動滿足充分下降條件的共軛梯度算法,有效求解了非線性方程組問題[16?18].其中,文[16]提出了一類新型的無導數(shù)PRP共軛梯度算法,其搜索方向公式為:

式中:δk=gk+1?gk,γ >0.該算法保持了文[16]自動滿足充分下降條件的性質,還克服了文[16]不具有的信賴域性質的不足,其搜索方向公式更為簡便,算法效果更好.文[18]也有類似的思想,所設計的算法收斂性更快,數(shù)值結果更好.文[17-18]不僅能有效求解問題(1.1),特別在大規(guī)模優(yōu)化問題上,效率更好.

基于以上討論,本文在經(jīng)典FR算法的基礎提出一種新的搜索方向,結合超平面投影技術和文[18]的經(jīng)典線搜索,設計一類針對非線性方程組的修正FR算法.研究表明該算法不僅自動滿足充分下降條件,而且搜索方向具有信賴域性質,在一定條件下所提出的方法全局收斂.初步的數(shù)值實驗也表明修正FR算法在求解非線性方程組方面更加高效.

2.MFR算法(Modified Fletcher-Reeves Method)

本節(jié)結合文獻[17,18]的技術,在經(jīng)典FR方法的基礎上,設計一個新的搜索方向如下:

式中: 常數(shù)μ1>0,μ2>0.顯然,在精確線搜索條件下,當目標函數(shù)為嚴格凸二次函數(shù)時,(2.1)式退化為經(jīng)典FR方法.

為便于表述,本文將修正FR算法簡稱為MFR算法,其步驟如下:

算法1(MFR算法)

步0 給定初始點x0∈Rn.ε ∈(0,1),μ1>0,μ2>0,σ >0.令k:=0.

步1 若‖g(xk)‖<ε則停止;否則轉步2.

步2 利用式(2.1)計算搜索方向dk.

步3 利用文[18]計算步長αk:

其中αk=max{s,λs,λ2s,···},σ >0,s>0,λ ∈(0,1).

步4 令迭代公式為zk=xk+αkdk.

步5 若‖g(zk)‖≤ε則停止,并令xk+1=zk;否則下一個迭代點xk+1取xk在超平面Hk=上的投影[19]:

步6 令k:=k+1,轉步1.

3.全局收斂性

假設A非線性方程組問題(1.1)的解集是非空集合,水平集?={x∈Rn:f(x)≤f(x1)}有界.

假設B映射g在Rn →Rn上Lipschitz連續(xù),即存在L>0,使得

由以上假設容易推出存在一個常數(shù)ξ >0,使得

引理3.1若搜索方向dk滿足式(2.1),則下列性質成立:

證當k=0時,式(3.2)、式(3.3)顯然成立.當k ≥1時,由式(2.1)有

即式(3.2)成立.因此由Cauchy-Schwartz不等式得

故式(3.3)左邊不等式成立.

另一方面,式(2.1)兩邊同取范數(shù),并再次利用Cauchy-Schwartz不等式得

綜上所述,(3.3)式得證.證畢.

引理3.2[19]令假設A、B成立,序列{xk}由MFR算法產(chǎn)生,若x?是非線性方程組(1.3)的解,即g(x?)=0,則

成立.

以上引理及其證明詳見文[19].

引理3.3若假設A、B成立,則MFR算法經(jīng)有限次回溯后必產(chǎn)生迭代xk+1=xk+αkdk,即MFR算法有意義.

證反證法.假設MFR算法不停止或者‖gk‖→0不成立,則存在常數(shù)η >0,使得

下面證明: 線搜索(2.2)能保證獲得一個正的步長,使之在有限步內終止,即證明滿足線搜索(2.2)的步長αk有下界.利用反證法,假設存在k′使(2.2)不成立,則對?m ∈N∪{0},令,有

由假設B和式(3.2)有

而根據(jù)式(3.1)、式(3.3),有

由式(3.3)、式(3.5)、式(3.6)得

根據(jù)以上三個引理,下面證明MFR算法在一般條件下全局收斂.

定理3.1設序列{αk,dk,xk+1,gk+1}由MFR算法產(chǎn)生,假設A,B成立,則

證反證法.假設式(3.7)不成立,則式(3.4)成立,故由式(3.3)有

因為由引理3.2中序列{xk}的有界性知道,必存在一個聚點和無限指數(shù)集N1,使

同理由式(3.1)、式(3.3)得到

也說明序列{dk}有界,因此也必存在一個聚點和無限指數(shù)集N2?N1,使

另外由引理3.2和引理3.3容易知道

因此

因為根據(jù)式(2.2)不難得到

當k →∞時,對所有k ∈N2,式(3.10)兩邊同取極限得

而當k →∞時,對所有k ∈N2,式(3.2)兩邊同取極限得

4.數(shù)值試驗

為了驗證MFR算法求解非線性方程組的有效性,下面將對表1中的測試問題進行數(shù)值實驗,所選測試問題來自文[20-21].每個測試函數(shù)取[500,1000,3000,5000]等4種維數(shù)情形,并從迭代次數(shù)(NI)、函數(shù)值計算次數(shù)(NG)、算法終止時函數(shù)的范數(shù)值(GN)、實驗所需時間(CPU time)等幾方面將MFR算法的實驗結果與傳統(tǒng)FR方法的實驗結果進行比較.

數(shù)值試驗是在Win 7.Pentium Dual E5800 3.20GHz,內存2.0G的PC機上進行的,測試代碼利用Matlab R2010b編寫,各參數(shù)取值如下:μ1=0.99,μ2=0.01,ε=10?5,終止條件為‖g(x)‖≤10?5或者NI≥1000.表4.1列出了數(shù)值實驗結果,表4.2列出6個測試問題的名稱和初始點.

表4.1 數(shù)值結果

表4.2 測試問題

為了更加直觀地比較兩種算法對以上測試問題的數(shù)值表現(xiàn),根據(jù)Dolan和Mo′re在文[22]中提出的評價方法,利用Matlab編寫程序得到以下三個數(shù)值實驗結果的比較圖像:

圖4.1 MFR算法與FR算法的NI性能比較

圖4.2 MFR算法與FR算法的NG性能比較

圖4.3 MFR算法與FR算法的CPU time性能比較

從圖4.1-4.3,容易直觀看出,無論是迭代次數(shù)、函數(shù)值計算次數(shù),還是實驗所需時間,代表MFR算法的曲線基本上都在代表傳統(tǒng)FR算法的曲線上方,這表明MFR算法求解問題的成功概率更大,而且魯棒性更強,穩(wěn)定性更高.針對這本次的6個測試問題,兩類算法是有效的,MFR算法總體效能優(yōu)于FR方法.

5.結語

本文提出一種求解非線性方程組問題的MFR算法,該算法具有自動滿足充分下降條件和信賴域性質的特點,具有很好的收斂性質;數(shù)值結果表明,MFR算法比經(jīng)典FR算法更高效.未來我們將加大數(shù)值實驗測試問題的個數(shù)和維數(shù),如10個以上測試問題,每個問題的維數(shù)設定到5萬維以上,進一步驗證MFR算法的穩(wěn)健性和有效性.同時,嘗試將MFR算法推廣到壓縮感知等實際工程問題中,推廣MFR算法的應用價值.