资源描述：
《基于新锥模型的带固定步长的非单调自适应信赖域算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、基于新锥模型的带固定步长的非单调自适应信赖域算法朱帅基金项目：山西省自然科学基金（2008011013）作者简介：朱帅（1980—），男，硕士，研究方向为非线性规划。赵绚2王希云3（1.山西大同大学工学院,山西大同,037003；2，3.太原科技大学应用科学学院,山西太原,030024）摘要：本文对无约束优化问题提出了一类基于新锥模型的带固定步长的非单调自适应信赖域算法.利用文[6]提出的固定步长算法,在适当的条件下,证明了此算法的全局收敛性和超线性收敛性.关键词：无约束优化；非单调技术；自适应信赖域算法
2、；固定步长；新锥模型中图分类号：O221.2文献标识码：A1.引言考虑无约束优化问题:,其中二次连续可微.传统的信赖域算法一般采用二次模型逼近,但对于一些非二次性态较强、曲率变化剧烈的函数,用二次函数模型逼近效果较差.为此,于1980年提出了锥模型方法.倪勤[2]提出了锥模型信赖域子问题的一种新可行集,后将形成的子问题称为新锥模型信赖域子问题.ShaoJianQu和KeCunZhang[3]等人提出了一类基于锥模型的非单调信赖域算法.最近,Ju-LiangZhang、Xiang-SunZhang[4]提出
3、了一种非单调自适应信赖域算法.另外,王希云、仝建[6]提出了一种带固定步长的非单调自适应信赖域算法.本文将带固定步长的信赖域算法应用到新锥模型信赖域算法中,提出了一种新的算法,数值试验表明算法是有效的.2.算法选取下面的子问题计算试探步：(1)其中,为一个在0到1之间的一个正数,,，为在处的梯度,和分别是维向量和矩阵,是信赖域半径.由文献[2]我们知道,上述问题可以分成如下三种情况考虑:⑴当时,子问题转换为8⑵当时,子问题转换为⑶当时,子问题转换为令,(2)其中,而定义为:(3)其中,是常数.(4)其中是
4、非负整数.采用修正.算法1Step0给定,,,令其中是阶单位矩阵.Step1计算,如果满足,则终止;否则转step2.Step2用折线法[5]求解子问题(1)得近似解.Step3依据(2)式计算.Step4令,8Step5利用公式(4)计算Step6令,更新[7]和[7]:其中,.依据(3)式计算,转Step1.1.全局收敛性记:,.H1水平集是有界的.H2在上Lipschitz连续.H3序列,一致有界,即对有.H4假设.引理3.1[3].引理3.2设H1 满足,则单调下降且收敛.证明:(5)由(3)式有
5、所以则(6)代入(5)得因此,序列单调非增,由H3.1可知,所以收敛.证毕引理3.3[4]设H3满足,则满足:(7)8引理3.4设H3和H4满足,则有:.(8)证明:当时,由H4知(8)成立.当时,根据Step4,知:,由于,所以.(9)对于,若,则由上式得:(10)根据引理3.2,单调下降且收敛,因此(11)若的情况由H4可得引理结论.根据(10)和引理3.3得:其中.由(11)式知:.(12)由引理3.2知:.(13)令,由数学归纳法,可得:,.(14)采用推导(12)式和(13)式的方法可得(14)
6、式对于有.(15)8由,所以有:(16)由的连续性,可得:.(17)又由式,两边取极限可得:.(18)所以有.结合假设H3.4,对,有.证毕.引理3.5[4]设H1-H4满足,则有定理3.1设H1-H4满足,则有:.(19)证明:反证法.若和无限子列使得,令.,使得对于有,,由引理3.1知,有下式成立:.这表明对于,,这与引理3.4中(18)式矛盾,故定理成立.证毕1.超线性收敛性下面,讨论本章算法的超线性收敛性,假设下面条件成立.H5当充分大时,矩阵是可逆的,若,则本算法中.H6成立.定理4.1若H1-
7、H6成立,算法产生的序列收敛于,且正定,在的邻域内Lipschitz连续,则序列超线性收敛于.8证明:根据H5,当充分大时,因为,所以且有界，所以有所以当充分大时(20)令由引理3.5可得(21)则由(20)、(21)式得.(22)所以.(23)由引理3.1,有.(24)由式(23)和式(24)知,当充分大时.因此,算法退化为拟牛顿算法,根据文[8]中定理5.5.1得:算法产生的序列超线性收敛于.证毕1.数值试验本节我们对以下三个函数进行了数值试验,在相同的条件下与文献[6]中的算法2进行了比较,在Mat
8、lab7.0环境下编制程序,试验结果见表1.参数选择如下:.8终止条件为:.例1Rosenbrockfunction例2Extendedrosenbrockfunction；例3Extendedpowellsingularfunction；说明:表1中,分别表示函数值和梯度值的迭代次数.n表示问题的维数.Problem表示所选择的测试函数,表示试验所求得的最优值,运行时间为CPU(单位为秒).表1数值试验结果比较Teb1The
