变分不等式多种问题

I-1[e-mail]-2..,,,..,,.,.,–,,..,.²²²²²²I-31²minff(x)jx2­g:²minfµ(x)jAx=b;x2Xg:²minfµ1(x)+µ2(y)jAx+By=b;x2X;y2Yg:²x¸0;F(x)¸0;xTF(x)=0:²x2­;(x0¡x)TF(x)¸0;8x02­:.,()(L2–L3);,(L4–L7).L8.L9.L10.L11–L14.L15–L18.,L19–L20.I-41.1­n,minfµ(x)jx2­g(1.1).²x¤,­,².rµ(x)µ(x),²Sd(x)=fs2njsTrµ(x)0g,x²Sf(x)=fs2njs=x0¡x;x02­gx.x¤:x¤2­Sf(x¤)\Sd(x¤)=;I-5'&$%HHHHHHHHY¾qx¤x2­rµ(x¤)­x¤2­;(x¡x¤)Trµ(x¤)¸0;8x2­rµ(x)f(x),(1.1)x2­;(x0¡x)Tf(x)¸0;8x02­:(1.2).I-61.2minfµ(x)jAx=b;x2Xg;(1.3)µ:n!,X½n,A2m£n,b2m.¸Lagrange,(1.3)LagrangeL(x;¸)=µ(x)¡¸T(Ax¡b)X£m,(x¤;¸¤)2X£mL¸2m(x¤;¸)·L(x¤;¸¤)·Lx2X(x;¸¤),µ(x),rµ(x)=f(x),8:x¤2X;(x¡x¤)T(f(x¤)¡AT¸¤)¸0;8x2X;¸¤2m;Ax¤=b:(1.4)I-7¸¤2m;(¸¡¸¤)T(Ax¤¡b)¸0;8¸2m:u=0@x¸1A;F(u)=0@f(x)¡AT¸Ax¡b1Aand­=X£m;,(1.4)u¤2­;(u¡u¤)TF(u¤)¸0;8u2­:µ(x),Fa(u)=0@¡AT¸Ax¡b1A,,Lagrangeu¤2­;µ(x)¡µ(x¤)+(u¡u¤)TFa(u¤)¸0;8u2­u¤.Fa(u)=Mu+q,M,Fa(u).I-81.3minfµ1(x)+µ2(y)jAx+By=bx2X;y2Yg(1.5)µ1(x)µ2(y).¸Lagrange,LagrangeL(x;y;¸)=µ1(x)+µ2(y)¡¸T(Ax+By¡b)X£Y£m,f(x)=rµ1(x),g(y)=rµ2(y).(x¤;y¤;¸¤)2­;8:(x¡x¤)T(f(x¤)¡AT¸¤)¸0;(y¡y¤)T(g(y¤)¡BT¸¤)¸0;(¸¡¸¤)T(Ax¤+By¤¡b)¸0;8(x;y;¸)2­;(1.6)­=X£Y£m:I-9u=0BB@xy¸1CCA;F(u)=0BB@f(x)¡AT¸g(y)¡BT¸Ax+By¡b1CCAFa(u)=0BB@¡AT¸¡BT¸Ax+By¡b1CCA;u¤2­;(u¡u¤)TF(u¤)¸0;8u2­:µ1(x),µ2(y),z=(x;y)u,µ(z)=µ1(x)+µ2(y),(1.5)u¤2­;¡µ(z)¡µ(z¤)¢+(u¡u¤)TFa(u¤)¸0;8u2­:,,,.I-101.4(1.1),­=n+(n-)µ(x),x1.1,x¤x¤¸0;(x¡x¤)Trµ(x¤)¸0;8x¸0:Fn!n.n+VI(n+;F):x¸0;(x0¡x)TF(x)¸0;8x0¸0:.(NCP)x¸0;F(x)¸0;xTF(x)=0:(1.7),NCP­=n+.,­=n+,(1.1).I-11,NCPVI(n+;F).xNCP,x¸0F(x)¸0.x0¸0(x0)TF(x)¸0.xTF(x)=0,(x0¡x)TF(x)=(x0)TF(x)¸0:xVI(Rn+;F).,xVI(Rn+;F),x¸0.x0=0x0=2x(x0¡x)TF(x)¸0,¨xTF(x)¸0.xTF(x)=0.xNCP,F(x)¸0,.F(x)Fj(x)0,x0,x0i=8:xi;ifi6=jxj+1;ifi=jx0¸0.(x0¡x)TF(x)=Fj(x)0,xVI.I-121.5(Leastabsolutedeviations)minkAx¡bk1;(1.8)A2m£n,b2m.,.,.,.²T.Hastie,R.Tibshirani,andJ.Friedman.TheElementsofStatisticalLearning:DataMining,InferenceandPrediction.Springer,secondedition,2009.x10:6.²J.M.Wooldridge.IntroductoryEconometrics:AModernApproach.SouthWesternCollegePublications,fourthedition,2009.x9:6.e1m-.kdk1=maxfyTdjy2B1g;B1=fy2mj¡e·y·eg:I-13,(1.8)minx2nmaxy2B1yT(Ax¡b):min-max.:x¤2n;y¤2B1;8:(x¡x¤)T(ATy¤)¸0;8x2n;(y¡y¤)T(¡Ax¤+b)¸0;8y2B1:u¤2­;(u¡u¤)T(Mu¤+q)¸0;8u2­u=0@xy1A;M=0@0AT¡A01A;q=0@0b1A;­=n£B1:I-142mn...si=Pnj=1xijdj=Pmi=1xijµ´¶³S1µ´¶³D1-x11x1jx1nHHHHHHHHHHHHHj@@@@@@@@@@@@@R..................µ´¶³Siµ´¶³Dj-xi1xijxin©©©©©©©©©©©©©*HHHHHHHHHHHHHj..................µ´¶³Smµ´¶³Dn-©©©©©©©©©©©©©*¡¡¡¡¡¡¡¡¡¡¡¡¡µxm1xmjxmnI-15Si:i;Dj:j;xij:SiDj;si:Si,si=Pnj=1xij;dj:Dj,dj=Pmi=1xij;hsi:Si,Si;hdj:Dj,Dj;tij:SiDj()yi:Si;zj:Dj.I-162.1iSijDj—.nSihsi,yinDjhdj,zj-=tijxij(hsi+yi+tij)¸(hdj+zj),,xij=0xij,(hsi+yi+tij)=(hdj+zj):hsi+yi+tij8:¸hdj+zj;xij=0;=hdj+zj;xij0:I-17²y1;y2;¢¢¢;ymz1;z2;¢¢¢;zn(),xij().X=0BBBBB@x11x12:::x1nx21x22:::x2n.........xm1xm2:::xmn1CCCCCA;F(X)=0BBBBB@F11F12:::F1nF21F22:::F2n.........Fm1Fm2:::Fmn1CCCCCA;I-18Fij(X)=©hsi(si)+yi+tijª¡©hdj(dj)+zjª;si=nXj=1xij;dj=mXi=1xij:,m£nXF(X),.,X¸0;F(X)¸0;Trace(XTF(X))=0:Trace(¢).²si(y;z)=Pnj=1xij(y;z)anddj(y;z)=Pmi=1xij(y;z)(y;z).I-192.2²,si·smaxi;²,dj¸dminj.()²,y1;¢¢¢;ym²,z1;¢¢¢;zn...:I-20²,;y¸0;smax¡s(y;z)¸0;yT(smax¡s(y;z))=0;²,.z¸0;d(y;z)¡dmin¸0;zT(d(y;z)¡dmin)=0:u¸0;F(u)¸0;uTF(u)=0;u=0@yz1A;F(u)=0@smax¡s(u)d(u)¡dmin1A;s(u)d(u)u.,F(u)u,,.I-213,Bridge-1,Bridge-2Bridge-3.YangtseRiverN1N2N3S3S2S1Bridge1Bridge2Bridge31234567891011,N1,N2,N3,S1,S2,S3.I-22.(orientedlink).NiSj,i=1;2;3;j=1;2;3.9O/DO/DPair.O/D!1;:::;!9,O/D,Bridge-1,Bridge-2,Bridge-33().P!jO/D!j.9O/D27(path)p1;:::;p27.[11].O/D!P!Linksonthepath!1=(N1;S1)P!1=fp1;p2;p3gp1=f1gp2=f4;2;11gp3=f4;5;3;10;11g!2=(N1;S2)P!2=fp4;p5;p6gp4=f1;8gp5=f4;2gp6=f4;5;3;10g!3=(N1;S3)P!3=fp7;p8;p9gp7=f1;8;9gp8=f4;2;9gp9=f4;5;3g!4=(N2;S1)P!4=fp10;p11;p12gp10=f7;1gp11=f2;11gp12=f5;3;10;11g!5=(N2;S2)P!5=fp13;p14;p15gp13=f7;1;8gp14=f2gp15=f5;3;10g!6=(N2;S3)P!6=fp16;p17;p18gp16=f7;1;8;9gp17=f2;9gp18=f5;3g!7=(N3;S1)P!7=fp19;p20;p21gp19=f6;7;1gp20=f6;2;11gp21=f3;10;11g!8=(N3;S2)P!8=fp22;p23;p24gp22=f6;7;1;8gp23=f6;2gp24=f3;10g!9=(N3;S3)P!9=fp25;p26;p27gp25=f6;7;1;8;9gp26=f6;2;9gp27=f3g.,I-23..Wardrop¡¡y=(y1;y2;y3),.²0·y23:;²f(y)23:,y;²0b23:.y¸0;F(y)=b¡f(y)¸0;yTF(y)=0:,f(y)y,.,,.,.,.I-2444.1minfcTxjAx=b;x¸0g.A2m£n,b2m,c2n.,b,c.bc,minfmax´2C´TxjAx2B;x2Dg(4.1)C;D½n,B½m..yLagrange¸,(4.1)LagrangeL(x;y;¸;´)=´Tx¡¸T(Ax¡y);(D£B)£(m£C).min-maxL¸2m;´2CL(x¤;y¤;¸;´)·L(x¤;y¤;¸¤;´¤)·Lx2D;y2B(x;y;¸¤;´¤):I-25(x¤;y¤;¸¤;´¤)min-max,8:x¤2D;(x¡x¤)T(¡AT¸¤+´¤)¸0;8x2Dy¤2B;(y¡y¤)T(¸¤)¸0;8y2B¸¤2m;(¸¡¸¤)T(Ax¤¡y¤)¸0;8¸2m´¤2C;(´¡´¤)T(¡x¤)¸0;8´2C:w¤2­;(w¡w¤)T(Mw¤+q)¸0;8w2­w=0BBBB@xy¸´1CCCCA;M=0BBBB@00¡ATI00I0A¡I00¡I0001CCCCA;q=0­=D£B£m£C:I-26(SplitFeasibilityProblem)Findx2DsuchthatAx2B;(4.1).Findx2D;y2B;suchthatAx¡y=0:.¸Ax¡y=0Lagrange,:u¤2­;(u¡u¤)TMu¤¸0;8u2­u=0B@xy¸1CA;M=0B@00¡AT00IA¡I01CA;­=D£B£m:I-274.2[1],,minx2Xmaxy2Y©(x;y):=µ1(x)+yTAx¡µ2(y)(4.2)X½n,Y½m,A2m£n.µ1(x):n!,µ2(y):m!.(x¤;y¤)2X£Y(4.2),©y2Y(x¤;y)·©(x¤;y¤)·©x2X(x;y¤):,(x¤;y¤)©(x;y)X£Y.,(4.2):(x¤;y¤)2X£Y