箱约束变分不等式的一种非精确半光滑算法.pdf
《箱约束变分不等式的一种非精确半光滑算法.pdf》由会员分享,可在线阅读,更多相关《箱约束变分不等式的一种非精确半光滑算法.pdf(4页珍藏版)》请在咨信网上搜索。
1、第44卷第2期2023年6月淮北师范大学学报(自然科学版)Journal of Huaibei Normal University(Natural Sciences)Vol.44 No.2Jun.2023箱约束变分不等式的一种非精确半光滑算法张杰,蔡玉玉,王翀(淮北师范大学 数学科学学院,安徽 淮北 235000)摘要:为提高求解箱约束变分不等式问题的效率,文章在一个互补函数的基础上,将原问题转化为与之等价的方程组,给出一种非精确半光滑算法。在该算法的每步迭代中,相应的线性方程组都采用非精确求解方法。算法的全局收敛性被证明,数值试验表明,算法对求解该类问题稳定可靠。关键词:箱约束变分不等式;非
2、精确牛顿方法;大规模问题中图分类号:O 221.0文献标识码:A文章编号:2095-0691(2023)02-0026-040引言变分不等式是一类重要的非线性问题,在物理、工程和金融等领域都有广泛应用。目前变分不等式问题仍然受到广泛关注,众多学者对其解的存在性和求解方法做出了诸多贡献1-6。变分不等式问题的一般表达式为:设XRn,F:RnRn,求xX,使F(x)T(y-x)0,yX。本文主要研究箱约束变分不等式,即设X=a,b:=|xRnaixibi,iN,记为VI(a,b,F)。如果X=|xRnx0,VI(a,b,F)就是非线性互补问题,即:求xR,使之满足x0,F(x)0,xTF(x)=0
3、。箱约束变分不等式尽管是变分不等式的一种特殊情形,但其在许多领域有着广泛应用7-8。对于变分不等式的研究主要集中在2方面:一是解的相关理论,另一个是求解算法。本文主要关注箱约束变分不等式算法。关于箱约束变分不等式的求解算法已经有了一些较好的结果9-13,其中光滑化方法是一类重要方法,其基本思想是通过互补函数,将问题转化为与之等价的光滑或非光滑方程组,进而求出原问题近似解。往往在实际问题中,待求实际问题转化得到的变分不等式或互补问题规模都较大,如果直接采用上述光滑化方法,往往会影响求解效率,其原因主要是精确求解子问题效率不高。因此,在文献 14 所给出的互补函数基础上,采用非精确技术求解转化后的
4、子问题,得到一种求解箱约束变分不等式的非精确半光滑方法。由于该方法避免精确求解转化后的大规模子问题,所以提高了求解效率。1算法本文利用文献 14 中的互补函数:i(u,v)=(u-ai)(u-bi)2+v2+(u-bi)(u-ai)2+v2+(bi-ai)v,i(u,v)=-(u-ai)(u-ai)2+v2+v)+(u-bi)+(u-bi)2+v2-v),这里t+=max0,t,t-=min0,t,tR。由文献 14 结果,求解箱约束变分不等式VI(a,b,F)就等价于求解i()xi,Fi()x+i()xi,Fi()x=0。定义向量函数H:Rn+1Rn+1:收稿日期:2022-11-18基金项
5、目:安徽省高等学校自然科学研究项目(KJ2020A0024);淮北师范大学实验室开放项目(2022sykf016)作者简介:张杰(1979),女,安徽淮北人,硕士,副教授,研究方向为优化理论、算法与应用。第2期张杰等:箱约束变分不等式的一种非精确半光滑算法H()z=1()x1,F1()x+x1+1()x1,F1()x+x12()x2,F2()x+x2+2()x2,F2()x+x2n()xn,Fn()x+xn+n()xn,Fn()x+xn,这里z(,x)。于是若H()z=0,则=0,x即为箱约束变分不等式VI(a,b,F)的解。记()z=H(z)2,则求解箱约束变分不等式VI(a,b,F)的非精
6、确半光滑方法可以设计如下:算法选取参数()0,1,()0,1以及()0,1。任取()0,x0R+Rn(R+表示正数)。另取序列满足k0,,0,1-0,令k=0。步1若H()zk=0,停止;步2计算zk=()k,xk,满足H()zk+Vkzk=k0rk,其中VkH()zk,k=()zkmin1,(zk),rkkH()zk。步3令lk为满足下式的最小非负数:()zk+lzk1-()1-0-kl()zk。步4令zk+1=zk+lkzk,k=k+1,转步1。2收敛性本节讨论算法的收敛性,为了分析需要,首先给出P0-函数概念和几个结论。定义 1设F:RnRn,若对任意x,yRn,xy,有maxxiyi(
7、)xi-yi()Fi()x-Fi(y)0,则称F为P0-函数。命题1如果F:RnRn是连续可微的P0-函数,则任意VH(z)可逆。命题1在文献 14 中有详细证明。据命题1,算法第2步成立,从而可以得到算法是适定的。命题2如果F是连续可微的P0-函数,则对任意k0,由算法产生的无穷序列 zk=()k,xk,满足zk|()k,xkk()zk0。命题3如果对任意z=(),x R+Rn,都有VH(z)非奇异,那么存在z 的一闭邻域N(z)和正数(0,1,使得对z=(,x)N(z),0,1-0,()0,1以及0,,有R+,VH(z)非奇异,且()z+z 1-()1-0-()z。命题2和命题3的证明类似
8、于文献 10 中引理3和文献 15 中引理5,为简单计,本文从略。下面证明算法的全局收敛性,假设水平集L()z0=|zRn+1()z()z0有界,此即保证由算法产生的序列 zk有界,从而有聚点。定理1设F是连续可微的P0-函数,则由算法产生的序列 zk的任何聚点都是方程组H()z=0的解。证明设序列 zk由本文算法产生,z为 zk的任一聚点。不失一般性,假设序列 zk收敛于点z。根据算法设计数列()zk单调递减,所以由()z的连续性,有(zk)(z)0。如果()z=0,那么定理得证。下设()z0,由命题2知,zk,k()zk0=min1,(zk)0,故zR+。再由命题3可知,存在z的一闭邻域N
9、(z)和正数(0,1,使得对z=(,x)N(z),0,1-0,()0,1以及0,,()z+z 1-()1-0-()z成立。故对充分大的k,存在满足l(0,的正整数l,使()zk+lzk1-()1-0-kl()zk。对上式两边关于k+求极限,则有(z)0,这与所设()z0矛盾。此即说明上述2种情况都有27淮北师范大学学报(自然科学版)2023年H()z=0,从而定理得证。定理1证明了算法的全局收敛性,实际上还可以证明算法具有局部线性甚至超二次收敛性,类似于文献 10 和 15 中的讨论,本文从略。3数值算例为了测试非精确半光滑牛顿方法的求解效率,本节将对3个算例进行测试,所有试验程序都是用Mat
10、lab编写完成。算法参数按如下选取:=0.86,=0.001,0=0.1,=0.9,终止条件设为()z 10-6。算例 1F:R4R4为严格单调映射,F()x=x31-8x2-x3+x32+3x2+x3+2x33-3x4+2x34。(1)a=()0,0,0,0T,b=(5,5,5,5)T;(2)a=()-1,-1,-1,-1T,b=(1,1,1,1)T。算 例 2F:R4R4为 严 格 单 调 映 射,F()x=4x1+2x2+2x3+x4-82x1+4x2+x4-62x1+2x3+2x4-4-x1-x2-2x3+3。(1)a=()-5,-5,-5,-5T,b=()5,5,5,5T;(2)a=
11、()-1,-1,-1,-1T,b=(1,1,1,1)T。算例3(线性互补问题)F()x=Mx+q,其中q=(-1,-1,-1)T,矩阵M选取方式和文献 10 类似,即M=122201220012 0001,该问题的解为x=()0,0,0T,算法中初始点选取为x0=()1,1,1T。算例13的计算结果列在表1和表2中,No.it表示迭代次数、CPU表示时间、Res表示算法终止时值。另外,表2中的n代表问题的维数。从计算结果来看,非精确半光滑牛顿方法求解此类箱约束变分不等式效率很好,特别是算例3的测试结果说明,对较大规模问题,算法仍然具有很好的效率,总的来说,本文算法可靠、有效。表1算例1、2计算
- 配套讲稿:
如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。