解大規(guī)模非線性方程組的一種三項(xiàng)型投影算法

李丹丹，王松華

（1.廣州華商學(xué)院 應(yīng)用數(shù)學(xué)系，廣東 廣州 511300；2.百色學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣西 百色 533000）

考慮如下非線性單調(diào)方程組

其中，g是連續(xù)可微函數(shù)且單調(diào)的，即

非線性單調(diào)方程組廣泛應(yīng)用于科學(xué)領(lǐng)域，如化學(xué)平衡體系［1］、經(jīng)濟(jì)均衡問題［2］和圖像恢復(fù)［3］等.因此，有關(guān)非線性單調(diào)方程組算法的研究顯得十分重要.目前求解非線性單調(diào)方程組有若干方法，且效果顯著.常用方法主要分為2類：矩陣類和無矩陣類.矩陣類主要包含信賴域法［4］、牛頓法［5］和擬牛頓法［6］等；無矩陣類主要包括無導(dǎo)數(shù)法［7］和梯度投影法［8］等.近年來，具有良好性質(zhì)（充分下降性和信賴域特性）的共軛梯度法，結(jié)合超平面投影技術(shù)，能高效地求解大規(guī)模非線性方程組問題，且在相對較弱條件下可得到全局收斂性.

在Fang［10］搜索方向的研究基礎(chǔ)上，筆者構(gòu)建出一個(gè)新的搜索方向，結(jié)合Solodov和Svaiter［11］的投影技術(shù)和線搜索技術(shù)，提出了一個(gè)求解大規(guī)模非線性單調(diào)方程組的三項(xiàng)無導(dǎo)數(shù)型共軛梯度算法.新算法優(yōu)點(diǎn)如下：

1）搜索方向自動滿足充分下降性和信賴域特性；

2）在合理的假設(shè)下，新算法具有全局收斂性；

3）試驗(yàn)結(jié)果表明新算法與同類算法相比更具有競爭力，具有良好的魯棒性.

1 算 法

其迭代公式為

其中，x k為當(dāng)前迭代點(diǎn)，x k+1為新的迭代點(diǎn)，αk為給定的步長，d k為搜索方向，經(jīng)典的迭代公式定義為

其中，βk是一個(gè)共軛參數(shù)，g(x k)的簡寫為gk.

Solodov和Svaiter［11］提出了一種投影技術(shù)來更新下一個(gè)迭代點(diǎn)，該技術(shù)在理論和數(shù)值試驗(yàn)上保證算法的高效性和魯棒性，令z k=x k+αk d k，更新新的迭代點(diǎn)公式為

其次，F(xiàn)ang［10］提出了一類求解大規(guī)模非線性單調(diào)方程組的無導(dǎo)數(shù)型共軛梯度法，其搜索方向?yàn)?/p>

性

，但不具備信賴域特性.

最后，受式（3）結(jié)構(gòu)的啟發(fā)，構(gòu)造一個(gè)新的搜索方向

基于以上闡述，給出求解問題（1）的算法描述：

算法LCGP

步驟1給定初始點(diǎn)x0∈Rn，正常數(shù)s，σ>0，ε，ρ∈(0，1)，μ2，μ3>0，μ1>μ2+μ3.令k：=1；

步驟2若，則算法停止；否則轉(zhuǎn)步驟3；

步驟3通過式（4）計(jì)算搜索方向d k；

步驟4（線搜索［9］）計(jì)算步長αk=ρsmk且mk為滿足如下不等式的最小非負(fù)整數(shù)

其中，σ>0，s>0，ρ∈(0，1)；

步驟5令z k=x k+αk d k，若，則算法停止，并令新的迭代點(diǎn)x k+1=z k；否則，通過式（2）計(jì)算新的迭代點(diǎn)x k+1；

步驟6令k：=k+1，轉(zhuǎn)步驟2.

2 充分下降性和信賴域特性

為分析算法的全局收斂性質(zhì)，證明搜索方向d k的充分下降性和信賴域特性.

引理1 由式（4）定義的搜索方向d k，滿足以下不等式和

其中，μ1>|μ2-μ3|，μ2，μ3>0.

證明當(dāng)k=0時(shí)即式（6）成立.當(dāng)k≥1時(shí)，式（4）兩邊左乘得

因此，式（6）成立.

當(dāng)k=0時(shí)，式（7）顯然成立.當(dāng)k≥1時(shí)，由式（4）可推出

綜上所述，式（7）成立.

證畢.

3 全局收斂性分析

為分析算法LCGP的全局收斂性質(zhì)，需作合理假設(shè)：假設(shè)A

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

A2函數(shù)g(x)在Rn上是Lipschitz連續(xù)的，即存在正整數(shù)a，對任意的x，y∈Rn，使得如下不等式成立

由假設(shè)A可知，存在正整數(shù)b，有

引理2 在假設(shè)A條件下，x*為問題（1）的最優(yōu)解，即g(x*)=0，那么由算法LCGP產(chǎn)生的序列{x k}具有以下性質(zhì)

1）

2）序列{x k}是有界的；

3）

引理3 在假設(shè)A條件下，算法LCGP是適定的，即算法LCGP的線搜索是有限步終止的.

提出的引理2和引理3可由Yuan［12］的引理3.1和引理3.2類似可證，故省略其證明過程.

給出算法LCGP全局收斂性定理.

定理1在假設(shè)A條件下，算法LCGP產(chǎn)生的序列{gk}滿足如下式子

證明假設(shè)對任意的k∈N且存在正數(shù)ε，都有

上式結(jié)合式（7）得

另外，由引理2 2）可知，存在無窮指標(biāo)集K1和聚點(diǎn)，使得當(dāng)k∈K1時(shí)，有

一方面，式（12）兩邊取極限，結(jié)合式（11）、（13）和（14）得

另一方面，式（6）兩邊取極限得

相矛盾，結(jié)論成立.

證畢.

4 數(shù)值試驗(yàn)

為了驗(yàn)證算法的有效性，通過數(shù)值實(shí)驗(yàn)將新算法與同類算法作比較.在算法LCGP的步驟3中，分別采用MRMIL1［10］、MRMIL2［10］和MRMIL3［10］產(chǎn)生搜索方向，其余步驟與算法LCGP一致，所對應(yīng)的算法分別記為MRMIL1算法、MRMIL2算法和MRMIL3算法.

相關(guān)參數(shù)如下

采用Matlab（2014a）實(shí)現(xiàn)上述各類算法，且運(yùn)行環(huán)境為：Windows10（64 bite），RAM：8GiB，CPU 3.60 GHz，終止準(zhǔn)則為：gk≤10-5，設(shè)置算法的迭代次數(shù)上限為1 000，維數(shù)為［4 500，12 000，24 000，30 000，45 000］.測試問題共有10個(gè)：文獻(xiàn)［13］的問題2、7、9、12；文獻(xiàn)［14］的問題4.2；文獻(xiàn)［15］的問題4、6、7、9；文獻(xiàn)［16］的問題9.數(shù)值結(jié)果如表1所示，其中Pro表示問題序號，Dim表示維數(shù)，Iter表示迭代次數(shù)，NG表示函數(shù)計(jì)算次數(shù)，Time表示程序運(yùn)行時(shí)間.

表1 各類算法數(shù)值結(jié)果

為更加直觀分析4種算法在3種指標(biāo)下的優(yōu)劣勢，描繪出3種指標(biāo)性能圖［17］，分別為CPU運(yùn)行時(shí)間性能圖（如圖1所示）、迭代次數(shù)性能圖（如圖2所示）和目標(biāo)函數(shù)值計(jì)算次數(shù)性能圖（如圖3所示）.所描繪性能圖的計(jì)算公式

圖1 CPU運(yùn)行時(shí)間性能圖

圖2 迭代次數(shù)性能圖

圖3 目標(biāo)函數(shù)值計(jì)算次數(shù)性能圖

其中，P是測試集，|P|是測試集的問題個(gè)數(shù)，V是算法集合，τp，v是某種指標(biāo)（運(yùn)行時(shí)間、迭代次數(shù)和函數(shù)計(jì)算次數(shù)），t是給定的數(shù)值比率.

表1的數(shù)值結(jié)果顯示，在相同的問題、維數(shù)、參數(shù)和精度下，算法LCGP在3個(gè)衡量指標(biāo)（迭代次數(shù)Iter、目標(biāo)函數(shù)計(jì)算次數(shù)NG和運(yùn)行時(shí)間Time）下總體優(yōu)于MRMIL1算法、MRMIL2算法和MRMIL3算法.此外，從圖1～3可知，算法LCGP相比MRMIL1算法、MRMIL2算法和MRMIL3算法更加有效地、快速地求解大規(guī)模非線性方程組問題，且具有更好的魯棒性.

5 小結(jié)

針對大規(guī)模非線性單調(diào)方程組問題，在Fang［10］所構(gòu)造的搜索方向形式的基礎(chǔ)上，利用Li［9］的新型線搜索技術(shù)，設(shè)計(jì)出一種新的三項(xiàng)共軛梯度算法，該方法在任何線搜索下自動滿足充分下降性條件和信賴域性質(zhì).在一定的假設(shè)下，證明了新方法具有良好的全局收斂性質(zhì).通過大規(guī)模算例進(jìn)行數(shù)值試驗(yàn)，其結(jié)果表明新算法更適用于求解大規(guī)模非線性單調(diào)方程組問題，且求解效率高于同類算法.