中职 优化计算方法及其MATLAB程序实现第5章电子课件 高教版 .pdf

《中职 优化计算方法及其MATLAB程序实现第5章电子课件 高教版 .pdf》由会员分享，可在线阅读，更多相关《中职 优化计算方法及其MATLAB程序实现第5章电子课件 高教版 .pdf（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/55JJIIJIBackClosezO9MATLABSy1 2/55JJIIJIBackClose130?:k?,?Hesse?G(xk)=2f(xk)?,U?y?)?8I3xk?e.AO/,?G(xk),UY?1e?.+?,?k?Jr,LL?K?.d?,?zS“I8I?,=Hesse?,u5?KO?.?=0?:.20-V50c“,InDavidongJ?.?,?$FletcherPowelly?ykQq-?.3?20cp,?zK?9:.3OLIO8I?Hesse?,%3,ekHesse?.d,)?zK3/55JJIIJIBackClose?k?.5.195?g:3?2Hesse?Gk=2

2、f(xk)?,Cq?Bk?“Gk.,BkAke?nA:(1)3,ekBk Gk,?A?)?Cqu,(?k?;(2)k?k,Bk?,l?)?f3xk?e;(3)?Bk#5K?,=12?1?.e0?vnA:?Bk?E.?f:Rn R34/55JJIIJIBackClosem8D Rn?gY.o,f3xk+1?gCq?.f(x)f(xk+1)+gTk+1(x xk+1)+12(x xk+1)TGk+1(x xk+1).?,?g(x)gk+1+Gk+1(x xk+1).-x=xk,sk=xk+1 xk,F?yk=gk+1 gk,KkGk+1sk yk.5?,u?gf,(?.y3,3?EHesse?Cq

3、?BkvX,=Bk+1sk=yk.(5.1)(5.1).-Hk+1=B1k+1,K?5/55JJIIJIBackClose?,/:Hk+1yk=sk,(5.2):Hk+1Hesse?_?Cq.|ddk=HkgkBkdk=gk(.Bk(Hk)?1nA:,-Bk+1=Bk+Ek,Hk+1=Hk+Dk,(5.3):Ek,Dk12?.d(5.1)(5.2)?5K(5.3)(?.e0?1?.3(5.3)?Ek=ukuTk(1?),R,uk Rn.d(5.1),?(Bk+ukuTk)sk=yk,6/55JJIIJIBackClose=k(uTksk)uk=yk Bksk.(5.4)(5.4)Luk1uyk

4、 Bksk,=3?uk=(yk Bksk).dkEk=2(yk Bksk)(yk Bksk)T.u,d(5.4),?2(yk Bksk)Tsk(yk Bksk)=yk Bksk.dd,e(yk Bksk)Tsk6=0,?2(yk Bksk)Tsk=1,=2=1(yk Bksk)Tsk,Ek=(yk Bksk)(yk Bksk)T(yk Bksk)Tsk.?1?Xe:Bk+1=Bk+(yk Bksk)(yk Bksk)T(yk Bksk)Tsk.(5.5)7/55JJIIJIBackCloseaq/,|(5.2),Hk?11?,?Hk+1=Hk+(sk Hkyk)(sk Hkyk)T(sk Hk

5、yk)Tyk.(5.6)k?1?,|?E)?zK?,Xe.5.1(1)0,?:x0 Rn,?0 6?1,?H0(?In).-k:=0.1,ekgkk 6,xkCq4?:.2,O|dk=Hkgk.3,|Efk.4,-xk+1:=xk+kdk,d1?(5.6)(Hk+1.8/55JJIIJIBackClose5,-k:=k+1,=1.euArmijo(|?1?MATLABS.S5.1(1S)function k,x,val=sr1(fun,gfun,x0,epsilon,N)%U:1)?K:min f(x)%:fun,gfunO8I9F,x0:,%epsilonNN?,NS“g%:kS“g,x,v

6、alOCq:if nargin5,N=1000;endif nargin4,epsilon=1.e-5;endbeta=0.55;sigma=0.4;n=length(x0);Hk=eye(n);k=0;9/55JJIIJIBackClosewhile(kN)gk=feval(gfun,x0);%OFdk=-Hk*gk;%O|if(norm(gk)epsilon),break;end%u?OKm=0;mk=0;while(m20)%Armijo|if(feval(fun,x0+betam*dk)x0=1.0;1.0;12/55JJIIJIBackClose k,x,val=sr1(fun,gf

7、un,x0)fun,gfunO8I9F?m.5.2 BFGS9MATLAByBFGS?8c61k?,dBroy-den!Fletcher!GoldfarbShanno31970cgJ?,?BFGS.?g:3(5.3)?Ek2?Ek=ukuTk+vkvTk,:uk,vk Rn;,R.u,d(5.1),?(Bk+ukuTk+vkvTk)sk=yk,13/55JJIIJIBackClose?d/(uTksk)uk+(vTksk)vk=yk Bksk.(5.7)Juy,v(5.7)?ukvk,?ukvkO1uBkskyk,=-uk=Bksk,vk=yk,?.ukEk=2BksksTkBk+2ykyTk

8、.uk,vk?L“(5.7),?(Bksk)Tsk?(Bksk)+?(yk)Tsk?(yk)=yk Bksk,?n,?2(sTkBksk)+1?Bksk+?2(yTksk)1?yk=0.14/55JJIIJIBackClose?d,-2(sTkBksk)+1=092(yTksk)1=0,=2=1sTkBksk,2=1yTksk.l?Xe?BFGS2?Bk+1=BkBksksTkBksTkBksk+ykyTkyTksk.(5.8)w,d(5.8),eBk,K?Bk+1,yBFGS?kXe5.n5.1?Bk?,Bk+1dBFGS?(5.8)(,oBk+1?yTksk 0.y 75w,?.yTksk

9、=sTkBk+1sk,?eBk+1?,Kw,kyTksk 0.15/55JJIIJIBackCloseey5.?yTksk 0Bk?.d(5.8),?0 6=d Rn,kdTBk+1d=dTBkd(dTBksk)2sTkBksk+(dTyk)2yTksk.(5.9)Bk?,?3?B1/2k,?Bk=B1/2kB1/2k.l?,|Cauchy-Schwarz?,?(dTBksk)2=?(B1/2kd)T(B1/2ksk)?26 kB1/2kdk2kB1/2kskk2=(B1/2kd)T(B1/2kd)(B1/2ksk)T(B1/2ksk)=(dTBkd)(sTkBksk).(5.10)Juy,?

10、(5.10)?3k6=0,?B1/2kd=kB1/2ksk,=d=ksk.16/55JJIIJIBackClose?d(5.9)(5.10),?dTBk+1d dTBkd(dTBkd)(sTkBksk)sTkBksk+(dTyk)2yTksk=(dTyk)2yTksk 0.l?,?d Rn,d 6=0,okdTBk+1d 0.y.?n5.1L,e?B0?3S“L?yTksk 0(k 0),KdBFGS?)?S?Bk?,l?|Bkd=gkk)dk,dkf3xk?e.n5.2e3BFGS(|Wolfe|OK,KkyTksk 0.y 5?,u(|kgTk+1dk=0,?yTksk=k(gk+1 gk

11、)Tdk=kgTkdk 0.17/55JJIIJIBackCloseuWolfe|OK,|TOK?1?(=f(xk+kdk)TdkgTkdk),?yTksk=k(gk+1 gk)Tdk k(1)gTkdk=k(1 )gTkdk 0.y.?kyL,Armijo|OKU?yyTksk 0.?ArmijoOKuSy?0.(5.11)18/55JJIIJIBackCloseJuy,B0?,?(5.11)?y?S?Bk?5.euArmijo(|OK?BFGS?.5.2(BFGS)0,?(0,1),(0,0.5),:x0 Rn,?0 6?1,?B0(?G(x0)?In).-k:=0.1,Ogk=f(xk)

12、.ekgkk 6,xkCq4?:.2,)5|Bkd=gk,(5.12)?)dk.19/55JJIIJIBackClose3,?mkve?K?m:f(xk+mdk)6 f(xk)+mgTkdk.(5.13)-k:=mk,xk+1:=xk+kdk.4,d?(5.11)(Bk+1.5,-k:=k+1,=1.euArmijo(|?BFGS?MATLABS.S5.2(BFGSS)function k,x,val=bfgs(fun,gfun,x0,varargin)%U:BFGS)?K:min f(x)%:fun,gfunO8I9F,x0:,%varargin?CC,NBFGS?20/55JJIIJIBa

13、ckClose%,?eSNTSu-?%:kS“g,x,valOCq:N=1000;%S“gepsilon=1.e-5;%NN?beta=0.55;sigma=0.4;n=length(x0);Bk=eye(n);k=0;while(kN)gk=feval(gfun,x0,varargin:);%OFif(norm(gk)epsilon),break;end%u?OKdk=-Bkgk;%)|Bk*dk=-gk,O|m=0;mk=0;while(m20)%Armijo|21/55JJIIJIBackClosenewf=feval(fun,x0+betam*dk,varargin:);oldf=fe

14、val(fun,x0,varargin:);if(newf0)Bk=Bk-(Bk*sk*sk*Bk)/(sk*Bk*sk)+(yk*yk)/(yk*sk);22/55JJIIJIBackCloseendk=k+1;x0=x;endval=feval(fun,x0,varargin:);5.2|BFGS(S5.2)?zKminxR2f(x)=2(x1 x22)2+(x2 2)2.TKk?4?:x=(4,2)T,4?f(x)=0.)5.1?O8I9F?m,-#|.|S5.2,OK?kf(xk)k 6 105.?:,(JXL5.2?.23/55JJIIJIBackCloseL5.2 BFGS?(J:

15、(x0)S“g(k)8I(f(xk)(1.0,1.0)T106.0956 1014(1.0,1.0)T132.4356 1012(2.0,1.0)T161.9396 1015(1.0,2.0)T123.8232 1015(10.0,10.0)T202.0524 1017L5.1w,BFGS1k?.5.3 DFP9MATLAByDFP?1?,1959cdDavidonJ?,?FletcherPowell)U?,DFP,)?zKk?.aquBFGS?,?DFP?Xe:Hk+1=HkHkykyTkHkyTkHkyk+sksTksTkyk.(5.14)24/55JJIIJIBackClose?,Juy

16、,d(5.14),eHk,?Hk+1,aqun5.1?y,?DFP?Xe5.n5.3?Hk?,Hk+1dDFP?(5.14)(,oHk+1?sTkyk 0.aqun5.2,y,?(|Wolfe|OK,?S?Hk?5sTkyk 0?v.?5,Armijo|OKUv,IXe?:Hk+1=Hk,sTkyk6 0,HkHkykyTkHkyTkHkyk+sksTksTkyk,yTksk 0.(5.15)euArmijo(|OK?DFP?.25/55JJIIJIBackClose5.3(DFP)0,?(0,1),(0,0.5),:x0 Rn,?0 6?1,?H0(?G(x0)1?In).-k:=0.1,O

17、gk=f(xk).ekgkk 6,xkCq4?:.2,O|:dk=Hkgk.(5.16)3,?mkve?K?m:f(xk+mdk)6 f(xk)+mgTkdk.(5.17)-k:=mk,xk+1:=xk+kdk.4,d?(5.15)(Hk+1.26/55JJIIJIBackClose5,-k:=k+1,=1.euArmijo(|?DFP?MATLABS.S5.3(DFPS)function k,x,val=dfp(fun,gfun,x0,epsilon,N)%U:DFP)?zK:min f(x)%:fun,gfunO8I9F,x0:,%epsilonNN?,NS“g%:kS“g,x,valOC

18、q:if nargin5,N=1000;endif nargin4,epsilon=1.e-5;endbeta=0.55;sigma=0.4;n=length(x0);Hk=eye(n);k=0;27/55JJIIJIBackClosewhile(kN)gk=feval(gfun,x0);%OFif(norm(gk)epsilon),break;end%u?OKdk=-Hk*gk;%O|m=0;mk=0;while(m20)%Armijo|if(feval(fun,x0+betam*dk)0)Hk=Hk-(Hk*yk*yk*Hk)/(yk*Hk*yk)+(sk*sk)/(sk*yk);endk

19、=k+1;x0=x;endval=feval(fun,x0);5.3|DFP(S5.3)?zKminxR2f(x)=2(x1 x22)2+(x2 2)2.TKk?4?:x=(4,2)T,4?f(x)=0.29/55JJIIJIBackClose)|S5.3,OK?kf(xk)k 6 105.?:,(JXL5.3?.L5.3 DFP?(J:(x0)S“g(k)8I(f(xk)(1.0,1.0)T92.0346 1011(1.0,1.0)T145.8598 1013(2.0,1.0)T181.4094 1016(1.0,2.0)T208.5698 1015(10.0,10.0)T681.5793

20、1013L5.2w,DFP?O?q?XBFGS.5.4 Broydenx9MATLAByc?BFGSDFP?,dykBksk(skHkyk)|?2?.?!?dBFGSDFP?30/55JJIIJIBackClose5|?)?a?xBk+1=kBDFPk+1+(1 k)BBFGSk+1(5.18)=BkBksksTkBksTkBksk+ykyTksTkyk+kukuTk,(5.19):k;ukde,=uk=qsTkBksk?ykyTkskBksksTkBksk?.(5.20)a?Broydenx.Juy,3(5.19),?k=0,=?BFGS?;?k=1,=?DFP?.A/,uHk?Broyde

21、nx?Hk+1=kHBFGSk+1+(1 k)HDFPk+1(5.21)=HkHkykyTkHkyTkHkyk+sksTksTkyk+kvkvTk,(5.22)31/55JJIIJIBackClose:k;vkde,=vk=qyTkHkyk?skyTkskHkykyTkHkyk?.(5.23)ykkm?Xk=1 k1 k(1 k),(5.24)k=(sTkBksk)(yTkHkyk)(sTkyk)2.JuyuTksk=0vTkyk=0,dBroydenx(5.19)(5.22)?u?kkv(5.1)(5.2).eBroydenx?5.n5.1Broydenx)4?z?g8IKminxRnf(x

22、)=12xTAx bTx.(5.25)32/55JJIIJIBackCloseXJ?H0?,?)?S“:?p?,K(1)?yTksk 0k 0k 0,Broydenx?5;(2)3(|e,?)?|d0,d1,dk(k 6n 1)v1?dTiAdj=0,0 6 i j 6 k;2?Hkyi=si,0 6 i 6 k1.ydu(1)?yn5.1aq,e=y(2).k8B.5?si=xi+1 xi=idi,yi=gi+1 gi=A(xi+1 xi)=Asi.o,?k=1,d(5.2)H1y0=s033/55JJIIJIBackClose,kdT0Ad1=(Ad0)Td1=10(As0)TH1g1=1

23、0yT0H1g1=10sT0g1=dT0g1=0,=?k=1,(.?k=l,(,yy?k=l+1(.d8Bb?,kdTiAdj=0,0 6 i?1?1n0.e1o.5?,1(yTlHlyl)vlvTlyi=?slyTlslHlylyTlHlyl?slyTlslHlylyTlHlyl?Tyi=slsTlyi(yTlsl)2+HlylyTlHlyi(yTlHlyl)2slyTlHlyi(yTlsl)(yTlHlyl)HlylsTlyi(yTlsl)(yTlHlyl)=sl(sTlAsi)(yTlsl)2+HlylyTlsi(yTlHlyl)2slyTlsi(yTlsl)(yTlHlyl)Hlyl(

24、sTlAsi)(yTlsl)(yTlHlyl)35/55JJIIJIBackClose=0+Hlyl(sTlAsi)(yTlHlyl)2sl(sTlAsi)(yTlsl)(yTlHlyl)0=0.?kHl+1yi=si,0 6 i 6 l 1.(5.27)qHl+1yl=slv,(5.27)u0 6 i 6 l.eydTiAdj=0,0 6 i 0.(5.31):vkde,=vk=qyTkHkyk?skyTkskHkykyTkHkyk?.5,-k:=k+1,=1.euArmijo(|?Broydenx?MAT-LABS.S5.4(BroydenxS)function k,x,val=broyd

25、en(fun,gfun,x0,epsilon,N)40/55JJIIJIBackClose%U:Broydenx)?zK:min f(x)%:fun,gfunO8I9F,x0:,%epsilonNN?,NS“g%:kS“g,x,valOCq:if nargin5,N=1000;endif nargin4,epsilon=1.e-5;endbeta=0.55;sigma=0.4;phi=0.5;n=length(x0);Hk=eye(n);k=0;while(kN)gk=feval(gfun,x0);%OFif(norm(gk)epsilon),break;end%u?OKdk=-Hk*gk;%

26、O|m=0;mk=0;41/55JJIIJIBackClosewhile(m20)%Armijo|if(feval(fun,x0+betam*dk)=feval(fun,x0)+sigma*betam*gk*dk)mk=m;break;endm=m+1;end%Broydenx?x=x0+betamk*dk;sk=x-x0;yk=feval(gfun,x)-gk;Hy=Hk*yk;sy=sk*yk;yHy=yk*Hk*yk;if(sy0.2*yHy)theta=0.8*yHy/(yHy-sy);42/55JJIIJIBackClosesk=theta*sk+(1-theta)*Hy;sy=0.

27、2*yHy;endvk=sqrt(yHy)*(sk/sy-Hy/yHy);Hk=Hk-(Hy*Hy)/yHy+(sk*sk)/sy+phi*vk*vk;x0=x;k=k+1;endval=feval(fun,x0);5.4|Broydenx(S5.4)?zKminxR2f(x)=2(x1 x22)2+(x2 2)2.TKk?4?:x=(4,2)T,4?f(x)=0.43/55JJIIJIBackClose)|S5.4,?=0.5,OK?kf(xk)k 6105.?:,(JXL5.4?.L5.4 Broydenx?(J:(x0)S“g(k)8I(f(xk)(1.0,1.0)T101.6903 1

28、014(1.0,1.0)T131.2482 1018(2.0,1.0)T146.3962 1016(1.0,2.0)T111.4843 1013(10.0,10.0)T153.1705 1014lL5.4w,?,?Broydenx?O?JuBFGSDFP.5.5?5?!?5,u(|?BFGS?5Q-55n.?B,44/55JJIIJIBackCloseBFGS?S“EXe:xk+1=xk kB1kgk,(5.32)Bk+1=BkBksksTkBksTkBksk+ykyTkyTksk,(5.33):sk=xk+1 xk;yk=gk+1 gk;kd(|?.3?5c,kXeb?.b?5.1(1)f(

29、x)3Rn?Y;(2)Y8L(x0)=x Rn|f(x)6 f(x0)8,f3L(x0),=30 0,?kG(x)G(x)k 6 Lkx xk,x N(x,).3?,I?2?1?,=det?I+w1wT2+w3wT4?=(1+wT1w2)(1+wT3w4)(wT1w4)(wT2w3),(5.35):wi(i=1,2,3,4)?n.e?5n.n5.2?BkdBFGS?(5.33)?)?S?,kvArmijoOK(2.14)?f.ef(x)vb46/55JJIIJIBackClose?5.1(1)(2),odS“(5.32)?)?S?xk?f(x)?4?:x.y ArmijoOKe?|?n2.3,

30、I?y|dkKFgk?Y?kv(2.16),=0 0=.dyk?,?yk=gk+1 gk=Z10G(xk+tsk)skdt,(5.36)?kyTksk=Z10sTkG(xk+tsk)skdt.47/55JJIIJIBackClose|b?5.1(2),?yTksk mkskk2,=ak,yTkskkskk2 m.(5.37)d(5.36),?kykk 6Z10kG(xk+tsk)skkdt 6 kskkZ10kG(xk+tsk)kdt.(5.38)Juy,db?5.1(2),kmaxxL(x0)kG(x)k=maxxL(x0)supd6=0|dTG(x)d|kdk26 M.d,d(5.38)?

31、kykk 6 Mkskk.(5.37),kbk,kykk2yTksk6kykk2mkskk26M2m,b.BFGS?Bk+1=BkBksksTkBksTkBksk+ykyTkyTksk,48/55JJIIJIBackClose,?tr(Bk+1)=tr(Bk)kBkskk2sTkBksk+kykk2yTksk.(5.39)?BuA(5.35),BFGS?Xe/:Bk+1=BkhI+?1sTkBksksk?(sTkBk)+?1sTkykB1kyk?yTki,Bk?I+w1wT2+w3wT4?.|(5.35),?det?Bk+1?=det?Bk?wT1w4?=det?Bk?sTkyksTkBksk

32、.(5.40)Pck,sTkBkskkskk2,49/55JJIIJIBackCloseKkBkskk2sTkBksk=?kskkkBkskksTkBksk?2sTkBkskkskk2=ckcos2k.(5.41)ud(5.40),kdet?Bk+1?=det?Bk?sTkykkskk2kskk2sTkBksk=det?Bk?akck.(5.42)u?B,(B)=tr(B)ln(det(B),Kk(B)0.,?0 0.d(5.39)!(5.41)(5.42),?(Bk+1)=tr(Bk+1)ln(det(Bk+1)=tr(Bk)kBkskk2sTkBksk+kykk2yTksk ln?det?

33、Bk?akck?=(Bk)ckcos2k+bk lnak+lnck=(Bk)+(bk lnak 1)+?1 ckcos2k+lnckcos2k?+lncos2k6(Bk)+lncos2k,?|?(t)=1t+lnt3m(0,)?59ak mbk6b,?blnm1 bklnak1.51/55JJIIJIBackCloseuk0 0,3k0 0?k?k k0,klncos2k 2.d(5.43),?0 0,?k?k K,kcosk.uaqun2.3?yL,kgkkkK 0.f(x)3Y8?,-:?4?:?,?B?S?xk?f(x)?4?:x.y.?eQ-5?7.n5.3?f(x)vb?5.1,Bk

34、?S?.eS“xk+1=xk B1kgk,x0 Rn(5.44)53/55JJIIJIBackClose?)?S?xkuf(x)?-:x,Kxk Q-5?x?7limkkBk G(x)dkkkdkk=0,(5.45):dk=xk+1 xk;G(x)=2f(x).y?dNk=G1kgk.ky(5.45)?dukdk dNkk=o(kdkk).(5.46),e(5.45),Kkdk dNkk=kG1k?Gkdk+gk?k=kG1k?Gk Bk?dkk 6 kG1kk k?Gk Bk?dkk6 C?kGk G(x)dkk+kG(x)Bkdkk?=o(kdkk).54/55JJIIJIBackClos

35、e,e(5.46),5?kGkkk.?,?kkGk(dk dNk)k=o(kdkk).dGkdNk=gk=Bkdk,kk(Gk Bk)dkk=o(kdkk).d9G(x)?Y5=?(5.45).5?5(Jkxk+dNk xk 6 Ckxk xk2,ukkdkk kxk xk 6 kxk+dk xk6 kxk+dNk xk+kdk dNkk55/55JJIIJIBackClose6 Ckxk xk2+o(kdkk).dd?kdkk=O(kxk xk),2“,?kxk+dk xk=o(kxk xk).d?n?y.y.?,y/?BFGS?Q-5n,?yLz16.n5.4?f(x)vb?5.1,x0B0?:?.xkdBFGS?)?S“S?ub?5.1(3)?x.o,eXk=1kxk xk ,KxkQ-5ux.