胡午杰，袁功林

(廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧 530004)

0 引言

本文考慮如下非線性方程組問題：

h(x)=0,x∈Rn,

(1)

其中目標(biāo)函數(shù)連續(xù)可微，滿足：

(h(x)-h(y))T(x-y)≥0, ?x,y∈Rn。

(2)

minh*(x),x∈Rn。

(3)

其中‖·‖是歐幾里得范數(shù)。求解問題(3)的迭代公式為：

xk+1=xk+αkdk,

其中dk表示搜索方向，αk為搜索步長。由上述迭代公式可知，算法的效率不僅與搜索方向有關(guān)，而且與搜索技術(shù)也密不可分[4-10]。眾所周知，共軛梯度算法簡單、高效和易操作，是求解大規(guī)模復(fù)雜問題的一種有效工具。共軛梯度法搜索方向定義為：

不同的βk決定不同的共軛梯度算法。其中著名的PRP[11-12]公式定義為：

該算法效率高，但收斂性不理想?；诖斯?，Zhang[8]提出如下的三項(xiàng)共軛梯度公式：

(4)

該算法具有充分下降性，滿足：

(5)

受此公式啟發(fā)，Yuan等[12]提出求解模型(1)的三項(xiàng)共軛梯度公式：

其中μ>0，此公式滿足式(5)和信賴域性質(zhì)。

(6)

受上述兩種方法的啟發(fā)，本文設(shè)計(jì)如下三項(xiàng)共軛梯度公式：

(7)

其中，yk=hk+1-hk，μ1>1,μ2>1。

本文將證明修正的三項(xiàng)共軛梯度算法(modified three-lerm conjugate gradient algorithm, MTCG)同時(shí)滿足下降性和信賴域性，且下降量更大。

1 修正的三項(xiàng)共軛梯度算法(MTCG)

算法MTCG步驟如下：

Step0：給定初始點(diǎn)x0=Rn，常數(shù)μi>1,σ,γ,s>0,i=1, 2;ρ,ε∈(0,1)。令dk=-μkhk,k:=1。

Step1:若‖hk‖<ε，則算法終止；否則進(jìn)行下一步。

Step2:基于如下的線搜索技術(shù)[10]選擇合適步長αk。

-h(xk+αkdk)Tdk≥σαk‖h(xk+αkdk)‖‖dk‖2,

(8)

其中αk=max{s,ρs,ρ2s,…},σ，s>0,ρ∈(0,1)。

Step3：令迭代公式為zk=xk+αkdk。

(9)

Step5：基于式(5)更新dk。

Step6：令k:=k+1，轉(zhuǎn)step 1。

備注：式(9)是Solodov[13]提出的基于超平面和投影更新當(dāng)前迭代點(diǎn)的技術(shù)，其中超平面Hk={x∈Rn|〈h(zk),(x-zk)〉=0}，xk+1為xk在超平面Hk上的投影。

2 算法MTCG的充分下降性及全局收斂性

證明算法MTCG的全局收斂性，需作基本的假設(shè)條件：

假設(shè)1：目標(biāo)模型(1)的解集非空。

假設(shè)2：目標(biāo)函數(shù)h(x)在Rn上Lipschitz連續(xù)，即存在一個(gè)常數(shù)L>0，使得：

‖h(x)-h(y)‖≤L‖x-y‖, ?x,y∈Rn。

由假設(shè)2可知：

(10)

其中ζ為一個(gè)正數(shù)。

引理1若dk是由式(5)定義，則有：

(11)

和：

‖dk‖≤(μ1+2μ2)‖hk‖。

(12)

證明：當(dāng)k=0時(shí)，式(10)、(11)顯然成立。

當(dāng)k>0時(shí)，由式(5)可知，

所以式(11)成立，對(duì)于式(12),由：

故式(12)成立。綜上所述，引理1成立。在式(11)、(12)和文獻(xiàn)[12]的基礎(chǔ)上，本文僅僅給出相應(yīng)的引理和收斂性定理，省略其證明過程。

引理2[12]若假設(shè)1、2成立，則算法MTCG生成有界的迭代點(diǎn)列且點(diǎn)列{xk}滿足關(guān)系式：

‖xk+1-x*‖2≤‖xk-x*‖2-‖xk+1-x*‖2，

其中，x*為迭代數(shù)列的極限點(diǎn)。

引理3[12]若假設(shè)1、2成立，則算法MTCG經(jīng)過有限次迭代生成點(diǎn)列{xk}且點(diǎn)列滿足公式xk+1=xk+αkdk。

定理1[12]若假設(shè)1、2成立，算法MTCG生成相應(yīng)的迭代序列{hk}，{αk}，{dk}，{xk},則：

(13)

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

為檢驗(yàn)算法效率，目標(biāo)算法與類似算法作數(shù)值比較。其中類似算法的搜索方向是式(4)簡記為算法(4)，其余步驟相同。相關(guān)測試函數(shù)選自文獻(xiàn)[14-16]，本文隨機(jī)挑選了其中的6個(gè)經(jīng)典函數(shù)，見表1所示。

表1 測試函數(shù)

測試環(huán)境：本文數(shù)值實(shí)驗(yàn)代碼都在Matlab R2010b編寫運(yùn)行，電腦配置為Intel Pentium(R)Dual-Core E5800 3.2 GHz的Windows 7操作系統(tǒng)。

實(shí)驗(yàn)參數(shù)設(shè)置：σ=0.98,s=1.5,γ=0.95，ε=10-5,μ1=1.01,μ2=1.5。

實(shí)驗(yàn)終止條件：‖h(x)‖≤10-5或NI≥1 000.實(shí)驗(yàn)結(jié)果見表2。

參數(shù)說明：NI為算法迭代次數(shù)；NG為目標(biāo)函數(shù)計(jì)算次數(shù)；t為Cputime算法運(yùn)行時(shí)間。

表2 數(shù)值結(jié)果

為了更直觀地比較兩種算法的性能，本文引用文獻(xiàn)[17]方法進(jìn)行算法MTCG與算法(4)的性能比較，其結(jié)果見圖1。

從圖1可以看出，算法MTCG相比算法(4)更加高效快速解決復(fù)雜問題，從而算法MTCG的魯棒性更強(qiáng)。

圖1 算法MTCG與算法(4)的性能比較(CPU-Time)

4 結(jié)語

針對(duì)大規(guī)模非線性方程組問題，本文在三項(xiàng)共軛梯度算法的啟發(fā)下，提出了一種新的三項(xiàng)共軛梯度算法。其中，算法自動(dòng)擁有充分下降性和信賴域性質(zhì)且在一定條件下具有全局收斂性。數(shù)值實(shí)驗(yàn)表明算法MTCG比算法(4)更有效，因此算法MTCG的提出是有意義的。