宮恩龍,陳雙雙,孫清瀅,陳穎梅

(1.青島酒店管理職業(yè)技術(shù)學(xué)院,山東青島 266100；2.中國(guó)石油大學(xué)理學(xué)院,山東青島 266580)

基于信賴域技術(shù)和修正擬牛頓方程的非單調(diào)超記憶梯度算法

宮恩龍1,陳雙雙2,孫清瀅2,陳穎梅2

(1.青島酒店管理職業(yè)技術(shù)學(xué)院,山東青島 266100；2.中國(guó)石油大學(xué)理學(xué)院,山東青島 266580)

基于信賴域技術(shù)和修正擬牛頓方程,結(jié)合Neng-Zhu Gu非單調(diào)策略,設(shè)計(jì)新的求解無(wú)約束最優(yōu)化問(wèn)題的非單調(diào)超記憶梯度算法,分析算法的收斂性和收斂速度。新算法每次迭代節(jié)約了矩陣的存儲(chǔ)量和計(jì)算量,算法穩(wěn)定,適于求解大規(guī)模問(wèn)題。數(shù)值試驗(yàn)結(jié)果表明新算法是有效的。

超記憶梯度算法；非單調(diào)規(guī)則；收斂性；收斂速度；數(shù)值試驗(yàn)

1 問(wèn)題的提出

其中f(x):Rn→R1是一階連續(xù)可微函數(shù)。

求解問(wèn)題(1)的共軛梯度算法,結(jié)構(gòu)簡(jiǎn)單,收斂速度快,存儲(chǔ)量小,適于求解大規(guī)模問(wèn)題[1-2]。記憶梯度法[3]是共軛梯度法的一種變形和改進(jìn),它具有比共軛梯度法更快的收斂速度。文獻(xiàn)[4-6]利用記憶梯度法的基本思想,增加記憶項(xiàng)的項(xiàng)數(shù),引入了超記憶梯度算法。由于這類(lèi)方法在迭代中較多地利用了已經(jīng)得到的目標(biāo)函數(shù)的某些信息,因而具有比梯度法更快的收斂速度[7]。但是記憶梯度法在每一次迭代中需要作一次二維精確搜索,超記憶梯度法

考慮無(wú)約束最優(yōu)化問(wèn)題在每一次迭代中需要作一次多維精確搜索,這一點(diǎn)很不理想,為此很多文獻(xiàn)[8-13]對(duì)算法進(jìn)行了改進(jìn)。最近,Shi等[14]結(jié)合信賴域技術(shù)提出了一類(lèi)具有全局收斂性和數(shù)值效果比FR、PRP、HS、CD、DY共軛梯度算法好的新超記憶梯度單調(diào)下降算法。

非單調(diào)技術(shù)由于其有利于求解全局最優(yōu)解和算法的快速收斂而受到關(guān)注[15-19]。Gu等[16]改進(jìn)傳統(tǒng)非單調(diào)技術(shù)中的參考值的選取,提出了一種新的非單調(diào)線搜索技術(shù):

這里δ∈(0,1),η∈(0,1)是兩個(gè)參數(shù)。

本文將結(jié)合Gu的非單調(diào)技術(shù),對(duì)時(shí)貞軍提出的超記憶梯度算法改進(jìn),設(shè)計(jì)非單調(diào)超記憶梯度算法,同時(shí)為了進(jìn)一步減少算法的存貯量和計(jì)算量,提出基于修正擬牛頓方程的Bk的一種稀疏對(duì)角修正形式,即基于Wei等[20]提出的新的修正擬牛頓方程

特別地,當(dāng)Ak=0時(shí),則對(duì)應(yīng)于擬牛頓方程。

基于式(4),給出Bk的修正形式如下:設(shè)Bk-1為對(duì)角稀疏正定矩陣,令Bk=Bk-1+ΔBk-1,其中ΔBk-1為對(duì)角矩陣,為保證Bk的正定性,限制Bk= diag(b1k,b2k,…,bnk)取值,即滿足

Bk近似滿足修正擬牛頓方程:

2 算 法

基于信賴域技術(shù)和修正擬牛頓方程的非單調(diào)超記憶梯度算法(SM):

步驟1 取x0∈Rn,ρ∈(0,1),μ∈(0,1),m≥2,B0=In,0＜＜為常數(shù),令k:=0。

步驟2 如果‖gk‖=0,則停止迭代；否則,轉(zhuǎn)步驟2。

步驟3 定義mk滿足0≤mk≤min{k,m}。

步驟4 xk+1=xk+Pk(αk),其中αk是{1,ρ,ρ2,…}中滿足下式的最大者:

其中Dk由式(3)確定,Pk(α)=Vkyk(α),且yk(α)是下列子問(wèn)題的解:

這里y∈Rmk+1,dk=-B-1kgk,Vk=(dk,Δxk-1,…, Δxk-mk)∈Rn×(mk+1),其中Δxk-1=xk-xk-1,…, Δxk-mk=xk-mk+1-xk-mk。

步驟5 利用式(8)修正Bk得到Bk+1,令k:= k+1,轉(zhuǎn)步驟2。

注1由于Ak有三種選擇(5)、(6)及Ak=0,因此有三種不同的校正形式,對(duì)應(yīng)三種不同的算法。當(dāng)η=0時(shí),則Dk=fk,說(shuō)明算法是單調(diào)下降算法。

注2新算法的主要工作量集中在求解子問(wèn)題(10),而由于子問(wèn)題(10)維數(shù)一般不高(一般取m =2,3即可)且Bk是實(shí)對(duì)稱(chēng)正定對(duì)角矩陣,因此子問(wèn)題(10)的求解相對(duì)變得簡(jiǎn)便。

3 全局收斂性

首先對(duì)目標(biāo)函數(shù)f(x)做如下假設(shè):

(H1)目標(biāo)函數(shù)f(x)在Rn上有下界。

(H2)目標(biāo)函數(shù)的梯度g(x)=?f(x)在包含水平集L(x0)={x∈Rnf(x)≤f(x0)}的開(kāi)凸集B上Lipschitz連續(xù),即存在L＞0滿足:‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈B。

引理3假設(shè)條件(H1)和(H2)成立,{xk}是由算法產(chǎn)生的無(wú)窮點(diǎn)列,則有

(i)f(xk+1)≤Dk,?k；

(ii)f(xk)≤Dk,?k；

(iii){Dk}是單調(diào)不增序列。

證明由式(9)和引理1知

4 線性收斂速度和超線性收斂速度

線性收斂速度分析需要以下假設(shè)條件:

(H3)f(x)是強(qiáng)凸函數(shù),即存在常數(shù)r＞0滿足

定理2設(shè){xk,αk,gk}是由算法產(chǎn)生的序列,假設(shè)(H1)～(H3)成立,則存在θ∈(0,1)滿足

f(xk)-f(x*)≤θk(f(x0)-f(x*)),?k.即{fk}R-線性收斂于f(x*)。

超線性收斂速度分析需要以下假設(shè)條件:

(H4)算法產(chǎn)生點(diǎn)列{xk}收斂于x*,?2f(x*)是一個(gè)正定矩陣,且f(x)在N(x*,ε0)={x‖xx*‖≤ε0}二階連續(xù)可微。

(H5)算法中dk=-gk滿足

引理4 假設(shè)條件(H4),(H5)成立,{xk}是由算法產(chǎn)生的無(wú)窮迭代點(diǎn)列,則存在k′使得αk=1,?k≥k′。

定理3 假設(shè)條件(H3),(H4),(H5)成立, {xk}是由算法產(chǎn)生的無(wú)窮迭代點(diǎn)列,則{xk}超線性收斂于x*。

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

從網(wǎng)站:www.ici.ro/camo/neculai/SCALCG/ testuo.paf選擇了2個(gè)算例,利用Matlab7.0編制程序在PIII.933機(jī)器上對(duì)本文算法進(jìn)行數(shù)值試驗(yàn),并與其單調(diào)算法進(jìn)行比較。

本文的算法記為SM。當(dāng)Ak取(5)、(6)及Ak= 0時(shí)對(duì)應(yīng)的算法為SM(1)、SM(2)及SM(0),算法SM(1)、SM(2)及SM(0)中取ηk≡0分別對(duì)應(yīng)其單調(diào)算法,分別記為MSM(1)、MSM(2)及MSM(0)。當(dāng)Bk≡In時(shí),記算法為SGM,算法SGM中取η≡0對(duì)應(yīng)其單調(diào)算法,記為MSGM。當(dāng)Bk分別用DFP, BFGS公式修正時(shí),算法分別記為DSM、BSM,算法DSM、BSM中取η≡0分別對(duì)應(yīng)其單調(diào)算法即為文獻(xiàn)[14]中算法,分別記為MDSM、MBSM。

算法中取η=0.36,μ=0.38,ρ=0.5,m=3,B0=In,和ˉb取為變化形式,即

初始點(diǎn)x0=(0.2,0.2,…,0.2)T,fopt=0。計(jì)算結(jié)果見(jiàn)表1(其中,“***”表示迭代時(shí)間大于300 s或者迭代次數(shù)超過(guò)3000仍未達(dá)到停機(jī)標(biāo)準(zhǔn))。

表1 例1的數(shù)值結(jié)果Table 1 Numerical results of example 1

表2 例2的數(shù)值結(jié)果Table 1 Numerical results of example 2

6 結(jié) 論

本文基于信賴域技術(shù)和修正的擬牛頓方程,結(jié)合Neng-Zhu Gu非單調(diào)策略,設(shè)計(jì)了新的求解無(wú)約束最優(yōu)化問(wèn)題的非單調(diào)超記憶梯度算法,分析了算法的收斂性和收斂速度。新算法Bk用公式(8)校正比用BFGS公式和DFP公式校正在計(jì)算大型例子需要更少的存儲(chǔ)量、計(jì)算量、迭代時(shí)間和迭代次數(shù),

目標(biāo)函數(shù)值更接近于最優(yōu)值,問(wèn)題規(guī)模越大,維數(shù)越高,新算法優(yōu)勢(shì)越明顯,因此新算法更適合于大規(guī)模問(wèn)題的計(jì)算。另外,非單調(diào)算法的數(shù)值表現(xiàn)優(yōu)于單調(diào)算法。

[1] 袁亞湘,孫文渝.最優(yōu)化理論與方法[M].北京:科學(xué)出版社,1997.

[2] 戴彧虹,袁亞湘.非線性規(guī)劃共軛梯度算法[M].上海:上?？茖W(xué)技術(shù)出版社,2000.

[3] MIELE A,CANTRELL J W.Memory gradient method for the minimization of functions[J].JOTA,1969,3:459-470.

[4] CRAGG E E,LEVY A V.Study on a memory gradient method for the minimization of functions[J].JOTA, 1969,4(3):191-205.

[5] WOLFE M A.A quasi-Newton method with memory for unconstrained function minimization[J].J Inst Maths Applics,1975,15:85-94.

[6] WOLFE M A,VIAZMINSKY C.Super-memory descent methods for unconstrained function minimization[J].JOTA,1976,18:455-468.

[7] 孫麟平.無(wú)約束極小化自適應(yīng)多信息下降算法[J].高校計(jì)算數(shù)學(xué)學(xué)報(bào),1982,14(2):107-114.

SUN Lin-ping.Adaptive supermemory descent method for unconstrained minimization[J].Numerical Mathematics:A Journal of Chinese Universities,1982,14(2): 107-114.

[8] 趙慶禎.一個(gè)改進(jìn)的超記憶梯度算法及其斂速估計(jì)[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),1983,6(3):376-385.

ZHAO Qing-zhen.Convergence and rate of convergence of an improved supermemory gradient method[J].Acta Mathematicae Applicatae Sinica,1983,6(3):376-385.

[9] 胡宗英.一個(gè)改進(jìn)的記憶梯度算法[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),1989,2:173-179.

HU Zong-ying.A modified memory gradient algorithm [J].Numerical Mathematics:A Journal of Chinese Universities,1989,2:173-179.

[10] 時(shí)貞軍.無(wú)約束優(yōu)化的超記憶梯度算法[J].工程數(shù)學(xué)學(xué)報(bào),2000,17(2):99-104.

SHI Zhen-jun.A supermemory gradient method for un-constrained optimization problem[J].Chinese Journal of Engineering Mathematics,2000,17(2):99-104.

[11] 時(shí)貞軍.改進(jìn)HS共軛梯度算法及其全局收斂性[J].計(jì)算數(shù)學(xué),2001,23(4):393-406.

SHI Zhen-jun.Modified HS conjugate gradient method and its global convergence[J].Mathematica Numerica Sinica,2001,23(4):393-406.

[12] 孫清瀅,劉新海.結(jié)合廣義Armijo步長(zhǎng)搜索的一類(lèi)新的三項(xiàng)共軛梯度算法及其收斂特征[J].計(jì)算數(shù)學(xué),2004,26(1):25-36.

SUN Qing-ying,LIU Xin-hai.Global convergence results of a new three terms conjugate gradient method with generalized Armijo step size rule[J].Mathematica Numerica Sinica,2004,26(1):25-36.

[13] SUN Qingying.Global convergence results of a Thtee term memory gradient method with non-monotone line search technique[J].ACTA Mathematics Scientis, 2005,25B(1):170-178.

[14] SHI Zhen-jun,SHEN Jie.A new class of super-memory gradient methods[J].Applied Mathematicd and Computation,2006,183:748-760.

[15] GRIPPO L,LAMPARIELLO F,LUCIDI S.A nonmonotone line search technique for Newton?s method[J]. SIAM J,NUMER ANAL,1986,23(4):707-716.

[16] GU Neng-zhu,MO Jiang-tao.Incorporating nonmonotone strategies inti the trust region method for unconstrained optimization[J].Computers&Mathematics withApplications,2007,doi:10.1016/j.camwa. 2007.08.038.

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

SUN Qing-ying,CUI Bin,WANG Chang-yu.Global convergence of a Lampariello modified diagonal-sparse quasi-Newton method with new non-monotone step size rule[J].Mathematica Numerica Sinica,2008,30(3): 255-268.

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

SUN Qing-ying,ZHENG Yan-mei.Global convergence results of Lampariello modified diagonal-sparse quasi-Newton method with larger non-monotone-step size rule [J].Advances in Mathematics,2008,37(3):311-320.

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

[20] WEI Z,LI G,QI L.New quasi-Newton methords for unconstrained optimizationproblems[J].Applied Mathematics and Computation,2006,175:1156-1188.

(編輯 修榮榮)

A non-monotone super-memory gradient method based on trust region technique and modified quasi-Newton equation

GONG En-long1,CHEN Shuang-shuang2,SUN Qing-ying2,CHEN Ying-mei2
(1.Qingdao Hotel Management College,Qingdao 266100,China；
2.College of Science in China University of Petroleum,Qingdao 266580,China)

Based on trust region technique and modified quasi-Newton equation,by combining with Neng-Zhu Gu non-monotone strategy,a new super-memory gradient method for unconstrained optimization problem was presented.The global and convergence properties of the new method were proved.It saves the storage and computation of some matrixes in its iteration, and is suitable for solving large scale optimization problems.The numerical results show that the new method is effective.

super-memory gradient method；non-monotone step rule；convergence；convergence rate；numerical experiment

O 221.2

A

1673-5005(2013)02-0191-06

10.3969/j.issn.1673-5005.2013.02.032

2012-09-05

國(guó)家自然科學(xué)基金項(xiàng)目(61201455)；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)(10CX04044A；11 CX06087A)

宮恩龍(1969-),男,副教授,碩士,從事數(shù)學(xué)規(guī)劃研究。E-mail:GongEnlong@163.com。