李丹丹，李遠飛

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

0 引言

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

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

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

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

算法MRMILL具體步驟為：

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

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

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

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

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

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

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

步驟7令k：=k+1，轉(zhuǎn)步驟1。

2 充分下降性條件

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

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

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

故式（8）成立。證畢。

3 全局收斂性分析

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

假設(shè)A

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

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

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

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

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

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

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

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

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

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

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

證明采用反證法。假設(shè)結(jié)論不成立，則對任意的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)生矛盾。故假設(shè)不成立，成立。證畢。

4 數(shù)值試驗

為檢驗算法MRMILL的有效性，對MRMILL算法、MRMIL1算法、MRMIL2算法在求解式（1）問題上進行數(shù)值試驗，并對數(shù)值試驗結(jié)果進行比較分析。測試問題來自文獻［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ù)設(shè)置：s=1，ρ=0.48，σ=0.024，τ=1，維數(shù)為［3000，6000，9000，30000，60000，90000］。測試問題見表1，試驗結(jié)果見表2。

表1 測試問題Tab.1 Test problems

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

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

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

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

從表2與圖1中可得出如下結(jié)論：

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

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

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