一种近似BFGS的自适应双参数共轭梯度法.pdf
《一种近似BFGS的自适应双参数共轭梯度法.pdf》由会员分享,可在线阅读,更多相关《一种近似BFGS的自适应双参数共轭梯度法.pdf(11页珍藏版)》请在咨信网上搜索。
1、应用数学MATHEMATICA APPLICATA2024,37(1):89-99一种近似BFGS的自适应双参数共轭梯度法李向利1,2,莫元健1,3,梅建平1(1.桂林电子科技大学数学与计算科学学院,广西 桂林 541004;2.广西高校数据分析与计算重点实验室,广西 桂林 541004;3.广西应用数学中心,广西 桂林 541004)摘要:为了更加有效的求解大规模无约束优化问题,本文基于自调比无记忆BFGS拟牛顿法,提出一个自适应双参数共轭梯度法,设计的搜索方向满足充分下降性,在一般假设和标准Wolfe线搜索准则下,证明该方法具有全局收敛性,数值实验结果证明提出的新算法是有效的.关键词:大规
2、模无约束优化;共轭梯度法;Wolfe线搜索;全局收敛性中图分类号:O224AMS(2010)主题分类:90C30文献标识码:A文章编号:1001-9847(2024)01-0089-111.引言常见无约束优化问题:min f(x),x Rn,(1.1)其中x Rn表示可行域,f(x)为可行域内的连续可微函数,g(x)为f(x)的梯度其计算表达式为g(x)=f(x).最早求解问题(1.1)的方法有牛顿法,拟牛顿法等.但是这些方法并不适用在大规模问题上,因为它们需要计算和存储Hessian矩阵或其近似值,这使得计算成本非常昂贵.共轭梯度法因其低存储、易计算和具有良好收敛性等特点进而被广泛应用在求解
3、大规模无约束优化问题当中.针对问题(1.1),共轭梯度法的近似解序列xk迭代格式如下:xk+1=xk+sk,sk=kdk,k=0,1,(1.2)其中k、dk分别表示步长和搜索方向.步长k通常由Wolfe1线搜索可得f(xk+kdk)6 f(xk)+kgkTdk,(1.3)gk+1Tdk gkTdk,(1.4)其中和满足关系0 6 0,(1.5)目前研究者们提出了一系列新的共轭梯度法,这些共轭梯度法的推广研究主要集中在共轭参数和搜索方向的选取上.其中一些经典的共轭参数k如下:Fetcher-Reeves(FR)2,Polak-Ribire-Polyak(PRP)34,Hestenes-Stief
4、el(HS)5,共轭下降(CD)6,Liu-Storey(LS)7,和Dai-Yuan(DY)8.对应的k公式分别为CDk=|gk+1|2gTkdk,LSk=gTk+1ykgTkdk,DYk=|gk+1|2dTkyk,收稿日期:2022-11-28基金项目:国家自然科学基金(11961010,61967004);桂林电子科技大学研究生创新项目(2023YCXS115)作者简介:李向利,女,汉族,陕西人,教授,研究方向:最优化理论与算法.90应用数学2024HSk=gTk+1ykdTkyk,FRk=|gk+1|2|gk|2,PRPk=gTk+1yk|gk|2.其中.表示欧几里得范数,yk=gk+
5、1 gk.拟牛顿法9也常用于求解大规模无约束优化问题.由Broyden10、Fletcher11、Goldfard12、Shanno13四位学者提出的BFGS方法是最有效的拟牛顿方法之一.为了更有效的求解大规模无约束优化问题,进一步减少计算和储存空间成本,将共轭梯度法和拟牛顿法相结合的研究已成热门趋势,众多学者对这两种方法的优化和改进仍在继续.在共轭梯度法中,标准的共轭条件可以让其获得良好的数值结果和收敛性,但标准的共轭条件在非精确线搜索中不能保证充分下降性,为了解决这一缺陷,DAI和LIAO14把拟牛顿法的思想用到共轭梯度法中,则有DAI-LIAO共轭条件:yTkdk+1=gTk+1sk,(
6、1.6)其中是DAI-LIAO参数,此时共轭梯度参数迭代更新公式为DLk=gTk+1ykyTkdk gTk+1skyTkdk,(1.7)搜索方向为dk+1=gk+1+D Lkdk=(I skyTksTkyk+sTksksTkyk)gk+1=QD Lk+1gk+1,(1.8)其中 0,当=0时,上式退化为HSk.许多学者对(1.7)中的参数进行研究,学者Hager和ZHANG15基于HS法提出著名的CGDESCENT共轭梯度法,其搜索方向满足充分下降性和共轭条件,CGDESCENT法可看作DL共轭梯度法的一种特殊形式,搜索方向为dCGDESCENTk+1=gk+1+(yk 2yk2(yTksk)
7、sk)Tgk+1yTksksk.(1.9)DAI和KOU16结合最佳逼近思想,使得共轭梯度法的搜索方向逼近Perry和Shanno17的自适应无记忆BFGS方法的搜索方向,提出一类新的共轭梯度法.LI18受文16的启发提出一个三项PRP 共轭梯度方法,其搜索方向接近无记忆BFGS拟牛顿方法的方向,在强Wolfe条件下,搜索方向满足充分下降性,搜索方向为dTPRPk+1=gk+1+NEWkdk+kyk,(1.10)其中,NEWk=gTk+1ykzkskyk2gTk+1dk(z2k),k=tkgTk+1dkzk,0 tk t 2,mk=min1,2yTkskyk2.搜索方向下降性对收敛性分析有着重
8、要作用,为保证算法生成的搜索方向满足充分下降性,因此,本文通过定理2.1说明公式(2.7)的搜索方向满足充分下降性.92应用数学2024定理2.1如果mk=min1,2yTkskyk2,则公式(2.7)所定义的搜索方向满足充分下降性,即满足关系式gTk+1dk+16 cgk+12,k 0.证结合(2.7)计算易得gTk+1dk+1=gk+12+tkgk+12wgTk+1dk+sTkgk+1yTkskgTk+1(mkyk sk)gk+12+tkgk+12dkgk+1gk+1dk+sTkgk+1yTkskgTk+1(mkyk sk)gk+12+tkgk+12+mkgTk+1yksTkgk+1yTk
9、sk(sTkgk+1)2yTksk.(2.8)根据基本不等式:aTb 612(a2+b2),对上式进行整理可得gTk+1dk+1 gk+12+tkgk+12+mk2gk+12+mk2(sTkgk+1)2(yTksk)2yk2(sTkgk+1)2(yTksk)2yTksk(1 tkmk2)gk+12+(sTkgk+1)2(yTksk)2(mk2yk2 yTksk).(2.9)下面对自适应双参数tk和mk的取值范围进行讨论.1)当tk=mint,max0,gTk+1(ykAksk)gk+12,该条件下满足0 6 tk6 t 6 1.2)当mk=min1,2ykTskyk2,该条件下满足0 6|mk
10、|6 1.通过公式(2.7)和自适应双参数tk和mk的取值范围可知,公式(2.9)中的1 tkmk2满足1 112 1 tkmk2121=c 0,所以本文提出的搜索方向对于充分下降性条件成立,即存在一个常数c 0,有gk+1Tdk+16 cgk+12,证毕.为提高算法效率来得到更好的数值结果,本文采用加速算法来替代公式(1.2)的最小点,并记为xk+1=xk+kkdk,(2.10)其中,k=akbk,ak=kgTkdk,bk=k(gk gz)Tdk,gz=f(z)和z=xk+kdk.如果bk=0,则计算新解为xk+1=xk+kkdk,否则,xk+1=xk+kdk.在文22中加速方案被证明是满足
11、线性收敛的.本文提出一种有效的自适应双参数三项共轭梯度算法,该方法能更有效的求解大规模无约束优化问题,新算法的具体步骤如下:算法2(TTNEWCG)步0初始值设置:k=0,x0 Rn,0 6 2000则停止迭代,否则进入步骤2.步2通过wolfe线搜索(1.3)和(1.4)求步长k.步3计算z=xk+kdk,gz=f(z),yk=gk gz,ak=kgTkdk,bk=kyTkdk.步4如果bk=0,计算k=akbk,并将更新下一步迭代点xk+1=xk+kkdk,否则为xk+1=xk+kdk,计算fk+1,gk+1,yk=gk+1 gk,sk=xk+1 xk.步5通过公式(2.7)计算搜索方向.
12、步6重启准则满足?gTk+1gk?0.2gk+12,则dk+1=gk+1.步7更新k=k+1,返回步1.第 1 期李向利等:一种近似BFGS的自适应双参数共轭梯度法933.收敛性分析在本节,我们证明TTNEWCG算法的全局收敛性.证明过程需做出如下合理假设:假设3.11)水平集=x Rn|f(x)6 f(x0)是有界的;2)在的某个邻域N内,函数的梯度f(x)在水平集上满足Lipschitz连续,即存在一个常数L 0,使得yk=g(x)g(y)Lx y,x,y N,(3.1)上面假设1)2)可等价于存在非负常数1和B满足g(x)1,x ,(3.2)x B,x ,(3.3)又由式(3.3)易得s
13、k 2B,x .(3.4)除了上述假设外,为了更好的证明TTNEWCG算法的理论性质,下面给出引理3.1来说明新设计的搜索方向满足充分下降性.引理3.1若搜索方向dk+1由算法TTNEWCG生成,则搜索方向dk+1具有充分下降性,即存在一个常数c 0使得gTk+1dk+1 cgk+12.(3.5)根据公式(2.7)-(2.10)可知该搜索方向满足充分下降性.因此,TTNEWCG方法定义良好.Zoutendijk条件23对证明共轭梯度法的全局收敛性起重要作用,在标准的wolfe线搜索条件下,Zoutendijk条件由下面引理3.2给出.引理3.223若假设3.1成立,近似序列解xk由TTNEWC
14、G算法生成,且搜索方向dk满足充分下降性,步长k通过wolfe线搜索得到,那么有k=0(gTkdk)2dk2 0有gk ,k 0,(3.8)根据公式(3.1)和(3.4)易知yk Lsk 2BL,(3.9)根据wolfe准则易得yTksk=(gk+1 gk)Tkkdk kk(1)gTkdk 0.(3.10)再根据公式(1.4)可得gTk+1sk gTksk=yTksk+gTk+1sk.(3.11)对式(3.11)进行移项可得gTk+1sk1 yTksk,(3.12)94应用数学2024其中0 6 1.又有gTkdk 0推得gTksk 0,所以1 yTksk gTk+1sk=yTksk+gTks
15、k 2000或gk 6 105(1+|fk|).表2显示在1000,5000,10000维度条件下五个对比算法的数值结果,N代表函数名称,dim代表维度,Iter,Fno,Gno,Time分别代表算法迭代次数,目标函数迭代次数,目标梯度迭代次数和CPU运行时间.表格中的“NAN”代表该方法存在数值溢出或者未能达到算法的收敛条件.表1为测试函数的序号及名称.通过表2中138个测试问题的结果可知,算法TTNEWCG能够全部求解所有测试问题,由此可知算法TTNEWCG是有效的.除了通过表格验证新算法的有效性和可行性外,本文将采用Dolan和Mor e25性能图来更加直观的对比分析四个算法数值效果.下
16、面是性能图原理的简单介绍.在实验环境相同情况下,四种算法求解同一个测试问题,这里有P代表由单个测试问题p组成的问题集合,S表示由单个算法s组成的集合.tp,s表示使用算法s求解测试问题p的耗费时间,性能比rp,s的数值越小表明算法s对于问题p的求解性能越好.rp,s计算表达式为:rp,s=tp,smintp,s:s S.第 1 期李向利等:一种近似BFGS的自适应双参数共轭梯度法95表 1测试函数序号测试函数序号测试函数1Extended Freudenstein and Roth24DIXMAANA(CUTE)2Extended Beale Function BEALE25DIXMAANB(
17、CUTE)3Extended Penalty Function U5226DIXMAANC(CUTE)4Raydan 1 Function27DIXMAANE(CUTE)5Raydan 2 Function28Broyden Tridiagonal6Diagonal1 Function29EDENSCH Function(CUTE)7Diagonal2 Function30DIAGONAL 68Diagonal3 Function31ENGVAL1(CUTE)9Hager Function32DENSCHNA(CUTE)10Generalized Tridiagonal-1 Function3
18、3DENSCHNC(CUTE)11Extended Three Exponential Terms34DENSCHNB(CUTE)12Generalized Tridiagonal-235DENSCHNF(CUTE)13Diagonal4 Function36Extended Block-Diagonal BD214Diagonal5 Function(MatrixRom)37Generalized quartic GQ1 function15Extended Himmelblau Function38Diagonal 716Generalized PSC1 Function39Diagona
19、l 817Extended Block Diagonal BD1 Function40Full Hessian18Extended Maratos Function41SINCOS19Extended Hiebert Function42Generalized quartic GQ220Extended EP1 Function43EXTROSNB(CUTE)21Extended Tridiagonal-2 Function44FLETCHCR(CUTE)22ARWHEAD(CUTE)45HIMMELBG(CUTE)23DQDRTIC46DIAGONAL 9024681012141600.10
20、.20.30.40.50.60.70.80.91()IterTTNEWCGTTCDDYCGDESCENTTPRPDY图 1算法迭代次数性能图02468101214161800.10.20.30.40.50.60.70.80.91()FnoTTNEWCGTTCDDYCGDESCENTTPRPDY图 2目标函数迭代次数性能图s()定义为性能分布函数,s()的曲线越高,其对应方法的数值性能就越好计算,它的计算公式如下:s()=1npsizep P:log2rp,s.96应用数学2024表2算法数值结果NdimTTCDDYCGDESCENTTPRPDYTTNEWCGiter/fno/gno/timei
21、ter/fno/gno/timeiter/fno/gno/timeiter/fno/gno/timeiter/fno/gno/time11000277/555/3327/0.251388179/359/2002/0.145576294/589/3602/0.26999863/127/650/0.0845046942/2827/9405/0.7487885000442/885/5311/2.06005806/1613/8881/3.45546334/669/4118/1.5942658/117/602/0.241561816/2449/8145/3.3611810000309/619/3716/
22、2.89299100/201/1092/0.844984375/751/4611/4.346458/117/602/0.497321762/2287/7605/6.32662100054/109/316/0.008142284/169/546/0.012497868/137/398/0.010004868/137/397/0.0246629261/784/1306/0.055432500064/129/375/0.051130199/199/659/0.080980582/165/490/0.064223370/141/409/0.0601402279/838/1396/0.318901100
23、0068/137/398/0.114398130/261/860/0.21455489/179/515/0.19398472/145/421/0.119457285/856/1426/0.6733953100032/65/303/0.001199116/33/203/0.000756515/31/192/0.000760717/35/196/0.00697418/25/109/0.0005048500027/55/437/0.009277629/59/377/0.009709815/31/247/0.005158423/47/373/0.008608314/43/247/0.006624710
24、0000/1/1/0.00104150/1/1/0.0002440/1/1/0.00321980/1/1/0.0001580/1/1/0.0003934100035/71/250/0.002437853/107/418/0.003629437/75/266/0.002493655/111/424/0.017663255/166/369/0.0037424500024/49/229/0.012838545/91/456/0.024293475/151/751/0.040920742/85/414/0.021826132/97/289/0.01723981000023/47/242/0.03558
25、5434/69/375/0.049704672/145/793/0.1264136/73/390/0.060924328/85/283/0.0444353510007/15/15/0.00025586/13/16/0.00021034/9/9/0.000159/19/19/0.00227463/10/7/0.000153850006/13/13/0.00113766/13/16/0.0011484/9/9/0.00129988/17/17/0.00185033/10/7/0.0008665100006/13/13/0.00275626/13/16/0.00274374/9/9/0.011033
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 近似 BFGS 自适应 参数 共轭 梯度
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。