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

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

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

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

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

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

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

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

1 問題的提出

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

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

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

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

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

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

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

基于式(4),給出Bk的修正形式如下:設(shè)Bk-1為對角稀疏正定矩陣,令Bk=Bk-1+ΔBk-1,其中ΔBk-1為對角矩陣,為保證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(α)是下列子問題的解:

這里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,因此有三種不同的校正形式,對應(yīng)三種不同的算法。當(dāng)η=0時,則Dk=fk,說明算法是單調(diào)下降算法。

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

3 全局收斂性

首先對目標(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)}的開凸集B上Lipschitz連續(xù),即存在L＞0滿足:‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈B。

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

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

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

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

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

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

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

(H3)f(x)是強凸函數(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)生點列{xk}收斂于x*,?2f(x*)是一個正定矩陣,且f(x)在N(x*,ε0)={x‖xx*‖≤ε0}二階連續(xù)可微。

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

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

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

5 數(shù)值試驗

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

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

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

初始點x0=(0.2,0.2,…,0.2)T,fopt=0。計算結(jié)果見表1(其中,“***”表示迭代時間大于300 s或者迭代次數(shù)超過3000仍未達到停機標(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è)計了新的求解無約束最優(yōu)化問題的非單調(diào)超記憶梯度算法,分析了算法的收斂性和收斂速度。新算法Bk用公式(8)校正比用BFGS公式和DFP公式校正在計算大型例子需要更少的存儲量、計算量、迭代時間和迭代次數(shù),

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

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

[2] 戴彧虹,袁亞湘.非線性規(guī)劃共軛梯度算法[M].上海:上海科學(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] 孫麟平.無約束極小化自適應(yīng)多信息下降算法[J].高校計算數(shù)學(xué)學(xué)報,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] 趙慶禎.一個改進的超記憶梯度算法及其斂速估計[J].應(yīng)用數(shù)學(xué)學(xué)報,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] 胡宗英.一個改進的記憶梯度算法[J].高等學(xué)校計算數(shù)學(xué)學(xué)報,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] 時貞軍.無約束優(yōu)化的超記憶梯度算法[J].工程數(shù)學(xué)學(xué)報,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] 時貞軍.改進HS共軛梯度算法及其全局收斂性[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步長搜索的一類新的三項共軛梯度算法及其收斂特征[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] 孫清瀅,崔彬,王長鈺.新非單調(diào)線搜索規(guī)則的Lampariello修正對角稀疏擬牛頓算法[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] 孫清瀅,鄭艷梅.大步長非單調(diào)線搜索規(guī)則的Lampariello修正對角稀疏擬牛頓算法的全局收斂性[J].數(shù)學(xué)進展,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

國家自然科學(xué)基金項目(61201455)；中央高校基本科研業(yè)務(wù)費專項(10CX04044A；11 CX06087A)

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