基于三階擬牛頓方程的對角三階擬牛頓法

馮茹茹，王希云

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原030024)

無約束優(yōu)化問題的一般形式為:

其中f:Rn→R為二次連續(xù)可微函數(shù)，fk表示f(xk)，gk表示▽f(xk)。定義dk=-Hkgk為擬牛頓方向，其中Hk為Hessen矩陣的逆近似，要求Hk正定且滿足擬牛頓條件

其中yk-1=gk-gk-1，sk-1=xk-xk-1.在擬牛頓算法中，存儲量至少為O(n2)。如果用稀疏矩陣來逼近Hessen陣的逆，要求存儲量為O(n)，且近似滿足擬牛頓條件。對角稀疏擬牛頓算法的提出使存儲量和工作量明顯減少，適合于大規(guī)模稀疏問題的求解。

1988 年，Barzilai和 Borwein[1]提出兩點步長法，迭代公式為xk+1=xk-Dkgk，其中Dk=αkI是一個矩陣。為了使Dk具有擬 Newton性質(zhì)，計算 αk使min‖sk-1-Dkyk-1‖，得

時貞軍[2]提出了對角稀疏擬牛頓法，該算法在每次迭代中利用對角矩陣近似擬牛頓法中的校正矩陣，通過求解得到min‖Hkyk-1-sk-1‖2得到Hk，從而構(gòu)造對角稀疏擬牛頓法。

之后，很多學(xué)者對此類算法進(jìn)行了研究，其中對角二階擬牛頓法[3]對Hessen陣具有二階逼近階;孫清瀅，崔彬[4]和鄭艷梅[5]分別將 Grippo 非單調(diào)線搜索和Zhang H.C.提出的非單調(diào)線搜索引入對角稀疏擬牛頓法進(jìn)行了研究。

基于三階擬牛頓方程[6]

來獲得Hessen陣的正定對角矩陣逆近似，同時將Zhang H.C.[7]提出的非單調(diào)線搜索規(guī)則與時貞軍提出的大步長線搜索技巧結(jié)合設(shè)計求解無約束優(yōu)化問題的對角三階擬牛頓法。

1 對角三階擬牛頓法

為保證搜索方向dk=-Hkgk為下降方向，要求，因此有問題(SP)

在問題(SP)中，m，M取正常數(shù)。

算法1(DSQN):

(Ⅰ)?x0∈Rn，H0=In，C0=f0=f(x0)，Q0=0＜ηmin≤ ηmax＜1，k=0，ε＞0.

(Ⅱ)若‖gk‖ ＜ε，則停，否則轉(zhuǎn)(Ⅲ)。

(Ⅲ)令dk=-Hkgk，其中Hk由式(5)確定，轉(zhuǎn)(Ⅳ)。

令xk+1=xk+αkdk，fk+1=f(xk+1).

(Ⅴ)通過某種規(guī)則給出 ηk∈[ηmin，ηmax]，

令k∶=k+1，轉(zhuǎn)(Ⅱ)。

引理1 若xk不是問題(SP)的穩(wěn)定點，則有‖dk‖≤M‖gk‖.

引理2 若xk不是問題(SP)的穩(wěn)定點，則有

引理 3[7]對?k有，fk≤Ck.

2 全局收斂性

假設(shè)1f(x)在水平集L(x0)={x∈Rn|f(x)≤f(x0)}上有下界。

假設(shè)2f(x)的梯度g(x)在水平集上Lipschitz連續(xù)，即存在常數(shù)L＞0，使得‖g(x)-g(y)‖≤L‖x-y‖，?x，y∈L(x0).

證明 令K1={k|αk=sk}，K2={k|αk＜sk}(i)如果k∈K1，則由式(6)及引理1和2，可以得到:

(ii)如果k∈K2，則 αk＜sk，由線搜索規(guī)則及引理3知，對?k∈K2有:

再由中值定理及 αk∈{sk，ωsk，ω2sk，…}，存在θk∈[0，1]和正整數(shù)i≥1 使得

由假設(shè)2，Cauchy-Schwartz不等式，式(8)得:

由上式可得:

則由(i)和(ii)可得

因為f(x)有下界，且對?k有，fk≤Ck，所以Ck有下界。由上式可得:

由ηmax＜1及式(7)知:由式(10)和式(11)可得.證畢。

3 超線性收斂性

假設(shè)3f(x)在極小點x*的鄰域內(nèi)二次連續(xù)可微，且存在ε＞0，M'＞m'＞0使得當(dāng)

‖x-x*‖＜ε，?y∈Rn，有

m'‖y‖2≤yT▽2f(x)y≤M'‖y‖2;

假設(shè)4 ▽2f(x)在極小點x*的某鄰域內(nèi)Lipschitz連續(xù)，即且存在ε＞0，

‖▽2f(y)-▽2f(x)‖≤γ‖x-y‖，?x，y∈N(x*，ε).

其中r是Lipschitz常數(shù)。

定理2 假設(shè)1、2、3均成立，若算法產(chǎn)生無窮點列{xk}收斂到局部極小點x*，即xk→x*，但xk≠x*，若

則:(1)當(dāng)k充分大時，αk=1;(2)序列{xk}超線性收斂到x*.

證明 (1)由引理1及定理1可知‖dk‖→0.利用泰勒展開及引理1、2有

當(dāng)k充分大時‖dk‖2]，即當(dāng)k充分大時，σk=1滿足算法算法1中的線搜索規(guī)則。

(2)可仿照文獻(xiàn)[1]證明{xk}超線性收斂到x*的充要條件為式(12)。

4 數(shù)值結(jié)果

利用MATLAB程序，將算法1與文獻(xiàn)[1]中的對角稀疏擬牛頓法進(jìn)行了比較，詳細(xì)結(jié)果見表1.

用IT表示算法的迭代次數(shù)，T表示所用時間，fopt表示目標(biāo)函數(shù)的最優(yōu)值。下面分別給出維數(shù)N=100，2 000，5 000，10 000 的計算結(jié)果。當(dāng)N＜2 000，在精度滿足fk-f*≤10-8時，可以得到問題的精確解。當(dāng)N≥2 000，在精度滿足fk-f*≤10-6時算法迭代停止。

表1 算法1與對角稀疏擬牛頓法的數(shù)值結(jié)果Tab.1 The numerical results from the method 1 and diagonal sparse quasi-Newton method

計算結(jié)果表明，當(dāng)維數(shù)增加時，迭代次數(shù)的增加最不敏感，反而有一定的減少。從整體上看，基于三階擬牛頓方程的對角三階擬牛頓法比對角稀疏擬牛頓法計算效率要高，適合求解大規(guī)模無約束優(yōu)化問題。

[1]BARZILAI J，BONWEIN J M.Two-point step size gradient methods[J].IMA Journal Of Numerical Analysis，1988，8:141-148.

[2]時貞軍，孫國.無約束優(yōu)化問題的對角稀疏擬牛頓算法[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2006，26(1):101-112.

[3]潘義勇，潘平奇.無約束優(yōu)化問題的對角二階擬牛頓算法[C]//中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集.北京:中國運籌學(xué)會，2008:64-68.

[4]孫清瀅，崔彬，王長鈺.新非單調(diào)線搜索規(guī)則的 Lampariello修正對角稀疏擬牛頓算法[J].計算數(shù)學(xué)，2008，30(3):255-269.

[5]孫清瀅，鄭艷梅.大步長非單調(diào)線搜索規(guī)則的Lampariello修正對角稀疏擬牛頓算法的全局收斂性[J].數(shù)學(xué)進(jìn)展，2008，37(3):311-320.

[6]ZHANG J Z，XU C X.Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations[J].J Comput Appl Math，2001，137:269-278.

[7]ZHANG H C，WILIAM W HAGER.A nonmonotone line search technique and its application to unconstrained optimization[J].J SIAM J Optim，2004，14(4):1043-1056.

[8]朱帥，王希云.一類Armijo搜索下的記憶梯度法及其全局收斂性[J].太原科技大學(xué)學(xué)報，2010，31(3):249-251.