中职 优化计算方法及其MATLAB程序实现第8章电子课件 高教版 .pdf
1/37JJIIJIBackClosezO9MATLABSy1l 52/37JJIIJIBackClose?zK?5,?5m?X.d?,?zK?5.?55?E5?zK?:.8.1?K?5?!?5ue?Kmin f(x),x Rn,s.t.hi(x)=0,i=1,2,l.(8.1)?K?B,K(8.1)?.KFL(x,)=f(x)lXi=1ihi(x),(8.2):=(1,2,l)Tf.3/37JJIIJIBackClosee?.KFn?K(8.1)?4?7,?KKT(Karush-Kuhn-Tucker).n8.1(.KFn)b?xK(8.1)?4?:,f(x)hi(x)(i=1,2,l)3x?,?SY.e|hi(x)(i=1,2,l)5,K3f=(1,2,l)T?xL(x,)=0,=f(x)lXi=1ihi(x)=0.y PH=?h1(x),h2(x),hl(x)?.4/37JJIIJIBackClosedn?b?H?.d,el=n,KH_?,l?H?Rn?|,?3 Rl(l=n)?f(x)=lXi=1ihi(x),d(?y.e?l uz?,?yh(u(z),z)u(z)+zh(u(z),z)=0,?u(z)=HT1HT2.(8.3)3zNC,dh(u(z),z)=0z?zKminzRnlf(u(z),z)?4?:,?kzf(u(z),z)=0,6/37JJIIJIBackClose=u(z)Tyf(y,z)+zf(y,z)=0.5?x=(y,z),(8.3)“,?H2H11yf(x)+zf(x)=0.-=H11yf(x),Kkyf(x)=H1,zf(x)=H2.5=f(x)=yf(x)zf(x)=H1H2=lXi=1ihi(x).y.?7/37JJIIJIBackClose?K?7,I?(8.2)?.KFL(x,)?Fux?Hesse?.OLXe:L(x,)=xL(x,)L(x,)=f(x)lPi=1ihi(x)h(x),2xxL(x,)=2f(x)lXi=1i2hi(x).XJ8I?Y?,K?5.n8.2u?K(8.1),b?f(x)hi(x)(i=1,2,l)?Y?,3(x,)Rn Rl?L(x,)=0.e?0 6=d Rn,hi(x)Td=0(i=1,2,l),kdT2xxL(x,)d 0,KxK(8.1)?8/37JJIIJIBackClose4?:.yy.ex4?:,K73?N(x,)9ux?S?xk,?xk N(x,),xk6=x,kf(x)f(xk),hi(xk)=0,i=1,2,l,k=1,2,.-xk=x+kzk,k 0,kzkk=1,S?(k,zk)kf?u(0,z)kzk=1.d?V,?0=hi(xk)hi(x)=kzTkhi(x+ikkzk),ik(0,1).k,-k ,?hi(x)Tz=0,i=1,2,l.(8.4)9/37JJIIJIBackClose2d?Vm,?L(xk,)=L(x,)+kxL(x,)Tzk+122kzTk2xxL(x,)zk+o(2k).duxkv?,?k0 f(xk)f(x)=L(xk,)L(x,)=122kzTk2xxL(x,)zk+o(2k).k/2,?zTk2xxL(x,)zk+o(22k)2k6 0.?4(k ),?(z)T2xxL(x,)z6 0.duzv(8.4),?g.d,x4?:.y.?10/37JJIIJIBackClose8.2?K?5?!e?zK?5:min f(x),x Rn,s.t.gi(x)0,i=1,2,m.(8.5)P1D=x Rn|gi(x)0,i=1,2,m,I8I=1,2,m.?K?5I?k?k?Vg.u1:x,=x D.dUy/,=k?vgi(x)=0,?,?Kvgi(x)0.u?/,3 x?,?SE,?gi(x)0,?cK?5.d,k7r/m5.8.1eK(8.5)?1:x D?gi(x)=0,K?gi(x)0 x?k?.,ekgi(x)0,K11/37JJIIJIBackClose?gi(x)0 x?k?.8I(x)=i|gi(x)=0(8.6)x?k?I8,x?k?8(48).e?n?K5?:.n8.1(Farkasn)?a,bi Rn(i=1,2,r).K5?|bTid 0,i=1,2,r,d Rn?aTd 0N?3K1,2,r,?a=rPi=1ibi.12/37JJIIJIBackClosey 5.=3K1,2,r,?a=rPi=1ibi.?d RnvbTid 0(i=1,2,r),okaTd=rXi=1ibTid 0.75.?kvbTid 0(i=1,2,r)?dvaTd 0.y.?(,=a 6 C=?x Rn?x=rXi=1ibi,i 0,i=1,2,r?.?a0 Ca3IC?K,=ka0 ak2=minxCkx ak2,KkaT0(a0 a)=0.13/37JJIIJIBackClose(1)kyu?u C,7kuT(a0 a)0.,e,K3u C,uT(a0 a)0.5?CIa0,u C,?a0+u C.dkka0+u ak2 ka0 ak2=2 0(u C).(2)y?d=a0a.dubi C,od(1)?(?bTid 0,?d75?b?AkaTd 0.?,kaTd=aT(a0 a)=aT(a0 a)aT0(a0 a)=(a0 a)T(a0 a)=ka0 ak2 0,b?g,75?y.y.?e?GordannFarkasn?.14/37JJIIJIBackClosen8.2(Gordann)?bi Rn(i=1,2,r).5?|bTid 0,i=1,2,r,d Rn(8.7)?bi(i=1,2,r)5,=3?0?Ki(i=1,2,r),?rXi=1ibi=0.(8.8)y5.y.?(8.7)k),=3,d0,?bTid0 0,i=1,2,r.uu?0?Ki(i=1,2,r),krPi=1ibTid0 0.P0=max16i6rbTid,K7k0 00 bTid 0,i=1,2,r.e?Er+2n+1:d=d,a=10,bi=1bi,i=1,2,r,0.(8.9)oJ?yvFarkasn?,=bTid=bTid 0 bTid 0,i=1,2,r,aTd=0.?dFarkasn,3K1,2,r,?a=rXi=1ibi.16/37JJIIJIBackClose(8.9)“,?rXi=1ibi=0,rXi=1i=1.75?y.y.?e?nA5.n8.3?x?K(8.5)?4?:,I(x)=i|gi(x)=0,i=1,2,m.b?f(x)gi(x)(i I(x)3x?,gi(x)(i II(x)3x?Y,KK(8.5)?18Fe8S?88,=F S=,F=d Rn|gi(x)Td 0,i I(x),(8.10)S=d Rn|f(x)Td 0.17/37JJIIJIBackClosey y.?F S 6=,K3d F S.w,d 6=0.dF,S?9?Y5,3?,?0?,kf(x+d)0,i=1,2,m.b?g.y.?e?K(8.5)?7,=?KKT.n8.3(KKT)?x?K(8.5)?4?:,k?8I(x)=i|gi(x)=0,i=1,2,m.?f(x)gi(x)(i=1,2,m)3x?.e|gi(x)(i I(x)18/37JJIIJIBackClose5,K3=(1,2,m)T?f(x)mXi=1igi(x)=0,gi(x)0,i 0,igi(x)=0,i=1,2,m.y xK(8.5)?4?:,?dn8.3,3d Rn?f(x)Td 0,i I(x),=5?|f(x)Td 0,gi(x)Td 0919/37JJIIJIBackClosei 0(i I(x),?0f(x)XiI(x)igi(x)=0.Jy06=0.,e0=0,KkPiI(x)igi(x)=0,ddgi(x)(i I(x)5,b?g.d7k0 0.u-i=i0,i I(x);i=0,i II(x),K?f(x)mXi=1igi(x)=0,9gi(x)0,i 0,igi(x)=0,i=1,2,m.y.?20/37JJIIJIBackClose8.3?K?5y3e?zK?5:min f(x),x Rn,s.t.hi(x)=0,i=1,2,l,gi(x)0,i=1,2,m.(8.11)P1D=x Rn|hi(x)=0,i E,gi(x)0,i I,I8E=1,2,l,I=1,2,m.rn8.1n8.3(5=?K(8.11)?KKT?7.n8.4(KKT?7)?x?K(8.11)?4?:,3x?k?8S(x)=E I(x)=E i|gi(x)=0,i I.(8.12)21/37JJIIJIBackClose?f(x),hi(x)(i E)gi(x)(i I)3x?.e|hi(x)(i E),gi(x)(i I(x)5,K3(,)Rl Rm,=(1,2,l)T,=(1,2,m)T,?f(x)lXi=1ihi(x)mXi=1igi(x)=0,hi(x)=0,i E,gi(x)0,i 0,igi(x)=0,i I.(8.13)5(1)(8.13)KKT,v?:xKKT:.(x,(,)KKT,(,)K?.KFf.KKT:!KKTKKTO?.(2)igi(x)=0(i I(x)p5t.Xigi(x)?k70.e?0,?,u0,Kvp5t.22/37JJIIJIBackClose?K,K(8.11)?.KFL(x,)=f(x)lXi=1ihi(x)mXi=1igi(x).(8.14)JuCx?FHesse?OxL(x,)=f(x)lXi=1ihi(x)mXi=1igi(x),2xxL(x,)=2f(x)lXi=1i2hi(x)mXi=1i2gi(x).n8.2?yaq,yK(8.13)?Xe.n8.5u?zK(8.11),b?f(x),hi(x)(i E)gi(x)(i I)?Y?,k?8S(x)d(8.12)23/37JJIIJIBackClose.(x,(,)K(8.11)?KKT:.e?0 6=d Rn,hi(x)Td=0(i E),gi(x)Td=0(i I(x),kdT2xxL(x,)d 0,KxK(8.11)?4?:.8.1zKmin f(x)=2x21 x22,s.t.x21+x22 2=0,x1+x2 0,x1,x2 0.?yx=(1,1)TKKT:,K?KKT.24/37JJIIJIBackClose)Of(x)=4x12x2!?x=x=42!,h(x)=22!,g1(x)=11!.-f(x)h(x)1g1(x)=0,)?=1.5,1=1.2-2=3=0,?f(x)h(x)3Pi=1igi(x)=0,igi(x)=0,i 0,i=1,2,3.LxKKT:,(x,(,)KKT,=1.5,=(1,0,0)T.?,K(8.11)?KKT:4?:.?XJKe?zK,KKKT:!4?:!?4?:n?d?.25/37JJIIJIBackCloseek?zK?.8.2u?zKmin f(x),x Rn,s.t.hi(x)=0,i=1,2,l,gi(x)0,i=1,2,m.(8.15)ef(x),hi(x)(i=1,2,l)5,gi(x)(i=1,2,m)(=gi(x),o?zKzK.n8.6?(x,)zK(8.15)?KKT:,Kx7TK?4?:.26/37JJIIJIBackClosey uzK,.KFL(x,)=f(x)lXi=1ihi(x)mXi=1igi(x)ux,?uz1:x,kf(x)f(x)lXi=1ihi(x)mXi=1igi(x)=L(x,)L(x,)+xL(x,)T(x x)=L(x,)=f(x).?xK?4?:.y.?8.4Q:K?!0?zK?Q:?kVg.kQ:27/37JJIIJIBackClose?.8.3?zK(8.11),e3x(,),0,vL(x,)6L(x,)6L(x,),(x,)Rn Rl Rm+,(8.16)K(x,)?zK(8.11)?.KF?Q:,xK(8.11)?Q:.e?nL,Q:x=KKT:,?4?:.n8.7?(x,)?zK(8.11)?Q:.K(x,)=K(8.11)KKT:,?4?:.y dQ:?8.3xminxRnL(x,)28/37JJIIJIBackClose?4?:.d?zK?5?xL(x,)=0,y?zK(8.11)KKT?1f.,2dQ:?(,)maxi0(iI),RlL(x,)?4:,?d/,(,)mini0(iI),RlL(x,)?4?:.odn8.4,3f=(1,2,m)T(i 0,i=1,2,m),?hi(x)=0,i Egi(x)=i 0,i 0,ii=0,i I.29/37JJIIJIBackClosel?xK(8.11)?1:,igi(x)=0,i I,?(x,)vK(8.11)?KKT,=KKT:.?,dQ:?,uK(8.11)?1:x,kL(x,)6 L(x,),=f(x)6 f(x)lXi=1ihi(x)mXi=1igi(x)6 f(x),l?xK(8.11)?4?:.?n8.7,Q:KKT:,?.,?,uzK,KKT:!Q:?4?:n?d?.ukXen.n8.8?(x,)zK?KKT:,K(x,)A?.KF?Q:,xTzK?430/37JJIIJIBackClose?:.y 5?uzK,.KFL(x,)=f(x)lXi=1ihi(x)mXi=1igi(x)ux,?d?5(n1.4),kL(x,)L(x,)+xL(x,)T(x x)=L(x,),=L(x,)6 L(x,).,u?(,)RlRm+,kL(x,)L(x,)=lXi=1(i i)hi(x)mXi=1(i i)gi(x)31/37JJIIJIBackClose=mXi=1igi(x)6 0,=L(x,)6 L(x,),?(x,)Q:,xzK?4?:.y.?e?zK?K.u?zK(8.11),XeP:H(x)=?h1(x),hl(x)?T,G(x)=?g1(x),gm(x)?T.-y Rl,z Rm,L(x,y,z)=f(x)H(x)Ty G(x)Tz9(y,z)=infxRnL(x,y,z).32/37JJIIJIBackClose(y,z)u(y,z).?K(8.11)?.KFmax(y,z),s.t.y Rl,z Rm+.(8.17)?K(8.11)?Wolfemax L(x,y,z),s.t.xL(x,y,z)=0,y Rl,z Rm+.(8.18)5?3,?.,u.KF,du8I(y,z)?.KFux?4?,w,kxL(x,y,z)=0.?.KF?,?Wolfe.33/37JJIIJIBackCloseu55yK?g5yK,.KF(8.17)k?/.ef.8.2?k55yKmin cTx,s.t.Ax=b,x 0.(8.19)?.KF.).KFL(x,y,z)=cTx yT(Ax b)zTx.ux4?.-xL(x,y,z)=c ATy z=0.34/37JJIIJIBackClose“.KF,?(y,z)=infxRnL(x,y,z)=infxRn(c ATy z)Tx+yTb=yTb=bTy.5?z=c ATy 0,ukmax bTy,s.t.ATy 6 c.(8.20)55yK(8.19)?5y.?8.3?g5yKmin12xTBx+cTx,s.t.Ax 6 b,(8.21)35/37JJIIJIBackClose:B Rnn?;A Rmn.?g5yK(8.21)?5y.)k?TK?.KFL(x,z)=12xTBx+cTx zT(b Ax).ux4?.duB?,?L(x,z)ux.-xL(x,z)=Bx+c+ATz=0,)?x=B1(c+ATz).“.KF,?(z)=infxRnL(x,z)=infxRn?(Bx+c+ATz)Tx zTb 12xTBx?=bTz 12B1(c+ATz)TBB1(c+ATz)36/37JJIIJIBackClose=bTz 12(cT+zTA)B1(c+ATz)=(b AB1c)Tz 12zT(AB1AT)z 12cTB1c.-d=b AB1c,D=AB1AT,Kk(z)=12zTDz+dTz 12cTB1c.5?fz 0,d?g5yK(8.21)?.KFmax12zTDz+dTz 12cTB1c,s.t.z 0.?e?KK?8Im?X.37/37JJIIJIBackClosen8.9(fn)?x(y,z)O?K(8.11)K(8.17)?1),Kk(y,z)6 f(x).y x(y,z)O?K(8.11)K(8.17)?1),?(y,z)=infxRn?f(x)yTH(x)zTG(x)?6 f(x)yTH(x)zTG(x)=f(x).y.?
