李艷冉，高 靜，曹名圓，姜曉威，白 雪

(北華大學數學與統計學院，吉林 吉林 132013)

本文考慮非線性單調方程組

F(x)=0，

(1)

其中F(x)：n→n單調且連續(xù)，即F(x)滿足對?x，y∈n，有(F(x)-F(y))T(x-y)≥0.非線性單調方程組廣泛應用于圖像分割[1]、電力系統的操作與控制[2]、信號重構[3]等眾多領域.數學領域中的有序回歸問題[4]、單調變分不等式問題[5]以及具有Bregman距離的廣義近端算法的子問題[6]也可以轉化為非線性單調方程組來求解.牛頓法、擬牛頓法等經典求解算法由于每步迭代過程中都需要計算雅克比矩陣或者雅可比矩陣的近似矩陣，不適合求解大規(guī)模方程組，因此，當問題規(guī)模很大時，很多學者更傾向于使用結構簡便、存儲空間小的共軛梯度法來求解大規(guī)模非線性單調方程組問題.

minf(x)，

其中，f：n→是光滑函數.假設xk是第k步的迭代點，dk是搜索方向，αk是步長，gk是f(x)在點xk處的梯度，βk為共軛參數，則第k+1步迭代點的選取格式為

xk+1=xk+αkdk，k=0，1，2，…，

不同的βk對應不同的共軛梯度法，常用的共軛參數有

2012年，Rivaie等[7]提出了RMIL共軛梯度法求解無約束優(yōu)化問題，其共軛參數βk定義為

該算法的數值結果表明，RMIL共軛梯度法與其他共軛梯度法相比，在運算性能方面更占優(yōu)勢.2020年，Fang[8]在此基礎上，提出了一類求解非線性單調方程組的改進的RMIL無導數共軛梯度法，在RMIL共軛參數的基礎上引入了譜參數θk，使

該方向dk無需步長αk的調節(jié)即可滿足充分下降性.

當確定搜索方向dk后，通過線搜索技術找到點

zk=xk+αkdk，

使其滿足

(F(zk)，xk-zk)>0.

另一方面，對于滿足F(x*)=0的任意x*∈，根據F的單調性，可得

(F(zk)，x*-zk)=-(F(x*)-F(zk)，x*-zk)≤0.

因此存在超平面

Hk={x∈n(F(zk)，x-zk)=0}，

將單調方程組(1)的解x*從xk中嚴格分開.基于上述結論，文獻[8]中將xk投影到Hk上得到下一迭代點xk+1：

(2)

該投影技術結合無導數線搜索技術確保了搜索方向的有界性和算法的全局收斂性.數值實驗表明，在求解大規(guī)模非線性單調方程組問題時，該方法優(yōu)于同類算法.

2019年，Liu和Feng[9]提出一類求解帶有凸約束的非線性單調方程組的無導數共軛梯度法，將DY共軛參數改進為

受上述文獻的啟發(fā)，本文提出了一類求解非線性單調方程組問題的無導數共軛梯度法，改進共軛參數βRMIL，利用不等式證明技巧，構造與之對應的譜參數θk，使搜索方向dk滿足充分下降性和有界性，進而證明算法的整體收斂性.

1 算 法

算法1

步0 選取初始點x0∈n，令δ>0，σ>0，s>0，ε>0，1>ρ>0，kmax>0，α=s，d0=-F(x0).并令k=0.

步2 若α滿足

(3)

步4 計算F(xk+1)，yk=F(xk+1)-F(xk).確定搜索方向

(4)

其中γ∈(0，1)，yk=Fk+1-Fk，wk=dk+tkyk，

(5)

現在，我們證明由式(4)和(5)確定的搜索方向dk滿足充分下降性條件.

引理1設dk由算法1產生，則dk滿足充分下降性條件，即

2 收斂性分析

為了得到算法1的整體收斂性證明，現在給出如下假設.

假設1(ⅰ)非線性單調方程組F(x)=0的解集是非空的.

(6)

假設1表明，存在正數κ，對?x∈n滿足

(7)

引理2若假設1成立，且{xk}由算法1產生，則對任意的x*滿足F(x*)=0，有

此外，{xk}滿足

(8)

具體證明參見文獻[8].

引理3若假設1成立，且{xk}、{dk}由算法1產生，則有

其中，κ、γ、s、L均為常數，并且κ>0，1>γ>0，s>0，L>0.

證明：由式(2)和算法1的步2可知

(9)

又根據算法1步2中線性搜索的定義以及αk是{s，ρs，ρ2s，…}中使式(3)成立的最大數，1>ρ>0可知

αk≤s.

(10)

(11)

綜上，由式(6)～(7)和(9)～(11)可得

證畢.

引理4若假設1成立，xk、αk、dk、Fk由算法1產生，對所有k∈，存在常數ε，滿足Fk≥ε，則有

具體證明參見文獻[8].

綜合以上結論，可以獲得算法1的整體收斂性定理.

定理1若假設1成立，且{xk}，{dk}由算法1產生，則有

(12)

另外，序列{xk}收斂到x*且F(x*)=0.

證明：假設式(12)不成立，則存在常數ε>0滿足

(13)

根據引理1可得

(14)

因此，由式(13)和(14)可知

(15)

(16)

由式(8)、(9)和(16)可得

(17)

另一方面，結合引理4和式(15)，有

此式與式(17)矛盾，進而表明式(12)成立.由假設1和引理2以及式(12)，能夠推出{xk}收斂到x*，且x*滿足F(x*)=0.證畢.

3 數值實驗

將本文算法1與文獻[8，10]提出的MRMIL1和DFPB1算法進行比較.本文所有數值實驗都是在4 GB內存Intel CPU I5-4210的PC機上，用Matlab R2015b 編程完成的.

本文利用文獻[11]中定義的分式

刻畫算法性能.這里，P是測試集，|P|是測試集P中問題的數量，V是符合條件的問題集，tp，ν表示計算機運算測試問題所花費的CPU時間，或者函數調用次數，或者函數迭代次數.

圖1給出了本文算法1(黑色實線)與MRMIL1(綠色實線)和DFPB1算法(紅色實線)在CPU時間、函數調用次數和函數迭代次數方面的實驗結果對比.圖1的橫坐標τ表示一種算法求解測試問題的最快(高)效率的百分比，縱坐標ρv(τ)表示每種方法成功解決的測試問題數量的百分比.從圖1 a和圖1 b中可以看出，在函數調用次數和CPU時間方面，算法1的性能曲線在其他兩條曲線之上，說明本文提出的無導數改進RMIL共軛梯度方法在求解大規(guī)模非線性單調方程組問題時能夠使用更少的函數調用次數和CPU時間，求解效率更高.因此，從函數調用次數和CPU時間方面考慮數值性能，本文算法明顯優(yōu)于文獻[8，10]中的方法.圖1 c顯示的是算法迭代次數的對比結果，從圖像可以看出，當τ<2時，算法1與DFPB1算法的數值表現基本一致，稍遜于MRMIL1；當τ≥2時，三個算法在迭代次數方面表現相當.

圖1算法性能對比Fig.1Comparison of algorithm performance

4 小 結

本文主要研究了求解大規(guī)模非線性單調方程組的高效算法，提出了一類基于投影技術的無導數共軛梯度方法.證明了搜索方向滿足充分下降性條件，在無導數線搜索和適當假設條件下，證明了算法的整體收斂性.數值結果表明，該算法在求解大規(guī)模非線性單調方程組時具有較高效率，在函數調用次數和CPU時間方面的表現優(yōu)于同類算法.