约束优化问题的单参数填充函数算法.pdf
《约束优化问题的单参数填充函数算法.pdf》由会员分享,可在线阅读,更多相关《约束优化问题的单参数填充函数算法.pdf(12页珍藏版)》请在咨信网上搜索。
1、应用数学MATHEMATICA APPLICATA2023,36(4):891-902约束优化问题的单参数填充函数算法马素霞1,3,高岳林2,3,杨丽丽2,柳迎春2(1.宁夏大学数学统计学院,宁夏 银川 750021;2.北方民族大学数学与信息科学学院,宁夏 银川 750021;3.宁夏科学计算与智能信息处理协同创新中心,宁夏 银川 750021)摘要:本文研究约束优化问题的全局优化确定性方法.基于填充函数的定义,具体构造出了一个新的单参数填充函数并做了相关理论证明.结合 SQP 和 BFGS局部极小化算法设计了新的填充函数全局优化算法.数值实验表明,该算法可行有效,具有良好的全局寻优能力.关
2、键词:全局优化;约束优化问题;填充函数方法中图分类号:O221.2AMS(2010)主题分类:90C26;90C30文献标识码:A文章编号:1001-9847(2023)04-0891-121.引言科学和工程中的大量决策问题都可归结为求解全局优化问题,而这类问题的求解方法是当今社会的一个重要研究热点.现有的全局优化算法大体可分为两大类,即,确定性算法14和随机性算法57.其中,填充函数法是一种经典的全局优化确定性方法,由西安交通大学的葛仁溥教授2最早提出,该方法主要通过循环迭代不断跳出当前已知的最好局部极小点以便找到另一个更好的局部极小点,直到找到全局极小点为止,从而能够克服一般优化算法容易陷
3、入“早熟”的缺陷.在文1中,葛仁溥教授率先给出了填充函数的初步概念,并将其应用于无约束全局优化问题的求解,该方法因内部只需要调用现有的局部优化方法而深受广大学者的欢迎.然而,文1中的第一代填充函数包含指数项和两个参数,由于参数调节上的困难使得实际应用中的计算量变大以及指数项的存在容易遗失问题的最优点,从而导致了该填充函数的不适用性.因此,诸多国内外学者都对葛教授的填充函数的不足之处做出了相关改进并提出了各种能够被应用到实际问题中的填充函数.例如,文8-11中所出现的四种双参数填充函数、文12-16中所提出的五个单参数填充函数以及文17-22中所给出的六种无参数填充函数等等,这些填充函数的提出使
4、得全局优化理论更为丰富.值得一提的是,文16中的填充函数仅在部分可行域内有定义,使得该填充函数的填充效率大为降低;文21中是一个很有前景的无参数填充函数,它具有连续可微的性质,但仍然包含指数项从而降低了填充效果,文22的填充函数却避免了这一缺点,但其函数图像在某些情况下是平坦的,使得填充函数在跳出局部极小点时的效率降低,该填充函数中也包含不连续可微的符号函数,这大大限制了极小化填充函数所需下降方法的选取范围.上述填充函数方法仅能被用于求解无约束全局优化问题或盒子约束全局优化问题.目前,只有少数填充函数可以解决约束全局优化问题,如文23-27中的方法.收稿日期:2022-09-09基金项目:国家
5、自然科学基金(11961001);宁夏高等教育一流学科建设基金(NXYLXK2017B09);南京证卷支持基础学科研究项目(NJZQJCXK202201);北方民族大学研究生创新项目(YCX22096)作者简介:马素霞,女,汉族,山西人,研究方向:最优化理论与方法,智能计算与大数据处理.通讯作者:高岳林.892应用数学2023此外,现有的填充函数虽然各有优点,但也存在一些缺点,如填充函数包含多个参数,导致调整困难,降低了算法的效率,若某些填充函数是非光滑函数,这也是传统局部优化方法无法实现的.为了求解有约束的全局优化问题,本文提出了一种新的填充函数,它是一个连续可微的单参数函数.如果参数的取值
6、尽可能小且大于0,那么该填充函数将保证不可行区域不存在驻点.另外,如果某个可行点的目标函数值大于当前局部极小值,则该点也不是所提填充函数的驻点.如果存在另一个优于目标函数当前极小值的局部极小点,那么此填充函数的极小点就会落在目标函数值较优的极小点附近.本文的其余部分组织如下.第二节中给出了填充函数方法的相关预备知识.第三节提出了一种连续可微的单参数填充函数.并对其解析性质做出了分析.第四节是所设计的填充函数全局优化算法的具体步骤.第五节给出一些测试问题的数值实验结果.第六节是结论.2.预备知识本文研究以下约束全局优化问题:(OP)minF(x)s.t.gi(x)0,i=1,2,m,x ,其中f
7、:R,gi(x):R,i=1,2,m,均为二次连续可微函数,是一个盒子,S=x|gi(x)0,i=1,2,m是有界集且满足cl(int(S)=S,这里int(A)表示集合A的内部,cl(A)表示集合A的闭包.在S的限制上,存在=ni=1li,ui满足S 和S=(表示集合的界).为确保问题(OP)的全局最优解存在以及所提出的填充函数方法能够顺利实现,预先给出关于该问题的一些假设条件和定义是有必要的.假设2.1问题(OP)中的目标函数是连续可微的.假设2.2集合是由问题(OP)在S中的所有局部极小点组成的,且L=F(x)|x 是有限的.注2.1假设2.2表明问题(OP)可能有无限个局部极小点,但是
8、局部极小值的数量总是有限的.定义2.1 如果存在 0,使得x B(x0,)S,有F(x)()F(x0),则x0被称为F(x)在集合S上的一个局部极小点(极大点).如果等式不成立,则x0被称为F(x)在集合S上的一个严格局部极小点(极大点);如果x S,有F(x)()F(x0)成立,则x0被称为F(x)在集合S上的一个全局极小点(极大点).如果等式不成立,则x0被称为F(x)在集合S上的一个严格全局极小点(极大点).注2.2B(x0,)表示x0的以为半径的邻域.定义2.2假设xk是目标函数F(x)的一个局部极小点,称函数MF(x,xk)是F(x)在点xk处的一个填充函数,如果MF(x,xk)满足
9、以下条件(填充性质):1)点xk是函数MF(x,xk)的一个严格局部极大点.2)假设S1k=x xk|F(x)F(xk)或 x S,如果x1s S1k,那么x1s不是MF(x,xk)的稳定点.3)如果xk不是F(x)的一个全局极小点,那么MF(x,xk)在集合S2k=x S|F(x)F(xk)中存在一个局部极小点x.第 4 期马素霞等:约束优化问题的单参数填充函数算法893注2.3定义2.2的前两个填充性质保证了填充过程得以实现,而第三个填充性质则确保了填充函数极小点x的存在性.另外定义2.2也可概括为:1)填充函数在S1k上是一个减函数并且没有驻点;2)填充函数的极小点在S2k上.3.新的填
10、充函数及其解析性质基于定义2.2所要求的三个填充性质并且考虑到多参数填充函数的不足之处,提出了下面的单参数填充函数:MF(x,xk,r)=arctan(x xk2)h(F(x)F(xk)/r)+fr(mi=1g(gi(x)+3r)(h(F(x)F(xk)/r)1),(3.1)其中,h(t)=1,t 0,1+t3 t2,1 t 0,1,t 0,fr(t)=t (m r)3r3 1,t (m r),1,t (m r),式中r 0为参数,表示是的欧氏范数,F(x)是目标函数,xk是问题(OP)的一个局部极小点,h(t),g(t)和fr(t)是R上连续可微的一元函数.m是问题(OP)中不等式约束的个数
11、.容易验证,填充函数(3.1)是连续可微的.下面验证,当r 0且r足够小时,MF(x,xk,r)满足第二部分所定义的填充函数.定理3.1如果xk,那么r 0,xk是填充函数MF(x,xk,r)在中的严格局部大点.证若xk,那么必然存在很小的正数使得x S B(xk,)都有F(x)F(xk).此时,结合函数h(t)的定义可知h(F(x)F(xk)/r)=1,故MF(x,xk,r)=arctan(x xk2)0,从而由函数g(t)的定义可得mi=1g(gi(x)+3r)=iIJg(gi(x)+3r)+iJg(gi(x)+3r)iIJ1+iJ(1 (gi(x)+3r)3)iIJ1+iJ(1 r)=m
12、 r,再利用函数fr(t)的定义不难断定MF(x,xk,r)=arctan(x xk2)0,如果xk,那么x S1kxk均不是MF(x,xk,r)的稳定点且MF(x,xk,r)Td 0,这里d=(x xk).证由定理 3.1 中的证明易知,x S1kxk,有 MF(x,xk,r)=arctan(x xk2).因此MF(x,xk,r)T=2(xxk)1+xxk4=0,故x不是MF(x,xk,r)的稳定点.与此同时,MF(x,xk,r)Td=2(xxk)(xxk)1+xxk4=2xxk21+xxk4 0且r足够小时,必然存在一点x S2k是MF(x,xk,r)在S2k中的局部极小点.证因为xk是F
13、(x)在S中的一个局部非全局极小点,所以集合S中必然存在F(x)的另一个局部极小点x1满足F(x1)0使得F(x)F(xk)且maxi1,mgi(x).当0 r 0,则0 r 0,MF(x,xk,r)Td=2(x xk)T(x xk)1+x xk4=2x xk)21+x xk4 0,(3.5)这里可行方向d=(x xk).因此在S2k上的某处,MF(x,xk,r)的可行方向将是上升的.由定理3.2、注3.1和式(3.5)易知,MF(x,xk,r)在S上先下降后上升,故MF(x,xk,r)的函数值先减小然后沿着方向(xxk)增加.利用MF(x,xk,r)的连续可微性可知,点x是MF(x,xk,r
14、)在方向(x xk)上的一个局部极小点,且由定理3.2知x S2k.证毕.定理3.2-3.3表明,如果xk不是F(x)在S上的一个全局极小点,那么当r 0且r足够小时,MF(x,xk,r)在上存在一个局部极小点x满足x S2k或者x.自此,定理3.1-3.3的结论显示,MF(x,xk,r)是一个满足定义2.2的填充函数.4.填充函数算法本节将利用构造的填充函数设计出相应的单参数填充函数算法(PFFA:Parameter FilledFunction Algorithm).填充函数算法总是涉及到极小化过程,包括极小化目标函数或者极小化填充函数本身.本文将采用SQP方法极小化目标函数,采用BFGS
15、方法极小化填充函数.步 0选择参数r的一个下界Lr(例如,取Lr=109)和一个常数 0(本文取0=0.01);0(本文取=106);置k=1.步1以x0 S作为初始点极小化F(x)得到xk,置i=1.步2构造函数MF(x,xk,r)=arctan(x xk2)h(F(x)F(xk)/r)+fr(mi=1g(gi(x)+3r)(h(F(x)F(xk)/r)1),转步3.步3如果i 2n,置xi=xk+0ei并以xi作为初始点极小化MF(x,xk,r)得到xfk并转步4;否则转步5.步4如果F(xfk)F(xk)Lr,那么通过设置r:=r来减小r然后转步 2;否则,算法停止并将xk作为F(x)的
16、一个全局极小点.第 4 期马素霞等:约束优化问题的单参数填充函数算法8955.数值实验本文使用Matlab(2016a)对PFFA算法进行编码并执行.通过使用6种测试函数对该算法进行测试,所有这些计算过程均在Intel(R)Core(TM)i5-8500 3.00 GHz power处理器8.00 GB内存,Win10操作系统的台式电脑上进行.下面给出6种测试函数,其中F(x)表示目标函数,x0表示初始点,x和F(x)分别表示全局极小点和全局极小值.例128min F(x)=x1 x2,s.t.g1(x)=x2 2x41+8x31 8x21 2 0,g2(x)=x2 4x41+32x31 88
17、x21+96x1 36 0,0 x1 30 x2 4.例1的全局最优解为x=(2.3295,3.1783)T,F(x)=5.5079.实验中,采用初始点x0=(0,0)T和x0=(0.6,0.8)T,其计算结果见表5.2.例229min F(x)=x21+x22 cos(17x1)cos(17x2)+3,s.t.g1(x)=(x1 2)2+x22 1.62 0,g2(x)=x21+(x2 3)2 2.72 0,0 xi 2,i=1,2.在例2中,x=(0.7255,0.3993)T,F(x)=1.8376.本文使用初始点x0=(1,1)T,x0=(0.5,0.5)T,x0=(1.5,1.5)T
18、,x0=(2,2)T和x0=(2,1)T对该问题进行数值测试,其计算结果见表 5.2.例329min F(x)=25(x1 2)2(x2 2)2(x3 1)2(x4 4)2(x5 1)2(x6 4)2,s.t.g1(x)=(x3 3)2 x4+4 0,g2(x)=(x5 3)2 x6+4 0,g3(x)=x1 3x2 2 0,g4(x)=x1+x2 2 0,g5(x)=x1+x2 6 0,g6(x)=x1 x2+2 0,0 x1 6,0 x2 8,0 x4 6,0 x3 5,0 x5 10,0 x6 10.例3在可行域内的全局最优解为x=(5,1,5,0,5,10)T,F(x)=310.本文使
19、用初始点x0=(3,3,3,3,3,3)T,x0=(4,4,4,4,4,4)T,x0=(3,3,4,4,3,5)T,x0=(4,4,4,4,4,4)T和x0=(2,2,3,2,3,2)T对该问题进行数值测试,其数值计算结果见表5.2.896应用数学2023例428min F(x)=37.293239x1+0.8356891x1x5+5.3578547x23 40792.141,s.t.g1(x)=0.0022053x3x5+0.0056858x2x5+0.0006262x1x4 6.665593 0,g2(x)=0.0022053x3x5 0.0056858x2x5 0.0006262x1x4
20、 85.334407 0,g3(x)=0.0071317x2x5+0.0021813x23+0.0029955x1x2 29.48751 0,g4(x)=0.0071317x2x5 0.0021813x23 0.0029955x1x2+9.48751 0,g5(x)=0.0047026x3x5+0.0019085x3x4+0.0012547x1x3 15.699039 0,g6(x)=0.0047026x3x5 0.0019085x3x4 0.0012547x1x3+10.699039 0,78 x1 102,33 x2 45,27 x3 45,27 x4 45,27 x5 45.例4在可行域
21、内的全局最优解为x=(78,33,29.9953,45,36.7758)T,F(x)=30665.5387.本文使用了初始点x0=(90,33,35,35,40)T来测试这个问题,其计算结果见表5.2.例510min F(x)=(4 2.1x21+x413)x21+x1x2+(4+4x22)x22,s.t.g(x)=sin(4x1)+2sin2(2x2)0,1 x1,x2 1.在例5中,x=(0.1093,0.6234)T,F(x)=0.9711.本文使用初始点x0=(1,1)T,x0=(0,0)T和x0=(1,1)T对该问题进行数值测试,其计算结果见表5.2.例626min F(x)=20e
22、xp(0.2|x1|+|x2|2)exp(cos(2x1)+cos(2x2)2)+20,s.t.g1(x)=x21+x22 300,g2(x)=2x1 x2 4,30 xi 30,i=1,2.例6的全局最优解为x=(0,0)T,F(x)=2.7183.实验中,采用初始点x0=(30,30)T,其计算结果见表5.2.后面这部分对PFFA算法进行了数值实验测试.为了证明该算法的有效性,我们对PFFA算法计算所得到的迭代次数和填充函数的评估次数的数值结果与文10,23,26中相应的数值结果进行了比较.在此之前,对这部分所使用的一些符号约定如表5.1所示.表5.1符号说明PN:测试函数序号DN:决策变
23、量个数k:第k次迭代Iter:算法终止前的迭代次数Alg:算法类型N:算法终止前填充函数的函数评估次数第 4 期马素霞等:约束优化问题的单参数填充函数算法897表5.2例1-4的计算结果PNDNkx0kF(x0k)xkF(xk)11(0.0000,0.0000)0.0000(0.6116,3.4421)-4.053622(1.5442,2.5098)-4.0540(1.6000,2.8204)-4.42003(2.1654,2.2549)-4.4203(2.3295,3.1785)-5.507921(0.6000,0.8000)-1.4000(0.6116,3.4421)-4.05372(2.
24、1654,2.2549)-4.4203(2.3295,3.1785)-5.507921(1.0000,1.0000)-2.0000(0.6116,3.4421)-4.05372(2.5000,1.9000)-4.4000(2.3295,3.1785)-5.507921(1.0000,1.0000)5.5503(1.1111,1.1010)3.456322(0.8050,0.8051)3.4239(0.7330,0.7330)2.08573(0.7001,0.3887)1.9064(0.7250,0.3991)1.837521(0.5000,0.5000)4.7040(0.4396,0.3537
25、)1.98302(0.7106,0.3995)1.9069(0.7250,0.3992)1.837521(1.5000,1.5000)5.6334(0.4390,0.3539)1.97232(0.7104,0.3994)1.9070(0.7254,0.3993)1.837521(2.0000,2.0000)12.6971(0.4396,0.3539)1.98232(0.7104,0.3994)1.9073(0.7254,0.3993)1.837521(2.0000,1.0000)9.1237(1.8351,1.1008)5.61252(0.7005,0.3996)1.9863(0.7250,0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 约束 优化 问题 参数 填充 函数 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。