基于信赖域技术和修正拟牛顿方程的非单调超记忆梯度算法

宫恩龙,陈双双,孙清滢,陈颖梅

(1.青岛酒店管理职业技术学院,山东青岛 266100；2.中国石油大学理学院,山东青岛 266580)

基于信赖域技术和修正拟牛顿方程的非单调超记忆梯度算法

宫恩龙1,陈双双2,孙清滢2,陈颖梅2

(1.青岛酒店管理职业技术学院,山东青岛 266100；2.中国石油大学理学院,山东青岛 266580)

基于信赖域技术和修正拟牛顿方程,结合Neng-Zhu Gu非单调策略,设计新的求解无约束最优化问题的非单调超记忆梯度算法,分析算法的收敛性和收敛速度。新算法每次迭代节约了矩阵的存储量和计算量,算法稳定,适于求解大规模问题。数值试验结果表明新算法是有效的。

超记忆梯度算法；非单调规则；收敛性；收敛速度；数值试验

1 问题的提出

其中f(x):Rn→R1是一阶连续可微函数。

求解问题(1)的共轭梯度算法,结构简单,收敛速度快,存储量小,适于求解大规模问题[1-2]。记忆梯度法[3]是共轭梯度法的一种变形和改进,它具有比共轭梯度法更快的收敛速度。文献[4-6]利用记忆梯度法的基本思想,增加记忆项的项数,引入了超记忆梯度算法。由于这类方法在迭代中较多地利用了已经得到的目标函数的某些信息,因而具有比梯度法更快的收敛速度[7]。但是记忆梯度法在每一次迭代中需要作一次二维精确搜索,超记忆梯度法

考虑无约束最优化问题在每一次迭代中需要作一次多维精确搜索,这一点很不理想,为此很多文献[8-13]对算法进行了改进。最近,Shi等[14]结合信赖域技术提出了一类具有全局收敛性和数值效果比FR、PRP、HS、CD、DY共轭梯度算法好的新超记忆梯度单调下降算法。

非单调技术由于其有利于求解全局最优解和算法的快速收敛而受到关注[15-19]。Gu等[16]改进传统非单调技术中的参考值的选取,提出了一种新的非单调线搜索技术:

这里δ∈(0,1),η∈(0,1)是两个参数。

本文将结合Gu的非单调技术,对时贞军提出的超记忆梯度算法改进,设计非单调超记忆梯度算法,同时为了进一步减少算法的存贮量和计算量,提出基于修正拟牛顿方程的Bk的一种稀疏对角修正形式,即基于Wei等[20]提出的新的修正拟牛顿方程

特别地,当Ak=0时,则对应于拟牛顿方程。

基于式(4),给出Bk的修正形式如下:设Bk-1为对角稀疏正定矩阵,令Bk=Bk-1+ΔBk-1,其中ΔBk-1为对角矩阵,为保证Bk的正定性,限制Bk= diag(b1k,b2k,…,bnk)取值,即满足

Bk近似满足修正拟牛顿方程:

2 算 法

基于信赖域技术和修正拟牛顿方程的非单调超记忆梯度算法(SM):

步骤1 取x0∈Rn,ρ∈(0,1),μ∈(0,1),m≥2,B0=In,0＜＜为常数,令k:=0。

步骤2 如果‖gk‖=0,则停止迭代；否则,转步骤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,转步骤2。

注1由于Ak有三种选择(5)、(6)及Ak=0,因此有三种不同的校正形式,对应三种不同的算法。当η=0时,则Dk=fk,说明算法是单调下降算法。

注2新算法的主要工作量集中在求解子问题(10),而由于子问题(10)维数一般不高(一般取m =2,3即可)且Bk是实对称正定对角矩阵,因此子问题(10)的求解相对变得简便。

3 全局收敛性

首先对目标函数f(x)做如下假设:

(H1)目标函数f(x)在Rn上有下界。

(H2)目标函数的梯度g(x)=∇f(x)在包含水平集L(x0)={x∈Rnf(x)≤f(x0)}的开凸集B上Lipschitz连续,即存在L＞0满足:‖g(x)-g(y)‖≤L‖x-y‖,∀x,y∈B。

引理3假设条件(H1)和(H2)成立,{xk}是由算法产生的无穷点列,则有

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

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

(iii){Dk}是单调不增序列。

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

4 线性收敛速度和超线性收敛速度

线性收敛速度分析需要以下假设条件:

(H3)f(x)是强凸函数,即存在常数r＞0满足

定理2设{xk,αk,gk}是由算法产生的序列,假设(H1)～(H3)成立,则存在θ∈(0,1)满足

f(xk)-f(x*)≤θk(f(x0)-f(x*)),∀k.即{fk}R-线性收敛于f(x*)。

超线性收敛速度分析需要以下假设条件:

(H4)算法产生点列{xk}收敛于x*,∇2f(x*)是一个正定矩阵,且f(x)在N(x*,ε0)={x‖xx*‖≤ε0}二阶连续可微。

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

引理4 假设条件(H4),(H5)成立,{xk}是由算法产生的无穷迭代点列,则存在k′使得αk=1,∀k≥k′。

定理3 假设条件(H3),(H4),(H5)成立, {xk}是由算法产生的无穷迭代点列,则{xk}超线性收敛于x*。

5 数值试验

从网站:www.ici.ro/camo/neculai/SCALCG/ testuo.paf选择了2个算例,利用Matlab7.0编制程序在PIII.933机器上对本文算法进行数值试验,并与其单调算法进行比较。

本文的算法记为SM。当Ak取(5)、(6)及Ak= 0时对应的算法为SM(1)、SM(2)及SM(0),算法SM(1)、SM(2)及SM(0)中取ηk≡0分别对应其单调算法,分别记为MSM(1)、MSM(2)及MSM(0)。当Bk≡In时,记算法为SGM,算法SGM中取η≡0对应其单调算法,记为MSGM。当Bk分别用DFP, BFGS公式修正时,算法分别记为DSM、BSM,算法DSM、BSM中取η≡0分别对应其单调算法即为文献[14]中算法,分别记为MDSM、MBSM。

算法中取η=0.36,μ=0.38,ρ=0.5,m=3,B0=In,和¯b取为变化形式,即

初始点x0=(0.2,0.2,…,0.2)T,fopt=0。计算结果见表1(其中,“***”表示迭代时间大于300 s或者迭代次数超过3000仍未达到停机标准)。

表1 例1的数值结果Table 1 Numerical results of example 1

表2 例2的数值结果Table 1 Numerical results of example 2

6 结 论

本文基于信赖域技术和修正的拟牛顿方程,结合Neng-Zhu Gu非单调策略,设计了新的求解无约束最优化问题的非单调超记忆梯度算法,分析了算法的收敛性和收敛速度。新算法Bk用公式(8)校正比用BFGS公式和DFP公式校正在计算大型例子需要更少的存储量、计算量、迭代时间和迭代次数,

目标函数值更接近于最优值,问题规模越大,维数越高,新算法优势越明显,因此新算法更适合于大规模问题的计算。另外,非单调算法的数值表现优于单调算法。

[1] 袁亚湘,孙文渝.最优化理论与方法[M].北京:科学出版社,1997.

[2] 戴彧虹,袁亚湘.非线性规划共轭梯度算法[M].上海:上海科学技术出版社,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] 孙麟平.无约束极小化自适应多信息下降算法[J].高校计算数学学报,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].应用数学学报,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].高等学校计算数学学报,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] 时贞军.无约束优化的超记忆梯度算法[J].工程数学学报,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].计算数学,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] 孙清滢,刘新海.结合广义Armijo步长搜索的一类新的三项共轭梯度算法及其收敛特征[J].计算数学,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] 孙清滢,崔彬,王长钰.新非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法[J].计算数学, 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] 孙清滢,郑艳梅.大步长非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法的全局收敛性[J].数学进展,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

国家自然科学基金项目(61201455)；中央高校基本科研业务费专项(10CX04044A；11 CX06087A)

宫恩龙(1969-),男,副教授,硕士,从事数学规划研究。E-mail:GongEnlong@163.com。