基于新锥模型的带固定步长的非单调自适应信赖域算法

1基于新锥模型的带固定步长的非单调自适应信赖域算法朱帅1赵绚2王希云3（1.山西大同大学工学院,山西大同,037003；2，3.太原科技大学应用科学学院,山西太原,030024）摘要：本文对无约束优化问题提出了一类基于新锥模型的带固定步长的非单调自适应信赖域算法.利用文[6]提出的固定步长算法,在适当的条件下,证明了此算法的全局收敛性和超线性收敛性.关键词：无约束优化；非单调技术；自适应信赖域算法；固定步长；新锥模型中图分类号：O221.2文献标识码：A1.引言考虑无约束优化问题:minnxRfx,其中:nfRR二次连续可微.传统的信赖域算法一般采用二次模型逼近fx,但对于一些非二次性态较强、曲率变化剧烈的函数,用二次函数模型逼近效果较差.为此,[1]Dnvidon于1980年提出了锥模型方法.倪勤[2]提出了锥模型信赖域子问题的一种新可行集,后将形成的子问题称为新锥模型信赖域子问题.ShaoJianQu和KeCunZhang[3]等人提出了一类基于锥模型的非单调信赖域算法.最近,Ju-LiangZhang、Xiang-SunZhang[4]提出了一种非单调自适应信赖域算法.另外,王希云、仝建[6]提出了一种带固定步长的非单调自适应信赖域算法.本文将带固定步长的信赖域算法应用到新锥模型信赖域算法中,提出了一种新的算法,数值试验表明算法是有效的.2.算法选取下面的子问题计算试探步：21min121..TTkkkTTkkgddBddbdbdstd(1)其中0,,1nnTkkBSBdRdSdRbd,0为一个在0到1之间的一个正数,kkkdfxdfx,kkxff，kkxgg为xf在kx处的梯度,kb和kB分别是n维向量和nn矩阵,0k是信赖域半径.由文献[2]我们知道,上述问题可以分成如下三种情况考虑:⑴当01kkb时,子问题转换为基金项目：山西省自然科学基金（2008011013）作者简介：朱帅（1980—），男，硕士，研究方向为非线性规划。2min..kkdstd⑵当01kkb时,子问题转换为0min..1kTkkdstdbd且⑶当01kkb时,子问题转换为00min..11kkTTkkddstbdbd或令kklkkkkkkkffxdxxd,kkkkkkpredxxd(2)其中max0kjlkffjmk,而mk定义为:110min11,kkifmkmkMif(3)其中0,1,1M是常数.1pkkkcBg(4)其中0,1,cp是非负整数.kB采用BFGS修正.算法1Step0给定00,0,0nxR,0,1,1M,令0000,0,,kmkffxBI其中I是n阶单位矩阵.Step1计算kg,如果满足kg,则终止;否则转step2.Step2用折线法[5]求解子问题(1)得近似解kd.Step3依据(2)式计算k.Step4令1kkkkkkkkxdxxd,,0,1TkkkTkkkgddBd3Step5利用公式(4)计算1k1111111max,4,,1pkkkkkkpkkkcBgdcBgppStep6令:1kk,更新kb[7]和kB[7]:111,TTkkkkkkkkkkTTTkkkkkkkyyBddBbgBBgddydBd其中1211,0,1,0kkTTTkkkkkkkkffffgdgdgd,31kkkygg.依据(3)式计算mk,转Step1.3.全局收敛性记:{:}kJk,{:}kIk.H1水平集00{|()}nxRfxf是有界的.H2()gx在0上Lipschitz连续.H3序列{}kB,kb一致有界,即10,M对,k有11,kkBMbM.H4假设lim()0kkkkJd.引理3.1[3]0min,/,0kkkkkkkkpreddggB.引理3.2设H1满足,则{}klf单调下降且收敛.证明:11011max,maxkkjlkjmkfxfxfx(5)由(3)式有11kmkm所以kmkm11则kljkkmjjkkmjxfxfxf0110maxmax(6)代入(5)得klklkklxfxfxfxf,max11因此,序列klf单调非增,由H3.1可知01xLxfkl,所以klf收敛.证毕引理3.3[4]设H3满足,则0c满足:,1,2,kkdcgk(7)4引理3.4设H3和H4满足,则有:lim0kkd.(8)证明:当{:}kkJk时,由H4知(8)成立.当{:}kkIk时,根据Step4,知:()0()klkkkkkffxdud,由于()0kkd,所以()()klkkkkffxdd.(9)对于km,若1klI,则由上式得:111()kkkkllllffd(10)根据引理3.2,{}klf单调下降且收敛,因此11lim()0kkllkd(11)若1klI的情况由H4可得引理结论.根据(10)和引理3.3得:2111111111()min,min1,kkkkkkklllllllgdgdcMcB21klMd其中11min1,McMc.由(11)式知:1lim0klkd.(12)由引理3.2知:1limlimkkllkkff.(13)令2ˆkkmll,由数学归纳法,可得:1jlim0kljkd,limlimkkljlkkff.(14)采用推导(12)式和(13)式的方法可得(14)式对于k有ˆˆ11ˆˆˆˆ111kkkkkklklkklljljljjjjIjJxxdd.(15)5由ˆ()11lkkM,所以有:ˆ1lim0kklkxx(16)由()fx的连续性,可得:ˆ1limlimlimkkkllkkkfff.(17)又由式1()()klkkkffxd,两边取极限可得:lim()0kkkd.(18)所以有lim0kkd.结合假设H3.4,对k,有lim0kkd.证毕.引理3.5[4]设H1-H4满足,则有22pkkkcpredgB定理3.1设H1-H4满足,则有:lim0kkg.(19)证明:反证法.若00和无限子列{}ik使得0ikg,令0|ikKkg.0,使得对于kK有,k,由引理3.1知,kK有下式成立:min,kkkkkgpredgB0001min,0M.这表明对于kK,0()0kkd,这与引理3.4中(18)式矛盾,故定理成立.证毕4.超线性收敛性下面,讨论本章算法的超线性收敛性,假设下面条件成立.H5当k充分大时,矩阵kB是可逆的,若111kkkTkKkBgbBg,则本算法中111kkkTkKkBgdbBg.H62()lim0kkkkkBfxdd成立.定理4.1若H1-H6成立,算法产生的序列{}kx收敛于*x,且2*()fx正定,在*x的邻域内Lipschitz连续,则序列{}kx超线性收敛于*x.6证明:根据H5,当k充分大时,111kkkTkKkBgdbBg因为1kbM,所以111kTkkOdbd且,kkgB有界，所以有kkpredd22121TTTTkkkkkkkkkkkTTkkkkgddBdgddBdodbdbd所以当k充分大时|())|kkkkkffxdpredd2221122TTTTkkkkkkkkkkkkgddfxdgddBdodod(20)令2pkcB由引理3.5可得2kkkpreddd(21)则由(20)、(21)式得1kkkkkffxdpredd()()()kkkkkkkffxdpreddpredd22kkodd.(22)所以lim1kkkkkkffxdpredd.(23)由引理3.1,有()()()()klkkkkkkkkkkffxdffxdpreddpredd.(24)由式(23)和式(24)知,当k充分大时k.因此,算法退化为拟牛顿算法,根据文[8]中定理5.5.1得:算法产生的序列{}kx超线性收敛于*x.证毕5.数值试验本节我们对以下三个函数进行了数值试验,在相同的条件下与文献[6]中的算法2进行了比较,在Matlab7.0环境下编制程序,试验结果见表1.参数选择如下:0001,0.75,4,0.02,0.01,MBI.7终止条件为:610kg.例1Rosenbrockfunction212212)1()(100xxxxf例2Extendedrosenbrockfunction2/12122212)1()(100niiiixxxxf；2n例3Extendedpowellsingularfunction4/144344142441422434)(10)2()(5)10(niiiiiiiiixxxxxxxxxf；4n说明:表1中nf,ng分别表示函数值和梯度值的迭代次数.n表示问题的维数.Problem表示所选择的测试函数,f表示试验所求得的最优值,运行时间为CPU(单位为秒).表1数值试验结果比较Teb1Thenumericalresultsofthecomparisonofthetwoalgorithmsproblemn算法1算法2nfngfCPUnfngfCPURosenbrockfunction2871.0314e-0180.078019192.2540e-0180.0560Extendedrosenbrockfunction20991.5106e-0140.078050503.3940e-0130.149540884.2921e-0140.063069692.2621e-0130.25308010102.7925e-0120.17101081083.7812e-040.2983100993.2764e-0140.0780###20016163.1982e-0140.4060###100032325.7262e-010116.2660###Extendedpowellsingularfunction2020202.1364e-0140.235033330.1855e-0130.58408020202.2245e-0130.219056562.2583e-0130.468020042426.1538e-0130.10601021034.6685e-072.4156数值结果分析:本文在文献[6]的基础上改用新锥模型对原问题进行逼近求解,针对上三个代表性的函数，从表1的数值结果可以看出,无论从迭代次数上，还是从计算结果上以及