基于凸組合技術的加速FR型共軛梯度算法*

李丹丹，王松華

(1.廣州華商學院應用數學系，廣東廣州 511300；2.百色學院數學與統計學院，廣西百色 533000)

0 引言

在振動系統、潮流方程等科學與工程計算領域存在許多大規模優化問題[1,2]，而這些優化問題往往能夠轉化為非線性方程組問題。因此，研究求解大規模非線性方程組的高效數值算法具有重要的理論價值與實際意義。

本文主要考慮以下非線性方程組問題：

F(x)=0,x∈Rn，

(1)

minf(x),x∈Rn。

近年來，求解上述優化問題的常見算法有牛頓法、信賴域法、擬牛頓法、Levenberg-Marquardt算法及其各種變形[3-8]。在選擇合理初始點的前提下，上述算法對于小規模優化問題具有快速收斂和數值效果良好等特點，但在迭代過程中，需要計算和存儲相關矩陣信息，給求解大規模優化問題帶來一定的局限性。為建立求解大規模優化問題的高效算法體系，研究者提出具有算法簡單、計算和存儲量低等優點的共軛梯度法[9-11]。

經典共軛梯度法的一般迭代公式為

xk+1=xk+αkdk，k=0,1,2,...,

其中αk為由某種線搜索所決定的步長。搜索方向dk為

其中,βk為共軛參數，Fk為F(xk)的簡寫。

本文基于Abubakar等[12]提出的修正FR搜索方向，借鑒Yuan等[13]的凸組合思想，構造凸組合系數如下：

同時，采用Andrei[14]的加速線搜索技術，提出一個求解大規模非線性方程組問題的加速FR型共軛梯度算法。

1 算法描述與性質

本節主要討論搜索方向的構建并介紹線搜索技術，同時提出凸組合修正共軛梯度算法。

首先，Abubakar等[12]在2019年提出一種修正FR共軛梯度法，其搜索方向為

dk=

其中，ωk-1=xk-xk-1,μ>0。該搜索方向具備充分下降性和信賴域特征，能有效求解大規模無約束優化問題。基于Yuan等[13]的凸組合思想，本文構建一個新型的凸組合搜索方向：

(2)

其次，本文通過下述方法計算步長αk=rmk，使得mk滿足下式的最小非負整數，即

(3)

其中，σ∈(0,1),r∈(0,1)。Andrei[14]研究表明，合理地應用加速線搜索，將有效提高算法的計算效率。于是借鑒于Andrei[14]的加速線搜索技術思想，對步長αk做出修正，即

最后，建立求解非線性方程組問題(1)的凸組合加速FR型共軛梯度算法(MMFR)。

步驟1：給定初始點x0∈Rn，參數ε,σ,r,β,μ∈(0,1)，令k:=0；

步驟2：若‖Fk‖≤ε，則算法停止；

步驟3：通過式(2)計算搜索方向dk；

步驟4：若‖F(xk+dk)‖≤β‖Fk‖，則令步長αk=1，轉步驟6，否則轉步驟5；

步驟5：通過式(3)決定步長αk；

步驟7：(更新步)更新新的迭代點xk+1=xk+αkdk，令k:=k+1，轉步驟2。

為后續證明算法的全局收斂性質，下面分析搜索方向dk的兩個重要性質：充分下降性和信賴域特性。

引理1算法MMFR產生的序列{dk}和{Fk}滿足以下性質：

(4)

及

‖dk‖≤τk‖Fk‖，

(5)

-Nk‖Fk‖2。

此外，由式(2)和Cauchy-Schwartz不等式可知

‖dk‖=‖-NkFk+(1-Nk)·

Nk‖Fk‖+(1-Nk)·

綜上所述，式(4)和式(5)成立,引理1得證。

2 全局收斂性分析

為進一步分析算法MMFR的收斂性，本節做如下假設：

假設H

(H1)函數F(x)在開凸集Ω1?Ω=

{x|‖F(x)‖≤‖F(x0)‖}是連續可微的；

(H2)函數F(x)的雅可比矩陣為?F(x)是有界的且為對稱正定矩陣，即存在正常數ξ1≥ξ2>0，使得有‖?F(x)‖≤ξ1和ξ2‖p‖2≤pT?F(x)

p≤ξ1‖p‖2,p∈Rn。

證明：由Brown等[15]的引理3.8可得

由引理1和式(3)可推出

(6)

這說明函數f(x)沿著下降方向dk是充分下降的。公式(6)結合f(x) 的定義可知，對于任意的k，都有‖Fk+1‖≤‖Fk‖。此外，由式(3)和式(4)得出

由假設H1中函數的有界性，再結合上式得

αkdk)<∞，

下面給出算法MMFR的全局收斂性定理。

(7)

假設結論不成立，即存在正整數ξ，對于任意k，那么有

‖?f(xk)‖>ξ。

(8)

另外，由假設H1可知，集合為有界集合，則序列{xk}是有界的，于是可得序列{dk}也是有界的。不失一般性，設點x*和d*分別為序列{xk}和{dk}的聚點。因此，對式(7)取極限得

?f(x*)Td*≥0。

同理，對式(6)取極限得

定理1說明序列{xk}至少是線性收斂的，下面定理給出算法MMFR具有強收斂性質。

定理2在假設H條件下，若算法MMFR產生的任一子序列{xk}收斂于聚點x*，則非線性方程組問題(1)的最優解為x*，進一步有序列{xk}整列收斂于x*。

證明：類似于Yuan[16]中定理3.4的證明方法，易證結論成立，故省略證明過程。

3 數值試驗

本節通過比較算法MMFR、經典FR、三項FR算法在求解大規模非線性方程組問題上的數值結果，驗證算法MMFR的有效性與穩定性。

下面給出經典FR算法和三項FR算法的搜索方向，分別為

(9)

dk=

(10)

在算法MMFR的步驟2中，分別采用式(9)和式(10)產生搜索方向，其余步驟不變，得到的算法記為FR算法和MFR算法。

參數設置：r=0.5,σ=0.068,μ=0.25,β=0.5。程序運行環境：MATLAB(2014a)軟件實現，Windows10 (64 bite)，RAM:8 G，CPU 3.60 GHz。

算法終止準則為‖Fk‖≤10-5或Iter>3000，維數為[4500,12000,24000,30000,45000]。測試問題的函數名稱和初始點[17]見表1，數值試驗結果如表2所示，其中Pro (Problem)為問題序號，Dim (Dimension)為維數，Iter (Iterations)為迭代次數，NF(The number of function)為函數F(x)計算次數，Time為程序運行時間(單位：s)。根據迭代次數、函數計算次數和運行時間可以看出，總體上算法MMFR最好，算法MFR其次，算法FR最差(表2)。

表1 測試函數

表2 數值結果

為直觀地展示3種算法的性能差異，本節采用性能曲線描繪方法[18]分別描繪出迭代次數性能圖、函數計算次數性能圖和運行時間性能圖(圖1-3)。由圖1-3可知，算法MMFR總體上比算法MFR和算法FR更優，且具有更好的魯棒性，因此本文提出的算法MMFR是有效的和魯棒的。

圖1 迭代次數性能圖

圖2 函數計算次數性能圖

圖3 運行時間性能圖

4 結論

本文在修正FR算法的基礎上，結合凸組合思想，構造出一個新的修正搜索方向，并利用加速線搜索技術，提出一個加速FR型共軛梯度算法。新的搜索方向不依賴線搜索,具有充分下降和信賴域特性，還具有良好的理論性質與數值效果。因計算簡單，存儲量小，十分適合求解大規模非線性方程組問題。同時，也可嘗試將新算法進一步推廣到信號恢復等實際應用中。