李丹丹，王松華

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

0 引言

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

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

F(x)=0,x∈Rn，

(1)

minf(x),x∈Rn。

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

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

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

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

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

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

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

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

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

首先，Abubakar等[12]在2019年提出一種修正FR共軛梯度法，其搜索方向?yàn)?/p>

dk=

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

(2)

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

(3)

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

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

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

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

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

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

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

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

為后續(xù)證明算法的全局收斂性質(zhì)，下面分析搜索方向dk的兩個(gè)重要性質(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 全局收斂性分析

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

假設(shè)H

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

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

(H2)函數(shù)F(x)的雅可比矩陣為?F(x)是有界的且為對(duì)稱正定矩陣，即存在正常數(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)結(jié)合f(x) 的定義可知，對(duì)于任意的k，都有‖F(xiàn)k+1‖≤‖F(xiàn)k‖。此外，由式(3)和式(4)得出

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

αkdk)<∞，

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

(7)

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

‖?f(xk)‖>ξ。

(8)

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

?f(x*)Td*≥0。

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

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

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

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

3 數(shù)值試驗(yàn)

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

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

(9)

dk=

(10)

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

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

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

表1 測(cè)試函數(shù)

表2 數(shù)值結(jié)果

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

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

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

圖3 運(yùn)行時(shí)間性能圖

4 結(jié)論

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