一類求解大規(guī)模非線性單調(diào)方程組的無導(dǎo)數(shù)共軛梯度方法

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

(北華大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，吉林 吉林 132013)

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

F(x)=0，

(1)

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

minf(x)，

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

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

不同的βk對應(yīng)不同的共軛梯度法，常用的共軛參數(shù)有

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

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

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

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

zk=xk+αkdk，

使其滿足

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

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

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

因此存在超平面

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

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

(2)

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

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

受上述文獻的啟發(fā)，本文提出了一類求解非線性單調(diào)方程組問題的無導(dǎo)數(shù)共軛梯度法，改進共軛參數(shù)βRMIL，利用不等式證明技巧，構(gòu)造與之對應(yīng)的譜參數(shù)θ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)

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

引理1設(shè)dk由算法1產(chǎn)生，則dk滿足充分下降性條件，即

2 收斂性分析

為了得到算法1的整體收斂性證明，現(xiàn)在給出如下假設(shè).

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

(6)

假設(shè)1表明，存在正數(shù)κ，對?x∈n滿足

(7)

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

此外，{xk}滿足

(8)

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

引理3若假設(shè)1成立，且{xk}、{dk}由算法1產(chǎn)生，則有

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

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

(9)

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

αk≤s.

(10)

(11)

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

證畢.

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

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

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

定理1若假設(shè)1成立，且{xk}，{dk}由算法1產(chǎn)生，則有

(12)

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

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

(13)

根據(jù)引理1可得

(14)

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

(15)

(16)

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

(17)

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

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

3 數(shù)值實驗

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

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

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

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

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

4 小 結(jié)

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