求解伪单调广义变分不等式的次梯度外梯度算法_邹雨航.pdf

2 0 2 3年4月第3 8卷第4期内江师范学院学报J o u r n a l o fN e i j i a n gN o r m a lU n i v e r s i t yA p r.2 0 2 3V o l.3 8N o.4求解伪单调广义变分不等式的次梯度外梯度算法邹雨航,叶明露*(西华师范大学 数学与信息学院,四川 南充 6 3 7 0 0 9)摘 要:2 0 1 2年C e n s o r等在欧氏空间里提出了一种求解伪单调变分不等式的算法.该算法在映射为L i p s c h i t z连续且伪单调的条件下得到了全局收敛性.基于该算法,将其推广到广义变分不等式,并在集值映射F连续且伪单调的条件下,证明了算法的全局收敛性.数值实验表明了新算法的可行性.关键词:广义变分不等式;次梯度外梯度算法;线搜索;伪单调D O I:1 0.1 3 6 0 3/j.c n k i.5 1-1 6 2 1/z.2 0 2 3.0 4.0 0 5中图分类号:O 2 2 4文献标志码:A文章编号:1 6 7 1-1 7 8 5(2 0 2 3)0 4-0 0 2 4-0 50 引言本文在欧氏空间Rn中考虑广义变分不等式问题(GV I P):寻找一个向量xC和一个向量tF x(),使得0,yC,其中CRn是一个非空闭凸集,F:Rn2Rn为集值映射,和 分别表示Rn的内积和范数.令S为GV I P的解集,即S=xC0,yC.当集值映射F退化为单值映射时,GV I P退化为经典变 分不等式问 题(V I P),即 寻找一个向 量x*S,使得0,yS,其中SRn是一个非空闭凸集,F:RnRn为单值映射.变分不等式在力学、微分方程、经济学、控制论、博弈论、图像处理等诸多方面都有着十分重要的应用.因此,广大学者提出了许多数值算法来求解变分不等式问题.其中投影法因其易实施、可并行运算的特点而受到了广泛的研究.1 9 6 4年,G o l d s t e i n1提出了一种投影方法xk+1=PCxk-F xk()(),当步长(0,2/L2)(L为F的L i p s c h i t z系数,为F的强单调系数),证明了迭代序列xk 能收敛到V I P的解.但是该算法需要F在C上L i p s c h i t z连续且强单调,这限制了这种算法的运用.为了 削 弱 强 单 调 的 条 件,1 9 7 6年K o r p e l e v-i c h2提出了外梯度投影算法求解变分不等式问题:yk=PCxk-F(xk)(),xk+1=PCxk-F(yk)(),当步长(0,1/L)(L为F的L i p s c h i t z系数),且F在C单调的条件下,证明了迭代序列xk 能收敛到V I P的解.但该算法需要向可行集C做两次投影.从而,当投影不易实施时,该算法的运算效率会受到影响.为了减少向可行集C做投影的次数,2 0 1 2年C e n s o r等3-4提出了次梯度外梯度投影算法:yk=PC(x-F(xk),Tk=wRn|0 xk+1=PTK(xk-F yk(),该算法在F伪单调且L i p s c h i t z连续的条件下,得到了算法的全局收敛性.其中迭代点xk+1是通过向半*收稿日期:2 0 2 2-0 6-2 7 基金项目:国家自然科学基金面上项目(1 1 8 7 1 0 5 9);国家自然科学基金青年项目(1 1 8 0 1 4 5 5)作者简介:邹雨航(1 9 9 7-),男,四川乐山人,西华师范大学硕士研究生,研究方向:优化理论及应用*通信作者:叶明露(1 9 7 5-),男,重庆人,西华师范大学教授,博士,研究方向:优化理论及应用第4期邹雨航,等:求解伪单调广义变分不等式的次梯度外梯度算法空间Tk做投影得到的,而向半空间的投影可以用显示公式表出(参见引理4).故向半空间投影次数的计算机耗时可以忽略.因此在每一次迭代过程中,该算法可视为只需向可行集C做一次投影,从而提高了算法的效率.广义变分不等式在均衡问题、非线性规划、工程科学等领域都有广泛的应用5-6.受到文献的启发,本文提出了一种求解广义变分不等式问题的次梯度外梯度算法,在映射F伪单调且连续的条件下,证明了算法所产生的迭代序列xk 能收敛到GV I P的一个解,并用数值实验验证了算法的可行性.1 预备知识定义1 设Rn为欧氏空间,称集值映射F:Rn2Rn,(1)在点x处上半连续,若对于任意包含F x()开集U,都存在x的一个开邻域N,使得F N()U;(2)在点x处下半连续,若对于任意开集U使得F x()U,都存在x的一个开邻域W使得对任意的yW,F y()U;(3)在点x处连续,若F在点x处既上半连续又下半连续;(4)在C上连续,若F在C上任意一点连续.定义2 设K为Rn中的非空闭凸集,称集值映射F:Rn2Rn在K上是伪单调的,若对任意的x,yK,uF x(),vF y()都有00.对固定的xRn,tF x(),0,我们用rx,t()来表示自然残差映射,即rx,t()=x-PCx-t().引理17 设 0,则xS当 且 仅 当rx,t()=0.引理27 设xRn,tF x(),则有以下结论成立:(1)对 0 1 0,有m i n(1,)rx,1,t()rx,t()m a x(1,)rx,1,t().下面我们回顾投影算子一些常见的性质.对任意 非 空 闭 集CRn,我 们 记PC(x):=a r g m i nyCx-y 为点x到C上的投影.引理37-8 设C为Rn中的非空闭凸集,则有以下结论成立:(1)0,xRn,yC;(2)PCx()-PCy()x-y,x,yRn;(3)PCx()-x2x-y2-PCx()-y2,xRn,yC.引理49-1 0 设H:=vRn|-a0是一个半空间,其中0uRn,aR.则PH(x)=x-m a x-au2,0u.特别的,若xH,则有PHx()=x-au2u.在本文中,我们对GV I P的条件假设如下:假设1(1)解集S非空;(2)F在C上伪单调且其值为非空紧凸集;(3)集值映射F在Rn上连续.2 算法及其收敛性算法1步 骤0:选 取 初 始 点x0Rn,参 数l0,1(),0,1(),令k=0.步 骤1:任 取tkF xk(),计 算zk=PCxk-tk(),若xk=zk,则停止,此时xk是V I P的解;否则,转到下一步.步骤2:(线搜索)计算k=lmk,其中mk是满足下式成立的最小非负整数m,lmtk-tkm()xk-ykm(),(1)其中tkm()=PF ykm()()tk(),ykm()=PCxk-lmtk().令yk=ykmk()=PCxk-ktk(),tk=tkmk()=PF yk()tk().步骤3:计算xk+1=PTKxk-ktkm()(),其中TK=w0.步骤4:令k=k+1,然后返回步骤1.注1 在算法1中,对任意的zC,由yk=PCxk-ktk()和引理1,可知0,所以CTK.注2 由引理1,当xk=zk时,有rxk,1,tk()=0,则xkS.引理5 若假设1的(3)成立,由(1)式可知,对任意的tkFx(),都存在最小非负整数m使得下式成立:lmtk-tkm()xk-ykm().证明 假设对任意的非负整数m,(1)式都不成立.则对任意的非负整数m都有52内江师范学院学报第3 8卷lmtk-tkm()xk-ykm().(2)讨论以下两种情况:(1)若xkC,此 时xk-ykm()xk-PCxk()0m(),且序列ykm()mN 是有界的.因为F下半连续且具有紧值,我们有F ykm()()mN 是有界的,因此tkm()mN 也是有界的1 1.进而可得lmtk-tkm()0(m),与(2)式矛盾.(2)若xkC,由(2)式有tk-tkm()xk-ykm()lm=rxk,lm,tk()lm.(3)结合引理2的(2)和l 0,1(),则对充分大的m有tk-tkm()rxk,lm,tk()lmrxk,1,tk()1=xk-PCxk-tk()0.(4)另一方面,结合F是下半连续的,由ykm()PCxk()=xkm(),tkF xk(),可知存在tkm()F ykm()()使得tkm()tkm(),结合tkm()=P(F(yk(m)tk()可知0tkm()-tktkm()-tk0m().(5)从而得到与(4)式矛盾.引理6 若假设1成立,xk 是算法1生成的无穷序列,则对任意的x*S,有xk+1-x*2xk-x*2-1-2()xk-yk2.证明 由Tk的定义可知0,因此=+kk.(6)记zk=xk-ktkmk(),xk+1-x*2=PTk(zk)-x*2=zk-x*2+zk-PTk(zk)2+2.(7)由引理3(1)可知2zk-PTkzk()2+2=20.从而得到zk-PTkzk()2+2-zk-PTkzk()2.(8)将(8)代入(7)可得xk+1-x*2zk-x*2-zk-PTk(zk)2=xk-ktk(mk)-x*2-xk-ktk(mk)-xk+12=xk-x*2-xk-xk+12+2k.(9)由F是伪单调的可知0.从而得到.(1 0)将(1 0)代入(9)可得xk+1-x*2xk-x*2-xk-xk+12+2k.(1 1)结合(6)和(1 1)可得xk+1-x*2xk-x*2-xk-xk+12+2k=xk-x*2-xk-yk2-yk-xk+12+2xk-x*2-xk-yk2-yk-xk+12+2k.(1 2)由C a u c h y-S c h w a r z不等式和(1)可知2k2kxk+1-yk tk-tk(mk)2xk+1-yk xk-yk.(1 3)结合0 xk-yk-yk-xk+1()2=2xk-yk2-2xk-yk yk-xk+1+yk-xk+12.即2 xk-ykyk-xk+12xk-yk2+yk-xk+12.(1 4)将(1 4)代入(1 3)可得2k2xk-yk2+yk-xk+12.(1 5)将(1 5)代入(1 2)可得xk+1-x*262第4期邹雨航,等:求解伪单调广义变分不等式的次梯度外梯度算法xk-x*2-1-2()xk-yk2.定理1 若假设1成立,xk 是算法1生成的无穷序列,则xk 收敛到GV I P的一个解.证明 取定x*S.由引理6结合 0,1()可知序列xk-x*是单调递减且有下界的.从而序列xk-x*是收敛的.进而序列xk 是有界的.并且还可得0(1-2)xk-yk2xk-x*2-xk+1-x*20m().所以l i mkxk-yk2=0.(1 6)设x是序列xk 的任意一个聚点,则存在指标集I 1,2,使得l i mk,kIxk=x.由文献1 1 的命题3.1 1,结合xk 的有界性,F在是下半连续且紧值的映射,可知F xk()是有界的,因此tk 也是有界的.同理,设t是序列tk 的任意一个聚点,则l i mk,kItk=t.结合(1 6)可知l i mk,kIyk=x.(1 7)进而由C是非空闭凸集且ykC可得xC.同理,由F是下半连续的且tkF x()可得tF x().首先,证明存在指标集II,使得下式成立:l i mk,kIrxk,1,tk()=0.(1 8)令=i n fkkI,讨论以下两种情况:(1)若=i n fkkI0,则对任意的kI可得k.进而对任意的kI可得0rxk,1,tk()rxk,1,tk()m i nk,1rxk,1,tk()m i n,10k().(1 9)即l i mk,kIrxk,1,tk()=0.(2)若=i n fk,kI=0,则存在II使得k0k,kI().由k的定义,对充分大的kI我们有,tk-tkmk-1()rxk,kl-1,tk()kl-1rxk,1,tk()1=rxk,1,tk().(2 0)下面我们证明l i mk,kItk-tkmk-1()=0.由yk的定义和投影算子的非扩张性可得xk-yk(mk-1)=xk-PC(xk-kl-1tk)xk-yk+yk-PC(xk-kl-1tk)xk-yk+xk-ktk()-xk-kl-1tk()=xk-