一类带参数的修正Fletcher-Reeves 共轭梯度法.doc

文库下载 免费文档下载/本文档下载自文库下载网，内容可能不完整，您可以点击以下网址继续阅读或下载：/doc/9d3a0f6d1eb91a37f1115c7c.html一类带参数的修正Fletcher_Reeves共轭梯度法经济金融分析第26卷第3期2009年9月经济数学MATHEMATICSINECONOMICSVol.26,No.3Sep12009一类带参数的修正Fletcher2Reeves共轭梯度法贺战兵1,2,向昭红3(1.湖南师范大学数学与计算机科学学院,湖南长沙410081;2.湖南大众传媒职业技术学院,湖南长沙410100;3.湖南长沙学院信息与计算科学系,湖南长沙410003)3摘要提出了求解无约束优化问题的一类带参数的Fletcher2Reeves共轭梯度法(FR方法).结合Armijo非精确线性搜索技术,.法是有效的.关键词无约束优化问题;共轭梯度法;FR方法;中图分类号O221.2minf(x),xRn,(1)这里函数f(被假写是连续可微的,并且记g(x)=?f(x).众所周知,共轭梯度法是求解无约束优化问题(1)的最有效的方法之一.给定初始近似解x0Rn,新的近似解序列xk由下列迭代公式生成xk 1=xk kdk,k=0,1,2,m.其中k是由某种线性搜索产生的步长,dk是搜索方向,其计算公式为dk=-gk,-gk kdk-1,如果k=0,如果k0.(2)这里gk=g(xk),k是一个参数,k的不同计算公式对应于不同的共轭梯度法,最经典的共轭梯度法有FR方法,PRP方法,HS方法,DY方法等.经典共轭梯度法在使用精确线性搜索并且被用来求解二次凸函数的极小化问题时是下降方法且产生相同的收敛序列,但在求解非二次函数的极小化问题特别在使用非精确线搜索时不一定具有全局收敛性.有许多文献试图通过对经典共轭梯度法的修正来研究其全局收敛性或改善其数值效果1-5.在本文中,我们主要研究FR共轭梯度法的修正及其全局收敛性.众所周知,FR方法是其中最有效的方法之一,k的计算公式为2://doc/9d3a0f6d1eb91a37f1115c7c.htmlpar(3)=k=k2.gk-1文献6证明采用精确线性搜索的FR方法在求解非二次凸函数时是全局收敛的.文献1证明FR3收稿日期:2009204228),男,湖南娄底人,硕士生,副教授作者简介:贺战兵(1969E2mail:80经济数学第26卷了在使用下列的强Wolfe非精确性搜索计算步长k时FR方法保持全局收敛性:Tf(xk kdk)f(xk) kgkdk,T|gkTdk|,|g(xk kdk)dk|(4)这里0.文献7-8进一步将上面的收敛结果推广到=的情形.然而,当FR方22法使用一般的非精确搜索如Armijo搜索与Wolfe搜索时,由于由(2)和(3)产生的方向dk不一定是下降方向,因而FR方法不一定收敛.基于这一考虑,文献5利用文献2提出的在共轭梯度法中结合谱梯度的思想提出了FR方法的一个修正形式,其中搜索方向dk的计算公式为dk=-gk,FR-kgk kdk-1,如果k=0,如果k0,(5)这里.k=2gk-1T(6)并且采用下列的广义Armijo线性搜索来计算步长k;T2f(xk dk,kdk)f(xk)k2k(7)其中1(0,1),20.文献5.本文在文献Armijo线性搜索下的修正形式,.11算法结构设xkRn是当前的近似解,由式(5)/doc/9d3a0f6d1eb91a37f1115c7c.html来计算搜索方向,但k的计算被修正为如下形式:,k=2gk-1T(8)且与k无关.由式(8)与式(5)容易验证这里参数1, Tk2gkdk=-gk.(9)式(9)表明,当gk0时,dk总是函数f(x)在xk处的一个下降方向.特别地,当取=1时,k退化为式(6)中的形式,此时,若进一步采用精确搜索,则k=1,所提出的方法还原为标准的FR方法.利用式(8)和式(5)并且结合Armijo非精确线性搜索技术,提出了下面的带参数的修正共轭梯度方法.算法1步骤0:给定常数,(0,1),选取初始点x0Rn,精度0.令k=0.,得到近似解xk,算法终止,否则转下一步.步骤1:若gkpii=0,1,步骤2:由式(8)计算k,然后由式(8)和式(5)计算dk.选取k为集合2,中满足下列条件kgkTdkf(xk kdk)f(xk) 的最大者.步骤3:令xk 1=xk kdk.(10)第2期贺战兵,向昭红等:一类带参数的修正Fletcher2Reeves共轭梯度法81步骤4:令k=k 1,转步1.注:在以算法1的步2中的线性搜索条件式(10)为标准的Armijo非精确线性搜索条件下,比文献5中的搜索条件(7)更简单且更容易实现,因而在确定k时具有更少的计算量.由式(9)和式(10)可得kgkTdkf(xk),f(xk 1)f(xk) 这表明由算法1产生的序列f(xk)是单调下降的,即算法1为下降算法.(11)21全局收敛性分析首先,假设://doc/9d3a0f6d1eb91a37f1115c7c.htmlpar假设A()函数f(x)在水平集D=xRnf(x)f(x0)上有下界.()函数f(x)在D上是连续可微的且具有Lipschitz,0,使得g(x)-g(y)Lx-,x为分析算法1的全局收敛法,.引理1若假设A,1xk2(12)12),c0,k2kk,k0.kc2dk(13).k=1,(9),k2Tgk=-gkdkgkdk,kgkdk,gkdk.k22gkdk,k2kk=12.dk-1k-1T-1f(xk dk.kdk)-f(xk)k?f(xk)(14),k(0,1)-1-1-1Tf(xk kdk)-f(xk)=k?f(xk kkdk)dk.,-1-1TT-1k?f(xk kkdk)dkk?f(xk)dk;?f(x)Lipschitz,2-1-1L?f(xk)Tdk(-1)gkTdk.kdk?f(xk kkdk)-82)Lk(1-126k/doc/9d3a0f6d1eb91a37f1115c7c.html-1)L2=(1-2.dkdkT2(15)-1)c=min1,(1-L,(14)(15),(13).f(xk),f(xk),(11) k0f(x)k-f(xk 1)k0g-kTkdk=k0gkkk2.(13),(12).=1,(12)Zoutendijk,2k4gk,(12)Zoutendijk.1(15),1.1xk1.A,liminfgk=0.k(16)(17),(16),0,k.gkdk(9),k0,2222dkdk-1k)kdk-kgk22222kgk(k-1 2-kkkgk.4gk,2FR222kdkdk-1 4=42-2gkgk/doc/9d3a0f6d1eb91a37f1115c7c.htmlgkgk2k22k= 4-22gk-1gkgk22kdk-14 2gk-1gk22j2 4g0j=1gj2j2k,22j=0gjkk2k42k22= .2k=dk2kk=0=0(1 k)k=01 k(12),(17),.1xk(1),f(x),(1).31,15.,),5MFR.1PFR(9,Matlab6.5,2.0GHzCPU256MB2,:Fletcher2Reeves83=0.5,MFRRAMWindowsXP2.=10-3,-8,.,gk10-6,1=2=102104,4105.1,=1,=1.2=2.1,:Pro;Dim;ite/doc/9d3a0f6d1eb91a37f1115c7c.html;fn;gn;-.1()Probadscbbadscpbandbardbdbealebigssboxbvgaussgulfhelixiejeusamkowosblinlin0lin1meyerosb1osb2pen1pen2roserosexsingsingxtridtrigvardimwatsonwoodDim22103426310233350241001010351110102104400501010124ite2013255313223122111129132813011314712191692982768386233867653413162169fn(gn)75(21)353(14)168(26)133(54)608(133)110(24)(41(22)25(12)3(2)281(130)27(14)131(29)251(131)16(12)6(4)99(15)2511(713)59(20)217(170)2268(299)1382(277)425(84)191(87)868(234)12381(868)388(66)218(35)115(14)1031(163)2027(170)()ite2113223498191091571115267275677157111224758313216045121110192fn(gn)89(22)353(14)164(23)112(99)(12)41(20)35(11)25(10)3(2)91(58)35(12)68(16)51(27)15(8)6(3)15(8)1452(568)60(8)198(158)1219(112)896(225)271(76)165(84)278(133)376(161)367(46)29(13)114(12)926(102)256(93)()ite51487-166-1422952/doc/9d3a0f6d1eb91a37f1115c7c.html122156153114316353-40181fn(gn)261(52k)2571(488)-2-()259(133)330(143)99(30)85(53)26(13)10(3)288(157)37(16)159(32)251(144)20(17)51(4)187(54)-81(41)()ite314126149693624111138143113612314-271773243049596432984763615172192fn(gn)112(32)(42)(23)162(65)-112(27)366(150)128(70)121(37)46(25)25(12)3(2)312(139)31(15)148(32)282(137)19(13)8(4)116(15)-69(28)298(178)2559(325)1896(305)470(96)241(97)1178(433)15389(985)556(77)259(182)12018779(1202)3411901(342)127168537475(128)424(160)1282(538)116921389(1170)223759(224)6822261378249(69)169(23)2432(262)5659(379)252(37)124(16)2126(173)2276(193)1,1.111.,=1,1.2,1,=84261.2,=1.1,1.=1,15/doc/9d3a0f6d1eb91a37f1115c7c.html,.1,1.1AL2BAALIM.DescentpropertyandglobalconvergenceoftheFletcher2ReevesmethodwithinexactlinesearchJ.IMAJNumerAnal,1985,(5):121-124.2BIRGINE,MARTINEZJM.AspectralconjugategradientmethodforunstrainedoptimizationJ.ApplMathOptim,2001,43:117-128.3DAIYH.YUANYX.ConvergencepropertiesoftheFletcher2ReevesmethodJ.IMAJNumerAnal,1996,16:155-164.4DIXONLCW.Nonlinearoptimizations:asurveyofthestateoftheartC/EvansDJ.SoftwareforNumericalMathematics,Academic,NewYork,1970:193-216.5ZHANGL,ZHOUWJ,LIDH.GlobalconvergenceofamodifiedFlelcher2ReevesmethodwithArmijo2typelinesearchJ.NumerischeMathematik,2006,(104)-6ZOUTENDIJKG.Nonlinearprogramming,computationalmetJ.Program2ming,NorthHollland,Amsteram,1970:37-86.7DAIYH,YUANYX.AhpropertyJ.SIAM/doc/9d3a0f6d1eb91a37f1115c7c.htmlJOptim,2000,10:177-182.8LIUG,J,oftheFletcher2ReevesalgorithmwithinexactlinesearchJ.ApplMathJChina,B,10:75-82.9MOR?JJGARBOWBS,HILLSTROMEKE.TestingunconstrainedoptimizationsoftwareJ.ACMTransactionsonMathematicalSoftware,1981,7:17-41.ACLASSOFMODIFIEDFLETCHER2REEVESCONJUGATEGRADIENTMETHODSWITHAPARAMETERHEZhan2bin