Luận văn Một phương pháp proximal điểm trong cho bài toán cực tiểu lồi và cho bất đẳng thức biến phân

38 Do m < 1,ta thu du'ejctli ba"td~ngthucnay rang f(xk) :s;f(y*). Dieu nay dfin dSn 1 1 f(xk) + Akd<p(xk,xk)=f(xk) :s; f(y*) :s; f(y*)+ Akd<p(Y*,xk). VI y* Ia nghi~mduy nha"tnen xk =y* vadoB6 de2.6.2tasuyraxkIa cvctieu cua f trenJR!.~. (ii) Ta ky hi~ui(k) la ChIs61~pungvoi xkdu'ejc~pnh~t,nghlala yi(k}= xk+l. Ta dinh nghla "yk- ,i(k} E 8'ljJi(k}(xk+l). Ta bitt rang ,k=- :k <p/(xk,xk+l). Tli nhungky hi~utrentachungminhcackh~ngdinhsau: a. {f(xk)}kh6ngtang.VI f(xk) - f(xk+1)~m[J(xk)- 'ljJi(k}(xk+1)] (2.62) nentheoChtiy 2.6, f(xk) - 'ljJi(k}(xk+l)la ham kh6ngam, do do {f(xk)}cling kh6ngtang.Do dotacothegiasa{f(xk)}bi ch~ndu'oi(nSukh6ngthlf(xk)~ -00 va chungminhxong). b.,kE 8Ekf(xk).Voi Ek= f(xk) - 'ljJi(k}(xk+l)+ :k«p'(xk,xk+1),xk- xk+l). Tli dinhnghlacua,k, tathffyngaydu'ejcrang Ek= f(xk) - 'ljJi(k}(xk+l) - (,k,xk - xk+l). M~tkhacdo f ~ 'ljJi(k}va ,k E 8'ljJi(k}(xk+l)nen Vy, f(y) ~ 'ljJi(k}(y)~ 'ljJi(k}(xk+l)(,k,y - xk+l). (2.63) Trangtru'onghejpd~cbi~t,voi y = xk thl Ek~ O.TIT (2.63)ta co Vy, f(y) ~ f(xk)+'ljJi(k}(xk+l)- f(xk)+(rk,y- xk)+(,k,xk- xk+l), l nghlala,k E 8Ekf(xk). +00 1 c.L {Ek - :\«p' (xk,xk+l),xk - xk+l)} < +00 k=l k Tli (2.62)taco Ek = f(xk) - 'ljJi(k}(xk+l)+ lk«p'(xk,xk+l),xk - xk+l) :s; ~[J(xk) - f(xk+l)] + lk«p'(xk,xk+1),xk - xk+l). 39 Nhuv~y n n I) Ek- :k «I>'(xk,xk+l),xk - xk+l)} ~ ~I)f(xk) - f(xk+l)]k=l k=l - ~[J(xl) - f(xn+l )]. Vi f bi ch~nduoi nen +00 1 L {Ek- ~«I>'(xk,xk+l),xk - xkH)} < +00. k=l k d. f(xk) -+ ! =inf{f(x)Ix 2:O} Day {f(xk)}khongtang,hQitl;lde'nf. Gia su phanchungding! > 1* := inf f(x), nghlala t6nt 0thoaf(y) +8<f(xk),Vkdli IOn.xE!R.P Vi Ek-lk «I>/(xk,xk+l),xk- xk+l)-+ 0 nen t6nt<;likod~voi k 2:kothl Ek- ~«I>/ (xk xk+l) Xk - k+l) 8, ' , x <- /\k 2' Tu B6 d€ 2.2.2voi a =xk,b=xkH va c=y, taco Ily- xk+1112-Ily - xkl12~-t(y - xk+l, (xk,xk+l)) = - t(y - xk, I(xk, xk+1)) - t(xk - xk+1,I(xk ,xk+1)). Tu (2.64),taco ngay -t(xk - xk+l,/(xk,xk+l))<~k(~- Ek) M~tkhactuph~nb va ryk= -lk '(xk, xk+l) E OEkf(xk) ta du<;5c -t(y - xk,I(xk,xk+l)) = ~k(ryk,Y - xk) va f(Xk)- 8>f(y) 2:f(xk)+(-l, y - xk)- Ek' Ke'th<;5pvoi (2.67)va (2.68)tadu<;5c 1 k I k k+l Ak - e(y- x , (x ,x ))<e [-8+Ek]. Cu<3iclingtu (2.65),(2.66)va (2.69)tadu<;5c k+1 2 k 2 Ak 8 k 2 8 lIy - x II <lIy - x II +-[- - Ek - 8+Ek] =lIy - x II - Ak-'- () 2 2() (2.64) (2.65) (2.66) (2.67) (2.68) (2.69) 40 Liy t6ngbit ding thuetrenvoi mQik >kotadu'Qe k-l (y 0 ::; Ilxk - yl12::; Ilxko- yl12- 2() L Ak' k=ko += Cho k --t +00 thl L Ak ::;2: Ilxko - yl12< +00,di€u nay mall thuffnvoi gia thie't. k=ko BaygiGtagiasil'f co eveti€u x trenIR~va {Ad bi eh~n. e. {xk}bi eh~n Dungbit ding thue(2.65)voiy =x tadu'Qe Ilxk+l- xl12::; Ilxk- xl12 - t(x- xk, '(xk, xk+l)) - t(xk - xk+l, '(xk, xk+l)). Tli dinhnghlaeuaryk= -lk '(xk,xk+l) E OEkf(xk),ta co -b(x - xk,'(xk,xk+l)) = ~k(ryk,x- xk) ::; ~k[f(x)- f(xk)+Ek]::;~kEk. Do do Ilxk+l- x112::;Ilxk- xl12+ ~k[Ek- :k «1>'(xk,xk+l),xk- xk+l)]. Vi {Ak}bi eh~n( dogiathie't), apd1;1ngph~ne taco +=A 1 L ()k[Ek- :\«1>'(xk,xk+l),xk- xk+l)]<+00. k=l k Dung B6 d€ 2.1 ta suyra {llxk- xllhhQit1;1.V~y{xk}bi eh~n. f. MQi di€m gioi h<;lnx* eua{xk}Ia eveti€u eua f tren IR~va xk --t x* Cho xnk --t x*. VI f lien t1;1enen f(xnk)--t f(x*). Ap d1;1ngph~nd, f(xk) --t J = inf f(x). Do do f(x*) = j. VI x*E IR~nenx* la eveti€u euahamf trenIR~. xER~ Tli (2.70)thayx bdix* ta du'Qe Ilxk+l- x*112::;Ilxk- x*112+(yk, (2.70) trongdo {y= Ak[E - ~«1>' (xk xk+l ) xk - xk+l)] k () k Ak " . += Vi L (jk <+00 nenapd1;1ngmQtke'tquaeuaCorreavaLemareehal([7],M~nh k=l d€ 1.3)thl toanbQday {xk}hQit1;1de'nx*. . 41 2.7 Ktt quatinh toan86. f)~ thu~tgi<lidti d~Hdu'Qc,ta cin gi<libai toancon sail { mill 7/Ji(y)+ 1kd<p(y,xk), Y E JR~+. V(ji 7/Ji(y)= max{f(yj) +(s(yj),Y-yj) I j =0,. . . ,i-I}, baitoantrentu'dngdu'dng v(ji (SPh,i mill v +1kd<p(Y,xk), v 2:f(yj) + (s(yj),y - yj) j =0,. . . , i-I, Y E JR~+. Ta tha'ydng ne'u(yi,vi) la nghi~mcuabai toantrenthl Vi=max{f(yj)+(s(yj),y - yj)}. Vi r.p(t)= ~(t- 1)2+p,(t-logt - 1)nenhamml,lctieu cua bai toan(SPk,i) "cvc ky" phi tuye'nva vi~cHmnghi~mcuabai toan(SPk,i)co th~ra'tkho khan.Tuy nhien,ne'u P d<p(y,xk)= L(x~)2r.p(Y;),xm=1 m thlhamml,lctieula tachdu'QCva cachgi<libai toantrenIa tagi<libai toand6i ng~ucuano. V(ji mQim,tad~tZm= ;7:va Z= (zm)thlbai toan(SPk,i)co th~Tn vie't l(,linhu'sail (MSPh,i p mm v +L amr.p(zm), m=1 (sj Z) - v <b., - J' j=0,...,i-1, Z E JR~+, t d ' - ~ ( k )2 j - ( j ) k - 1 ' b. - ( ( j ) j ) - f( j ) '-rang 0 am - Ak xm , sm - S Y xm' m - ,..., p va J - s y ,y y, J - 1,..., i-I. HamLagrangetu'dnglingv(jibaitoan(MSP)k,ila p i-I L(v,z,p,)=v+L amr.p(Zm)+ LP,j [(sj, z) - v - bj] m=1 j=O va hamd6ing~u la d(p,)= inf{L(v,z,p,) I v E JR,z > O} ! inf{t amr.p(zm)+ ~p'j[(sj,z) - bj]}- z>o - m=1 j=O -00 i-I ne'uL p,j = 1, j=1 ngu'Qcl(,li. 42 Do v~yb~titmlnd6ing§:utu'onglingIa { max d(~), L ~j =1 (D) ~j2::0,j=O"",i-l, trongdo P i-I d(~)=L dm(~)- L ~jbj, m=I j=O i-I dm(~)= inf{G:ma}, j=O <p(zm)=z~- Zm-log Zm' Honnua,m6ihamdmla khclvi va Vdm(~)= (stnz~- bj)O~j~i-I' i-I trongdo z~= argmin{G:ma}. j=O Vi (D) Ia bai tmlntrailnenhammvctieucuano de u'oc1u'<;Jng,ta co th~sa dvngba'tky phu'ongphapc6 di~nnaod~giclino. GQi~* la nghit%mcuabai toan(D) thlz*= (z~)trongdo i-I z:n= argmill {G:m<p(zm)+L ~;stnzm}, j=O va i-I i-I * - (~ * j *) ~ *b'v - ~ ~js ,Z - ~ ~j J j=O j=O la nghit%mcuabai toan(SPk,i).Th~tv~y,dodi€u kit%ndQIt%chbli taco i-I L~;[(sj, z*) - v* - bj] =0, j=O i-I Vi L~; =1nen j=o i-I i-I i-I * - ~ * * - (~ * j *) ~ *b'v - ~~jV - ~~jS ,Z - ~~j J' j=o j=o j=o 43 Thi dl;l: f(x) =max{fj(x)=xTQ(j)x+(cj? x,j = 1,..., 5} yoi Q~k= etcos(ik)sinj,i < k Qii = *Isinjl+L IQikl i=/=k cj = e}sin(ij),i=l,...,n. ChQn: xQ = (1 1 1 1 1 1 1 1 1 1 ) A = 0.1000 m = 0.4000 Tieu chuffndung: Ilxold- xl12~ 0.001000 Gi<itItbandffucuahamI.jJ 5337.0664 Ke'tqua: 2 61.74627860 1 3 16.821912574 4 7.51790296 2 5 2.74151481 4 6 1.62981397 3 7 0.32026335 4 8 0.02442314 5 9 -0.06580683 6 10 -0.14407693 10 11 -0.16407434 8 12 -0.17470473 9 13 -0.17881529 8 14 -0.18039020 13 15 -0.18219034 10 16 -0.18263927 14 17 -0.17967192 40 18 -0.18234564 13 19 -0.18315244 11 20 -0.18042678 40 Solution: 0.00000.00060.01210.03630.07730.00000.07210.07440.04590.0189 f = -0.18042678