基于信赖域技术的非单调超记忆梯度算法.pdf

《基于信赖域技术的非单调超记忆梯度算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第4期数学进展Vo1．41，No．4ADVANCESINMATHEMATICSAug．，2012基于信赖域技术的非单调超记忆梯度算法孙清滢，付小燕，高宝，王宣战，徐敏才，刘丽敏(中围油人学学院，青岛，山东，266580)摘要：基于信赖域技术和修正拟牛顿方程，结合ZhangH．C．非单调策略，设计了新的求解无约束最优化问题的非单调超记忆梯度算法，分析了算法的收敛性和收敛速度．数值实验表明算法是有效的，适于求解大规模问题．关键词：超记忆梯度算法；非单调规则；收敛性；收敛速度；数值实验MR(2000)主题分类：90C30／中图分类号：0221．2文献标识码

2、：A文章编号：1000—0917(2012)04—0487—14O引言考虑无约最优化问题m∈iRn．厂()，(1)n。、～⋯其中f(x)：-÷是一阶迎续可微函数．求解问题(1)的共轭梯度算法，结构简单，收敛速度快，存储量小，1卜常适丁求解火规模问题【，．记忆梯度法是共轭梯度法的一种变形和改进，它具有比共轭梯度法更快的收敛速度．文献『31首先介绍了记忆梯度法，其迭代公式为fⅢ=—)Vf(x)+})Ax，1minf(x一030Vf(x)+1Ax)，wu’w1其中5=0，Axk一1=z一z一1，1．随后，文献[4-6]利川记忆梯度法的基本思想，增加记忆项的项数，引

3、入了超记忆梯度算法．由丁这类方法在迭代中较多地利川了已经得到的目标函数的某些信息，冈而具有比记忆梯度法更快的收敛速度，人量的数值例子证明了这一点[7]_其迭代公式为zuVf(x)+∑△，5，(k)：minf(xk-woVf(+i=1)△]其中△一=+1一—一三：=，2，·一，r收稿¨期：2010—03—17．修改稿收到【i期：2010—08—26．金项日：困家自然科学暴余(No．10971118)，中央高校本科业务费专项资金资助(No．10CX04044A)中罔石油人学f东)研究生创新会(No．S10—28)．E—mail：sunqingyingOl@163

4、．COrn488数学进展41卷可见记忆梯度法在每一次迭代中需要做一次二维精确搜索，超记忆梯度法在每一次迭代中需要做一次r+1维精确搜索，这一点很不理想．为此很多文献对算法进行了改进[s-13]．文献f8]首先将超记忆梯度法的多维精确搜索改造为一维非精确搜索，并证明了改进算法具有n步超线性收敛速度，从而使超记忆梯度法在理论上获得支持，使之更具有实用性．最近，Shi和Shen[141结合信赖域技术提出了一类具有全局收敛性和数值效果比FR，PRP，HS，CD，DY共轭梯度算法好的新超记忆梯度单调下降算法．近年米菲单调技术由于其有利于求解全局最优解和算法的快速收敛而

5、受到许多最优化爱好者的青睐．早期的研究是1986年Grippo，Lamparello利Lucidi[15]对牛顿算法提出的单调线搜索技术，即步长满足，(+d)。smJax。厂(一J)+flaVf()d％，(2)其中∈(0，1)，0mkmin{mk一1，M)，M是给定的非负整数．最近，ZhangH．C．和WilliamW．Hager[。]改进了传统非单调线搜索技术中的参考值，提出了新的非单调线搜索技术f(xk+adk)Ck+fl~Vf(zk)dk其中f(xk)，=0(叩一1Q一1Ck一1+f(xk))Q．k>1，、f1，k=0，，叩一1Q一1+1，1．这里吼一

6、1∈【叩mi，‰]，rimi∈【0，1]和r／max∈[‰i，1]是两个参数，卢∈(0，1)为常数．本文将结合ZhangH．C．的非单调技术，对时贞军的超记忆梯度算法进行改进，设计非单调超记忆梯度算法．同时为了进一步减少算法的存贮量和计算量，提出基于修正拟牛顿方程的的一种稀疏对角修正形式，即基于Wei，Li和Qi[17]提出的新的修正拟牛顿方程B+18k：，者日+1k=s，(6)其中=k+Aksk，是含有目标函数二阶信息的一简单矩阵，并给出其满足的条什AkSk=k其中叫=，=2(^一+)+(++9s)，满足s≠0，同时给出Ak的两种取法：(i)％=；(7)(

7、ii)k=裔()．(8)这里我们给出A的另外一种新的取法：(iii)A=赢(9)．(9)4期孙清滢，付小燕，高宝等：基十信赖域技术的非单调超记忆梯度算法489Hp基于式(6)，给出Bk的修正形式如下：设B一1为对角稀疏正定矩阵，令B：B一1+ABk一1，其中ABk一1为对角矩阵，满足●为保证的正定性，限制0<一b，i=1，2，⋯，佗，即mn((6_1+。·(1O)∑}21⋯，b．0一由式(10)知，对i=1，2，⋯，礼，有当s一_≠0时，+如果b碧，则取△6一=碧一b一；如果碧<查，则取△60△61=b一6一1；如果>，则取△6一1=—6一1．当s一1=0时

8、，则取△6一1=0．一一S本文将基于信赖．0域技术和