解大規(guī)模非線性方程組的新型梯度類投影算法

李丹丹，李遠飛

（廣州華商學院數(shù)據(jù)科學學院，廣東 廣州 511300）

0 引言

本文考慮非線性單調(diào)方程組

其中F：Rn→Rn是連續(xù)可微函數(shù)且單調(diào)的，即對?x，y∈Rn滿足不等式

因此非線性單調(diào)方程組問題可轉化為無約束優(yōu)化問題。

非線性單調(diào)方程組廣泛應用于不同領域，如單位球面優(yōu)化問題［1］、L1范數(shù)正則稀疏優(yōu)化問題［2］和壓縮感知中的信號恢復問題［3］等。目前用于求解非線性方程組的經(jīng)典算法有牛頓法［4］、擬牛頓法［5］、信賴域法［6］、共軛梯度法［7］。研究表明牛頓法與擬牛頓法雖局部收斂較快，但每次迭代都需計算一個與雅可比矩陣相關的方程組，導致算法在求解大規(guī)模問題時，計算量過大，效率低。而在信賴域方法中，信賴域半徑的選取往往依賴經(jīng)驗，具有一定的盲目性。共軛梯度法因具有算法簡易和存儲量小的特點，近年來被廣泛應用于求解大規(guī)模非線性方程組。如何利用共軛梯度法高效求解大規(guī)模非線性方程組，成為優(yōu)化領域的熱點之一。在共軛梯度法中其搜索方向和線搜索技術直接決定共軛梯度法理論的優(yōu)良性及算法的高效性。Fang［8］給出新的搜索方向，有效提高了非線性大規(guī)模問題的求解效率，本文在Fang［8］的基礎上，設計出一個新型的搜索方向，結合經(jīng)典且高效的線搜索方法［9］和超平面投影技術［10］，提出了一個無導數(shù)型共軛梯度投影算法用于求解大規(guī)模非線性單調(diào)方程組問題。

1 算法

一般共軛梯度法公式為

其中αk為給定的步長，dk為搜索方向，一般的迭代公式為

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

Fang［8］搜索方向的迭代公式記為

其中。同 時Fang［8］定 義 了 兩 種 不 同 參 數(shù)θk的 形 式，此 處 記 為

其中0＜γ＜1。將分別帶入式（3）得到搜索方向上述搜索方向雖具有充分下降性質(zhì)，但并不滿足信賴域性質(zhì)，而信賴域性質(zhì)對算法全局收斂性的證明起到促進作用。

基于βk的定義和的構造形式，本文提出了一個具有充分下降性與信賴域性質(zhì)的搜索方向

算法MRMILL具體步驟為：

步驟1給定初始點x0∈Rn，常數(shù)μ＞0，ε∈(0，1)，τ＞0，令k：=0；

步驟2若‖F(xiàn)(xk)‖≤ε，則算法停止，否則轉下一步；

步驟3按照式（6），計算搜索方向dk；

步驟4由線搜索技術［9］，令步長αk為序列{s，ρs，ρ2s，…}中滿足以下不等式的最大元素：

其中常數(shù)σ＞0，s＞0，ρ∈(0，1)，求出步長αk；

步驟5計算試探點zk=xk+αkdk；

步驟6若‖F(xiàn)(zk)‖≤ε，則算法停止；否則通過以下超平面投影技術［10］計算新的迭代點xk+1：

步驟7令k：=k+1，轉步驟1。

2 充分下降性條件

證明算法MRMILL中的dk滿足自動充分下降性條件，為分析算法MRMILL的全局收斂性提供保證。

引理1由式（6）產(chǎn)生搜索方向dk，則有

證明當k=0時，得顯然式（8）成立。當k≥1時，在式（6）兩邊左乘，得

故式（8）成立。證畢。

3 全局收斂性分析

為討論算法MRMILL的全局收斂性質(zhì)，需作如下一般性假設：

假設A

（A1）問題（1）的解集非空；

（A2）函數(shù)F：Rn→Rn是Lipschitz連續(xù)的，即存在常數(shù)M＞0，對任意的x，y∈Rn滿足‖F(xiàn)(x)-F(y)‖≤

由假設A可推出，存在常數(shù)ξ＞0，有

下面的引理2和引理3可由文獻［11］的引理4和文獻［12］引理3.2類似可證，故省略其證明過程。

引理2在假設A條件下，算法MRMILL產(chǎn)生無窮序列{xk}，那么問題（1）的最優(yōu)解x*滿足此外，序列{xk}有界且滿足。

引理3在假設A條件下，算法MRMILL的線搜索是有限步終止的。

引理4在假設A條件下，由式（6）產(chǎn)生搜索方向dk，則有

證明當k=0時，得‖d0‖=‖F(xiàn)0‖≤(2M+1)‖F(xiàn)0‖，顯然結論成立。當k≥1時，由式（6）得

此外，由yk-1的定義及假設（A2）得

結合式（10）得‖dk‖≤(2τM+1)‖F(xiàn)k‖。另外，由引理1得‖dk‖≥‖F(xiàn)k‖，故結論成立。證畢。

定理1在假設A條件下，序列{αk，dk，xk，F(xiàn)k}由算法MRMILL產(chǎn)生，則有。

證明采用反證法。假設結論不成立，則對任意的k∈N，存在常數(shù)ε＞0，有‖F(xiàn)k‖＞ε，由引理4得

另外，由引理2可知，存在無窮指標集K1和聚點，使得當k∈K1時，有

對于式（13），當k趨于無窮時，由極限運算法則可得

由 式（12）、（14）和（15）得F()T＞0，對于式（8），當k趨于無 窮時，由極限運算法則可得由式（14）和（15）得F()T≤0，產(chǎn)生矛盾。故假設不成立，成立。證畢。

4 數(shù)值試驗

為檢驗算法MRMILL的有效性，對MRMILL算法、MRMIL1算法、MRMIL2算法在求解式（1）問題上進行數(shù)值試驗，并對數(shù)值試驗結果進行比較分析。測試問題來自文獻［9］、［12-14］，初始點隨機產(chǎn)生，即：rand（n，1）。

程序運行環(huán)境：Windows 10操 作 系 統(tǒng)，Inel Pentium（R）DuaCore CPU，E58003.2 GHz，內(nèi) 存8 G，由MATLA2014a編寫運行。終止條件：‖F(xiàn)(x)‖≤10-5或Iter≥3000。參數(shù)設置：s=1，ρ=0.48，σ=0.024，τ=1，維數(shù)為［3000，6000，9000，30000，60000，90000］。測試問題見表1，試驗結果見表2。

表1 測試問題Tab.1 Test problems

表2 三種算法的數(shù)值結果Tab.2 Numerical results of three methods

續(xù)表2 三種算法的數(shù)值結果Continued Tab.2 Numerical results of three methods

為更直觀地反映各類算法的性能，針對三種指標，采用文獻［15］的評價方法，描繪出三類性能圖，如圖1。評價標準為：曲線越靠上，所表示的算法性能越好。

圖1 三類性能圖Fig.1 Three performance profiles

從表2與圖1中可得出如下結論：

（1）表2的數(shù)值結果表明在相同的精度、問題和維度下，算法MRMILL在迭代次數(shù)、目標函數(shù)計算次數(shù)和CPU運行時間等三個指標上總體效果優(yōu)于算法MRMIL1和算法MRMIL2；隨著維數(shù)的增加，算法MRMILL的求解效果并沒有受到影響，說明算法具有穩(wěn)定性，適合求解大規(guī)模非線性單調(diào)方程組問題。

（2）性能圖（圖1）中算法MRMILL在三種指標下，所對應的曲線均高于算法MRMIL1和算法MRMIL2，表明三種算法中MRMILL性能最優(yōu)，具有較強的魯棒性。

綜上所述，新算法具有良好的理論性質(zhì)，數(shù)值結果驗證了新算法的有效性與魯棒性，后續(xù)可進一步研究將新算法推廣到求解圖像恢復與信號處理問題中，驗證其實用性。