变分不等式的几类求解方法

:1997-06-03.:1997-10-20.(19801009)(9811023).14A2Appl.Math.JCUVol.14Ser.ANo.2简金宝(西安交通大学理学院;广西大学理学院)　赖炎连(中国科学院应用数学研究所)本文较为系统地分析和概述了变分不等式问题中几类占有重要地位的求解方法,包括方法产生的背景,主要结果及应用等.这几类算法分别为连续算法,(拟)牛顿型算法,一般迭代模型,投影算法,投影收缩算法等.变分不等式,最优化问题,求解方法,连续算法,(拟)牛顿算法,投影算法.()O221.2;(1991MR)90C33,65K10,65H10.1(VIP),VIP,.[13].VIP,,VIP.VIP.,VIP,,,.,,[438].,[49],()[3943],[13,15,1929],[18,3137],VIP.VIP,,.VIP,,VIP,,,,(),,.VIP,VIP.,VIP,.2VIPVIP,VIP,VIP.XnRn,F(x)RnRn.2.1Xx*(2.1)(VIP),XVIP(X,F),VIP(X,F)F(x*)T(x-x*)0,PxX.(2.1)2.2(1)F(x)X,(F(x1)-F(x2))T(x1-x2)0,Px1,x2X.(2.2)x1,x2X,x1x2,(2.2),F(x)X.(2)F(x)X(A)(),A0(F(x1)-F(x2))T(x1-x2)Aúx1-x2ú2,Px1,x2X.(2.3)2.3(1)F(x)X(c)(coercive),c0(F(x1)-F(x2))T(x1-x2)cúF(x1)-F(x2)ú2,Px1,x2X.(2.4)(2)F(x)XD-(D-coercive),D0,c0(F(x1)-F(x2))T(x1-x2)cúF(x1)-F(x2)ú2,Px1,x2X,úx1-x2úD.(2.5)2.4F(x)XLipschitz,L0úF(x1)-F(x2)úLúx1-x2ú,Px1,x2X.(2.6)2.5XRn,Gn,uRn,úuú=(uTu)12,úuúG=(uTGu)12,u*:u*X,úu*-uúG=min{úx-uúGûxX},u*uúuúGX,u*=PXG(u);PX(u)uX.2.6x*VIP(X,F),x*(a)(b),x*VIP(X,F).(a)x*ND0,úyúDy,VIP(X,Fy)Nx(y),Fy(x)=F(x*)+y+$F(x*)(x-x*);(b)x(y)yLipschitz,L0úx(y)-x(z)úLúy-zú,Py,z:úyúD,úzúD.[2,4,25,44],198高校应用数学学报14A2.7(1)F(x)Lipschitz,F(x).(2)X,F(x)F(x)D-([25]2.3).(3),,.(4)X,F(X)F(X).2.8F(x),F(x)Jacobi$F(x)T,(1)F(x)X$F(x)(PxX).(2)F(x)X{$F(x),xX},a0:dT$F(x)daúdú2,PxX,PdRn.2.9xRn(2.7)(NCP)NCP(F)x0,F(x)0,F(x)Tx=0.(2.7)VIP(X,F)NCP(F),2.10[2,4](1)XRn,VIP(X,F)F(x)=0.(2)X=Rn+÷={xRnûx0},VIP(X,F)NCP(F).,VIP(X,F)X,X=X0÷={xRnûg(x)0,h(x)=0},(2.8)g(x)=(g1(x),,gm(x))T,h(x)=(hm+1(x),,hm+r(x))T,gi(x):RnR1,iI÷={1,,m},,hj(x)=aTjx-bj:RnR1,jJ÷={m+1,,m+r},h(x).VIP(X,F)(NP),2.11[2,4,5](1)F(x)f(x):RnR1$f(x),VIP(X,F)min{f(x)ûxX};,f(x)(pesudo-con-vex),X,VIP(X,F).(2)XX0,,,VIP(X0,F)KKT,NCP:F(x)-$g(x)y-$h(x)z=0.(2.9)gi(x)0,yi0,yigi(x)=0,iI;hj(x)=0,jJ.(2.10)$g(x)=($gi(x),iI),$h(x)=($hj(x),jJ);F(x)=$f(x),(2.9)(2.10)NP(X0,f):min{f(x)ûxX0}KKT,VIP(X0,F)NP(X0,f)KKT.(2.9)(2.10)VIP(X,F)KKT.2.11VIPNP,VIP,NP.,VIP(X,F),[2].2.12[2,5]XRn,F(x)X,VIP(X,F).1992简金宝等:变分不等式的几类求解方法3VIP(X0,F)VIP(X0,F),.(continuationmethods)PEP(E),P=P(0).,,P,EP(E);P(E)P,.,X(2.8)X0.2.11(2),,VIP(X0,F)(2.9)(2.10)(NCP),(2.9)(2.10)VIP(X0,F).3.1VIPI[4](2.9)(2.10)(2.9)Jacobian.F(x),[4]NCPPVIP(X0,F,E,L):F(x)+E1x-$g(x)y-$h(x)z=0,(3.1)gi(x)+E2yi0,yi0,yi(gi(x)+E2yi)=L,iI;hj(x)+E3zj=0,jJ,(3.2)E=(E1,E2,E3)0,L0.yiyi(gi(x)+E2yi)=L,,2E2yi+gi(x)+g2i(x)+4E2L=0,iI.3.1[4](1)(xEL,yEL,zEL)PVIP(X0,F,E,L)(3.3)(3.4),J(x,y,z;E,L)=0:F(x)+E1x-$g(x)y-$h(x)z=0,(3.3)2E2yi+gi(x)+g2i(x)+4E2L=0,iI;hj(x)+E3zj=0,jJ.(3.4)(2)F(x),E0,L0(x,y,z)RnRm+Rr,J(x,y,z;E,L)Jacobian($J(x,y,z;E,L))T.J(x,y,z;E,L)=0VIP(X0,F)I:0.:0{Ek1,Ek2,Ek3,Lk},k=0,1,2,,w0=(x0,y0,z0)RnRmRr.k=0,1.1.wk=(xk,yk,zk),J(x,y,z;Ek,Lk)=0()wk+1=(xk+1,yk+1,zk+1).2.err(wk+1):,,k÷=k+1,1.err(w)(2.9),(2.10),,[4].(3.2),xkVIP(X0,F)X0,,().200高校应用数学学报14A.3.2F(x),(1)E0,L0,PVIP(X0,F,E,L),J(x,y,z;E,L)=0,.(2){wk}PVI(X0,F).(3){Ek1,Ek2,Ek3,Lk}:limkEk2Ek1=c20,limkEk3Ek1=c30,limkLkEk1=c0.{wk}VIP(X0,F).,,(E2,L),Jacobian($J(x,y,z;E,L))T(3.3)(3.4).,Kanzow(1994),[5].3.2VIP[6]F(x)J=Á(),x*VIP(X0,F)(2.12),X0x*.NCP(x*,y*).[6]NCPL0PVIP(X0,F,L):F(x)-$g(x)y=0;gi(x)-zi=0,iI.(3.5)yi0,zi0;yizi=L,iI.(3.6)[6](3.6).a0,b0,ab=LZUL(a,b)÷=a+b-(a-b)2+4L=0.(3.7)3.3L0,(x,y,z)PVIP(X0,F,L)(x,y,z)(3.8)FU(x,y,z;L)÷=F(x)-$g(x)yg(x)-zUL(y,z)=0.(3.8)UL(y,z)÷=(UL(yi,zi),iI).FU(x,y,z;L)=0VIP(X0,F):0.{Lk},w0=(x0,y0,z0)RnRmRm.k=0,1.1.FU(wk;0)=0,,wkVIP(X0,F).2.FU(x,y,z;Lk+1)=0()wk+1=(xk+1,yk+1,zk+1).k÷=k+1,1.(3.5),(3.6),gi(xk)=zki0,iI.{xk}X0,().,F(x),,,[4][6].3.4F(x),L0.2012简金宝等:变分不等式的几类求解方法(1)w=(x,y,z)RnRm+Rm,FU(w;L)Jacobian$FU(w;L).(2)PVIP(X0,F,L),FU(x,y,z;L)=0,.(3){xk,yk},{xk}NCPVIP(X0,F)(x*,y*)x*.3.3VIP[7][4][6],[7]VIP.[7]NCPPVIP(X0,F,E,L):F(x)+Ex-$g(x)y=0,gi(x)-zi=0,iI.(3.9)yi0,zi0,yizi=L,iI.(3.10)(3.7)3.5E0,L0,(x,y,z)PVIP(X0,F)(x,y,z)(3.11)5(w;E,L)÷=5(x,y,z;E,L)÷=F(x)+Ex-$g(x)yg(x)-zUL(y,z)=0.(3.11)(3.11),VIP(X0,F):0.{Ek,Lk},w0=(x0,y0,z0)RnRmRm.k=0,1.1.5(wk;0,0)=0,,wkVIP(X0,F).2.5(w;Ek+1,Lk+1)=0()wk+1=(xk+1,yk+1,zk+1).k÷=k+1,1.(3.9),(3.10),gi(xk)=zki0,iI.(xk)X0,.3.6(1)VIP(X0,F)x*,x*.L0E0,PVIP(X0,F,E,L)w(E,L)÷=(x(E,L),y(E,L),z(E,L)),(E,L)(0,0),{x(E,L)}{w(E,L)}VIP(X0,F)NCP()x*w*=(x*,y*,z*=g(x*)).(2)VIP(X0,F)x*,xX0,.(E,L)0,PVIP(X0,F,E,L);A0LkAEk(k),{wk},wd=(xd,yd,zd=g(xd))VIP(X0,F)KKT,xdVIP(X0,F).3.4VIP[8],,X0.[8],VIPX0,X0,[4,6].J=Á,[8]NCP,202高校应用数学学报14AVIP(X0,F)KKT(2.9)(2.10)PVIP(X0,F,E,L):gi(x)+Eyi0,yi0,(gi(x)+Eyi)yi=L,iI.(3.12)F(x)-$g(x)y=0.(3.13)[8]E0,L0.(3.12),(3.7),(3.12)(1+E)yi+gi(x)-4L+((1-E)yi-gi(x))2=0,iI.(3.14)3.7F(x),E0,L0(1)(x,y)PVIP(X0,F,E,L)(x,y)(3.13)(3.14).7(x,y;E,L)=0(2)(x,y)RnRm+,7(x,y;E,L)Jacobian($7(x,y;E,L))T.7(x,y;E,L)=0,[8]:0.:0,{Ek,Lk}:Ek0,limkEk=0;Lk0,limkLk=0.w0=(x0,y0)RnRm.k=0,1.1.wk=(xk,yk),7(x,y;Ek,Lk)=0()wk+1=(xk+1,yk+1).2.err(wk+1):,;k÷=k+1,1.,Ek=0,xk+1X0;Ek0,xk+1X0,..3.8F(x),VIP(X0,F)x*,E0,L0,(1)PVIP(X0,F,E,L),L.(2){wk}{xk}VIP(X0,F)KKT(NCP)VIP(X0,F)().3.5VIP[9][9],[8,4],VIP,F(x).NCPPVIP(X0,F,E,L):F(x)+E1x-$g(x)y-$h(x)z=0.(3.15)gi(x)+E2yi0,yi0,yi(gi(x)+E2yi)=L,iI;hj(x)+E3zj=0,jJ.(3.16)E=(E1,E2,E3),(E1,L)0,(E2,E3)0.3.9(E1,L)0,(E2,E3)0,F(x).(1)