基于三階擬牛頓方程的對(duì)角三階擬牛頓法

馮茹茹，王希云

(太原科技大學(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.在擬牛頓算法中，存儲(chǔ)量至少為O(n2)。如果用稀疏矩陣來逼近Hessen陣的逆，要求存儲(chǔ)量為O(n)，且近似滿足擬牛頓條件。對(duì)角稀疏擬牛頓算法的提出使存儲(chǔ)量和工作量明顯減少，適合于大規(guī)模稀疏問題的求解。

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

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

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

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

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

1 對(duì)角三階擬牛頓法

為保證搜索方向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)定點(diǎn)，則有‖dk‖≤M‖gk‖.

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

引理 3[7]對(duì)?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知，對(duì)?k∈K2有:

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

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

由上式可得:

則由(i)和(ii)可得

因?yàn)閒(x)有下界，且對(duì)?k有，fk≤Ck，所以Ck有下界。由上式可得:

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

3 超線性收斂性

假設(shè)3f(x)在極小點(diǎn)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)在極小點(diǎn)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)生無窮點(diǎn)列{xk}收斂到局部極小點(diǎn)x*，即xk→x*，但xk≠x*，若

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

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

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

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

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

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

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

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

計(jì)算結(jié)果表明，當(dāng)維數(shù)增加時(shí)，迭代次數(shù)的增加最不敏感，反而有一定的減少。從整體上看，基于三階擬牛頓方程的對(duì)角三階擬牛頓法比對(duì)角稀疏擬牛頓法計(jì)算效率要高，適合求解大規(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]時(shí)貞軍，孫國.無約束優(yōu)化問題的對(duì)角稀疏擬牛頓算法[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2006，26(1):101-112.

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

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

[5]孫清瀅，鄭艷梅.大步長(zhǎng)非單調(diào)線搜索規(guī)則的Lampariello修正對(duì)角稀疏擬牛頓算法的全局收斂性[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é)報(bào)，2010，31(3):249-251.