求解伪单调广义变分不等式的次梯度外梯度算法_邹雨航.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-yk+kl-1-k()tk 0k,kI-().(2 1)因此,由l i mk,kIxk=x,l i mk,kItk=t可知yk(mk-1)-x-0k,kI().结合tF x(),F是 下 半 连 续 的 可 知,存 在 序 列tkmk-1()使得tk(mk-1)F(yk(mk-1),tk(mk-1)t-k,kI().由tkmk-1()的定义可知0 tk(mk-1)-tk tk(mk-1)-tk tk(mk-1)-t-+t-tk 0k,kI-().(2 2)由此可知(1 8)成立.因为残差函数是连续的,由l i mk,kIxk=x,l i mk,kItk=t和(1 8)可知l i mk,kIrx,1,t()=0.(2 3)由引理1可知xS.将引理6中的x*替换为x可得xk-x 是收敛的,而x又是xk 的一个聚点,所以xk-x 收敛到0.因此xk 收敛到xS.3 数值实验本节给出了算法1在以下两个例子中的计算机检验结果,并与文献9 中的算法3.1(简称Y E算法)做了比较.这些结果都是用MAT L A B在C P U型号为1 2 t hG e nI n t e lC o r ei 7-1 2 7 0 0 H(1 4核,2.7 0 GH z)和运行内存为3 2.0 G B的笔记本电脑上运行的.算法1的参数选取如下:l=0.5,=0.9.算法1的终止条件设为rk(x,1,t)1 0-6.我们用i t e r.N u m记迭代步数,C P U(单位:秒)记运行时间.例1 设可行集K:=xRn+ni=1xi=1,F(x):=(t,t-x1,t-x2,t-xn-1)t 0,1 ,其中x=x1,x2,xn().则S=0,0,0,1().本例被文献1 2-1 3 用于测试集值变分不等式算法.步骤1中tk=1,1-xk1,1-xk2,1-xkn-1(),其中xk=xk1,xk2,xkn().初 始 迭 代 点x0=1/n*o n e s(n,1).其中o n e s(n,1)指元素全为1的72内江师范学院学报第3 8卷向量.数值结果如表1所示.表1 例1的数值结果维度 I t e r.N u m C P U 算法1Y E算法1Y E2 02 2 62 0 90.1 7 98 8 20.1 8 30 2 45 06 2 07 3 10.6 4 31 0 90.7 6 17 3 48 07 6 67 8 80.9 8 66 2 71.0 7 04 8 01 5 09 9 39 3 91 5.6 5 02 0 08.2 7 63 6 12 0 023 5 611 8 94.3 5 99 7 03.9 4 38 9 0 例2 设K:=Rn+,F(x):=(t,t-x1,t-x2,t-xn-1)t 0,1 是F:K2Rn的集值映射.则0,0,0,0()是G V I P的一个解.取步骤1中的tk=1,1-xk1,1-xk2,1-xkn-1(),其中xk=xk1,xk2,xkn().初始迭代点x0=o n e s(n,1),其中o n e s(n,1)是一个元素全为1的n维向量.数值结果如表2所示.表2 例2数值结果维度 I t e r.N u m C P U 算法1Y E算法1Y E2 02 3 12 1 40.1 9 35 8 80.1 9 07 2 15 06 6 87 6 30.7 0 44 0 30.7 4 72 3 48 07 8 98 4 71.0 8 08 1 01.1 8 11 0 01 5 08 5 19 3 63.6 9 32 3 03.9 3 00 5 02 0 09 8 81 0 3 67.1 5 80 9 17.2 1 26 4 0 注3 数值实验表明了新算法和Y E算法均能用于求解解集S非空、F连续、伪单调且紧值的集值变分不等式问题.新算法在某些例子中具有较少的迭代步数.参考文献:1G O L D S T E I N A A.C o n v e xp r o g r a mm i n gi n H i l b e r ts p a c eJ.B u l l e t i no f t h eAm e r i c a nM a t h e m a t i c a lS o c i-e t y,1 9 6 4,7 0(5):7 0 9-7 1 0.2KO R P E L E V I CH G M.T h ee x t r a g r a d i e n tm e t h o df o rf i n d i n gs a d d l ep o i n t sa n do t h e rp r o b l e m sJ.M a t e c o n,1 9 7 6,1 2:7 4 7-7 5 6.3C E N S ORY,G I B A L IA,R E I CH S.E x t e n s i o n so fK o r-p e l e v i c h se x t r a g r a d i e n tm e t h o d f o r s o l v i n g t h ev a r i a t i o n-a l i n e q u a l i t yp r o b l e mi nE u c l i d e a ns p a c eJ.O p t i m i z a-t i o n,2 0 1 2,6 1(9):1 1 1 9-1 1 3 2.4C E N S OR Y,G I B A L IA,R E I CH S.T h es u b g r a d i e n te x t r a g r a d i e n tm e t h o df o rs o l v i n gv a r i a t i o n a l i n e q u a l i t i e si nH i l b e r ts p a c eJ.J o u r n a lo fO p t i m i z a t i o n T h e o r ya n dA p p l i c a t i o n s,2 0 1 1,1 4 8(2):3 1 8-3 3 5.5郭科,陈茜.强伪单调变分不等式的线性收敛 J.内江师范学院学报,2 0 1 8,3 3(1 0):3 5-3 8.6孟继 东,马 燕 青,张 冰.A r m i j o型 线 搜 索 下 一 个 修 正H e s t e n e s-S t i e f e l共轭梯度法的全局收敛性 J.内江师范学院学报,2 0 1 2,2 7(4):2 7-3 0.7F A C CH I N E IF,P ANGJS.F i n i t e-d i m e n s i o n a lv a r i a-t i o n a l i n e q u a l i t i e sa n dc o m p l e m e n t a r yp r o b l e m sM.N e wY o r k:S p r i n g e r-V e r l a g,2 0 0 3.8X I UNH,Z HAN GJZ.S o m e r e c e n t a d v a n c e s i np r o j e c-t i o n-t y p em e t h o d sf o rv a r i a t i o n a l i n e q u a l i t i e sJ.J o u r-n a lo fC o m p u t a t i o n a la n dA p p l i e d M a t h e m a t i c s,2 0 0 3,1 5 2(1/2):5 5 9-5 8 5.9Y E M L.A ni m p r o v e dp r o j e c t i o n m e t h o df o rs o l v i n gg e n e r a l i z e dv a r i a t i o n a l i n e q u a l i t yp r o b l e m sJ.O p t i m i-z a t i o n,2 0 1 8,6 7(1 0):1-1 1.1 0F AN GCJ,CHE NS.S u b g r a d i e n te x t r a g r a d i e n ta l g o-r i t h m f o rs o l v i n g m u l t i-v a l u e d v a r i a t i o n a li n e q u a l i t yJ.A p p l i e d M a t h e m a t i c sa n dC o m p u t a t i o n,2 0 1 4,2 2 9(3-4):1 2 3-1 3 0.1 1AU B I NJP,E K E L AN DI.A p p l i e dn o n l i n e a ra n a l y s i sM.N e wY o r k(NY):W i l e y,1 9 8 4.1 2L IFL,HEYR.A na l g o r i t h mf o rg e n e r a l i z e dv a r i a-t i o n a li n e q u a l i t y w i t hp s e u d o m o n o t o n e m a p p i n gJ.C o m p u t e r s&M a t h e m a t i c s w i t h A p p l i c a t i o n s,2 0 0 9,2 2 8(1):2 1 2-2 1 8.1 3CHE N Y,Y E M L.A ni n e r t i a lP o p o ve x t r a g r a d i e n tp r o j e c t i o na l g o r i t h mf o r s o l v i n gm u l t i-v a l u e dv a r i a t i o n-a l i n e q u a l i t yp r o b l e m sJ.O p t i m i z a t i o n,2 0 2 2.As u b g r a d i e n t e x t r a d i e n t a l g o r i t h mf o r s o l v i n gp s e u d o m o n o t o n eg e n e r a l i z e dv a r i a t i o n a l i n e q u a l i t i e sZ O UY u h a n g,Y EM i n g l u*(C o l l e g eo fM a t h e m a t i c sa n dI n f o r m a t i o n,C h i n aW e s tN o r m a lU n i v e r s i t y,N a n c h o n g,S i c h u a n6 3 7 0 0 2,C h i n a)A b s t r a c t:I n2 0 1 2,C e n s o re t cp r o p o s e da na l g o r i t h mf o rs o l v i n gp s e u d o-m o n o t o n ev a r i a t i o n a l i n e q u a l i t i e s i nE u c l i d e a ns p a c e.T h ea l g o r i t h ma c h i e v e sg l o b a lc o n v e r g e n c eu n d e rt h ec o n d i t i o nt h a tt h em a p p i n gi sL i p s c h i t zc o n t i n u o u sa n dp s e u d o-m o n o t o n e,b a s e do nw h i c ht h ea l g o r i t h mi se x t e n d e dt og e n e r a l i z e dv a r i a t i o n a l i n e q u a l i t i e s,a n dt h eg l o b a l c o n v e r g e n c eo f t h ea l g o r i t h mi sp r o v e du n d e r t h e c o n d i t i o n t h a t t h e s e t-v a l u e dm a p i s c o n t i n u o u s a n dp s e u d o-m o n o t o n e.N u m e r i c a l e x p e r i m e n t s a r ec o n d u c t e dt oc o n f i r mt h e f e a s i b i l i t yo fn e wa l g o r i t h m.K e y w o r d s:g e n e r a l i z e dv a r i a t i o n a l i n e q u a l i t y;s u b g r a d i e n t e x t r a g r a d i e n t a l g o r i t h m;l i n es e a r c h;p s e u d o-m o n o t o n e(责任编辑:吕晓亚)82