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

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

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

F(x)=0，

(1)

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

minf(x)，

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

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

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

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

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

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

當(dāng)確定搜索方向dk后，通過線搜索技術(shù)找到點(diǎn)

zk=xk+αkdk，

使其滿足

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

另一方面，對(duì)于滿足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中嚴(yán)格分開.基于上述結(jié)論，文獻(xiàn)[8]中將xk投影到Hk上得到下一迭代點(diǎn)xk+1：

(2)

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

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

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

1 算 法

算法1

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

步2 若α滿足

(3)

步4 計(jì)算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ù)κ，對(duì)?x∈n滿足

(7)

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

此外，{xk}滿足

(8)

具體證明參見文獻(xiàn)[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)生，對(duì)所有k∈，存在常數(shù)ε，滿足Fk≥ε，則有

具體證明參見文獻(xiàn)[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)矛盾，進(jìn)而表明式(12)成立.由假設(shè)1和引理2以及式(12)，能夠推出{xk}收斂到x*，且x*滿足F(x*)=0.證畢.

3 數(shù)值實(shí)驗(yàn)

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

本文利用文獻(xiàn)[11]中定義的分式

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

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

圖1算法性能對(duì)比Fig.1Comparison of algorithm performance

4 小 結(jié)

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