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

李丹丹，王松華

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

0 引言

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

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

F(x)=0,x∈Rn，

(1)

minf(x),x∈Rn。

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

經(jīng)典共軛梯度法的一般迭代公式為

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

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

其中,βk為共軛參數(shù)，F(xiàn)k為F(xk)的簡寫。

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

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

1 算法描述與性質(zhì)

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

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

dk=

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

(2)

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

(3)

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

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

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

步驟2：若‖F(xiàn)k‖≤ε，則算法停止；

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

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

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

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

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

引理1算法MMFR產(chǎn)生的序列{dk}和{Fk}滿足以下性質(zhì)：

(4)

及

‖dk‖≤τk‖F(xiàn)k‖，

(5)

-Nk‖F(xiàn)k‖2。

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

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

Nk‖F(xiàn)k‖+(1-Nk)·

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

2 全局收斂性分析

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

假設H

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

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

(H2)函數(shù)F(x)的雅可比矩陣為?F(x)是有界的且為對稱正定矩陣，即存在正常數(shù)ξ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)

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

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

αkdk)<∞，

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

(7)

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

‖?f(xk)‖>ξ。

(8)

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

?f(x*)Td*≥0。

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

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

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

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

3 數(shù)值試驗

本節(jié)通過比較算法MMFR、經(jīng)典FR、三項FR算法在求解大規(guī)模非線性方程組問題上的數(shù)值結果，驗證算法MMFR的有效性與穩(wěn)定性。

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

(9)

dk=

(10)

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

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

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

表1 測試函數(shù)

表2 數(shù)值結果

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

圖1 迭代次數(shù)性能圖

圖2 函數(shù)計算次數(shù)性能圖

圖3 運行時間性能圖

4 結論

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