《最優(yōu)化方法》課程復(fù)習(xí)考試

1、 /44最優(yōu)化方法復(fù)習(xí)提要第一章最優(yōu)化問(wèn)題與數(shù)學(xué)預(yù)備知識(shí)1.1模型無(wú)約束最優(yōu)化問(wèn)題minf(x),x=(x,x,x)tgRn.12n約束最優(yōu)化問(wèn)題S=xIxgRn,g(x)0,i=1,2,m;h(x)=0,j=1,2,1ijminf(x);s.t.xGS.minf(x);即0,z=1,2,m,ih(x)=0,j=1,2,1.其中f(x)稱為目標(biāo)函數(shù)，x,x,.,x稱為決策變量，S稱為可行域,12ng(x)0(/=1,2,m),h(x)=0(j=1,2,1)稱為約束條件.Zj1.2多元函數(shù)的梯度、Hesse矩陣與Taylor公式定義設(shè)f:RnTR,xGRn如果3n維向量p,VAxeRn，有f(x

2、+Ax)一f(x)=pTAx+o(|)那么稱f(x)在點(diǎn)x處可微，并稱df(x)=PTAx為f(x)在點(diǎn)x處的微分.如果f(x)在點(diǎn)x處對(duì)于x=(x,x,x)t的各分量的偏導(dǎo)數(shù)12nQf(x).2Z=1,2,，nQxi都存在，那么稱f(x)在點(diǎn)x處一階可導(dǎo)，并稱向量Vf(x)=(fl,輕，,fl)TQxQxQx12n為f(x)在點(diǎn)x處一階導(dǎo)數(shù)或梯度.定理1設(shè)f:RnTR,xgRn.如果f(x)在點(diǎn)x處可微，那么f(x)在點(diǎn)x處梯度Vf(x)存在，并且有df(x)=(x)tAx定義設(shè)f:RntR,xeRnd是給定的n維非零向量，e=上如果dlimf(X+牛)-/(X)R)Xt0九存在，那么稱此極

3、限為f(x)在點(diǎn)x沿方向d的方向?qū)?shù)，記作5f(x)dd定理2設(shè)f:RntR,xeRn如果f(x)在點(diǎn)x處可微，那么f(x)在點(diǎn)x處沿任何非零方向d的方向?qū)?shù)存在，且5f(x)=W(QTe，其中e=上5d|d|定義設(shè)f(x)是Rn上的連續(xù)函數(shù)，xeRnd是n維非零向量如果350，使得V九e(0,5)，有f(x+九d)f(x)那么稱d為f(x)在點(diǎn)x處的下降上升方向定理3設(shè)f:RntR,xeRn，且f(x)在點(diǎn)x處可微，如果3非零向量deRn，使得Vf(x)Td0，那么d是f(x)在點(diǎn)x處的下降上升方向.定義設(shè)f:RntR,xeRn如果f(x)在點(diǎn)x處對(duì)于自變量x=(x,x,x)t的12n各分量

4、的二階偏導(dǎo)數(shù)(i,j=12,n)都存在，那么稱函數(shù)f(x)在點(diǎn)x處二5x5xij階可導(dǎo)，并稱矩陣52x5x5x11252f(x)52f(x)5x5x52x21252f(x)、5x5x1n52f(x)5x5x2n52f(x)52x丿n為f(x)在點(diǎn)x處的二階導(dǎo)數(shù)矩陣或Hesse矩陣.定義設(shè)h:RntRm,xeRn，記h(x)=(h(x),h(x),h(x)t，如果12mh(x)(i=1,2,m)在點(diǎn)x處對(duì)于自變量x=(x,x,x)T的各分量的偏導(dǎo)數(shù)i12ndh(x)(i=1,2,m;j=1,2,n)dxj都存在，那么稱向量函數(shù)h(x)在點(diǎn)x處是一階可導(dǎo)的，并且稱矩陣1Qx1Qh(x)/*1Qx2

5、Qh(x)/*Qx1Qx2Qh(x)Qh(x)Qx1Qx2dh(x)dh(x)Vh(x)=mxnQh(x)、1QxnQh(x)Q2xn為h(x)在點(diǎn)X處的一階導(dǎo)數(shù)矩陣或Jacobi矩陣,Qh(x)mQx丿n簡(jiǎn)記為Vh(x).例2設(shè)aeRn,xeRn,beR,求f(x)=aTx+b在任意點(diǎn)x處的梯度和Hesse矩陣ax+b,kkk=1解設(shè)a=(a,a，a)t,x=(x,x，x)t，那么f(x)=12n12n因。f=a(k=1,2,.,n)，故得Vf(x)=a.dxkk又因2f(x)=0(i,j=1,2,n)，那么V2f(x)=Odxdxij例3設(shè)QeRnxn是對(duì)稱矩陣，beRn,ceR，稱f(x

6、)=xtQx+bTx+c為二2次函數(shù)，求f(x)在任意點(diǎn)x處的梯度和Hesse矩陣.解設(shè)Q=(q),x=(x,x,x)T,b=(b,b，,b)T，那么jnxn12n121yyf(x,x，x)=qxx+12n2jiji=1j=1rqf(x)(IQ珂從而Vf(x)=I工bx+c,kkk=1qx+b1jj1j=1I|qx+b(Qx丿njjnn丿Ij=1丿厶qx1jjj=1藝qxnjjj=1rb)1:=Qx+bn=2qx+b(i=1,2,n)求偏導(dǎo)得到ijjij=1弓x)=q(i,j=1,2,，n)，于0 xdxijijV2f(x)二q11q21q12q22q)1nq2nqn1qn2q丿nn例4設(shè)Q(

7、t)=f(x+td)，其中f:RnTR二階可導(dǎo)，xGRn,dGRn,tGR,試求0(t),0(t).解由多元復(fù)合函數(shù)微分法知0(t)=Vf(x+td)Td,Q(t)=dTV2f(x+td)d定理4設(shè)f:RnTR,xGRn，且f(x)在點(diǎn)x的某鄰域具有二階連續(xù)偏導(dǎo)數(shù)，那么f(x)在點(diǎn)x處有Taylor展式f(x+Ax)=f(x)+Vf(x)t山+23V2f(x+臉心,(001)-證明設(shè)q(t)=f(x+tAx),tG0,1,那么Q(0)=f(x),Q(1)=f(x+Ax)按一元函數(shù)Taylor公式q(t)在t=0處展開(kāi)，有Q(t)=Q(0)+Q(0)t+-Q(0)t2,(00t)2從例4得知Q(

8、0)=Vf(x)tAx,Q(0)=(Ax)tV2f(x+0Ax)Ax令t=i，有f(工+Ax)=心+Vf(x)T叢+2如呵任+0Ax)Ax,(o0f(x)，那么稱x為f(x)在S上的全局或整體極小點(diǎn)，或者說(shuō)，x是約束最優(yōu)化問(wèn)題minf(x)的全局或整體最優(yōu)解，并稱xGSf(x)為其最優(yōu)值.2假設(shè)VxgS,x豐x，都有f(x)f(x)，那么稱x為f(x)在S上的嚴(yán)格全局或整體極小點(diǎn)3假設(shè)Bx的5鄰域Njx)=xgR|x-x|0)使得VxgNJx)dS，都有f(x)f(x)，那么稱x為f(x)在S上的局部極小點(diǎn)，或者說(shuō)，x是約束最優(yōu)化問(wèn)題minf(x)的局部最優(yōu)解xgS4假設(shè)Bx的8鄰域N(x)(

9、80)使得VxgN(x)p|S,x豐x，都有88f(x)f(x)，那么稱x為f(x)在S上的嚴(yán)格局部極小點(diǎn).第二章最優(yōu)性條件2.1無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件定理1設(shè)f:RnTR在點(diǎn)x處可微，假設(shè)x是問(wèn)題minf(x)的局部極小點(diǎn)，那么Vf(x)=0定義設(shè)f:S(匸Rn)tR在xgintS處可微，假設(shè)V(x)=0，那么稱x為f(x)的平穩(wěn)點(diǎn)定理2設(shè)f:RntR在點(diǎn)x處具有二階連續(xù)偏導(dǎo)數(shù)，假設(shè)x是問(wèn)題minf(x)的局部極小點(diǎn)，那么V(x)=0，且V2f(x)半正定.定理3設(shè)f:RntR在點(diǎn)x處具有二階連續(xù)偏導(dǎo)數(shù)，假設(shè)Vf(x)=0，且V2f(x)正定，那么x是問(wèn)題minf(x)的嚴(yán)格局部極小點(diǎn)

10、.注：定理2不是充分條件，定理3不是必要條件例1對(duì)于無(wú)約束最優(yōu)化問(wèn)題minf(x)=x2-x3，其中x=(x,x)TgR2，顯然1212Vf(x)=(2x,-3x2)t,VxgR2，令Vf(x)=0，得f(x)的平穩(wěn)點(diǎn)x=(0,0)t，而且12V2f(x)易見(jiàn)V2f(x)為半正定矩陣.但是，在X的任意8鄰域卜-XIS,總可以取到X二(0,)T,使f(x)f(x),即X不是局部極小點(diǎn).例2對(duì)于無(wú)約束最優(yōu)化問(wèn)題minf(x)=x4+2x2x2+x4，其中x=(x,x)tgR2,112212易知Vf(x)=(4x3+4xx2,4x2x+4x3)t，從而得平穩(wěn)點(diǎn)x=(0,0)t，并且112122(12

11、x2+4x2V2f(x)=12(8xx128xx)_12,V2f(x)4x2+12x2丿12(0顯然V2f(x)不是正定矩陣但是,f(x)=(x2+x2)2在x處取最小值，即x為嚴(yán)12格局部極小點(diǎn)例3求解下面無(wú)約束最優(yōu)化問(wèn)題minf(x)=1x3+1x3-x2-x,313221其中x=(x,x)TgR2，12解因?yàn)?x2-1)Vf(x)=1,V2f(x)=Ix2-2x丿22(2x102x-2丿2x210所以令Vf(x)=0，有J1一x2-2x=0.22解此方程組得到f(x)的平穩(wěn)點(diǎn)x(1)0丿,x(2)(-1)x=,x10丿(-1)從而V2f(x(3)(200)-2丿丿,V2f(x(2)=(2

12、0)(-2.00)-2丿丿,V2f(x(4)(-20)由于V2f(x(1)和V2f(x(4)是不定的，因此x(1)和x不是極值點(diǎn).V2f(x)是負(fù)定的，故x(3)不是極值點(diǎn)，實(shí)際上它是極大點(diǎn)V2f(x(2)是正定的，從而x(2)是嚴(yán)格局部極小點(diǎn)定理4設(shè)f:RnTR是凸函數(shù)，且f(x)在點(diǎn)xeRn處可微，假設(shè)Vf(x)二0，那么X為minf(x)的全局極小點(diǎn).推論5設(shè)f:RntR是凸函數(shù)，且f(x)在點(diǎn)xeRn處可微那么x為minf(x)的全局極小點(diǎn)的充分必要條件是Vf(x)二0例4試證正定二次函數(shù)f(x)=xtQx+bTx+c有唯一的嚴(yán)格全局極小點(diǎn)2x=Q-ib，其中Q為n階正定矩陣.證明因?yàn)?/p>

13、Q為正定矩陣，且Vf(x)=Qx+b,VxeRn，所以得f(x)的唯一平穩(wěn)點(diǎn)x=Q-ib又由于f(x)是嚴(yán)格凸函數(shù)，因此由定理4知，x是f(x)的嚴(yán)格全局極小點(diǎn)2.2等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件定理1設(shè)f:RnTR在點(diǎn)x處可微，h:RntR(j=1,2，,l)在點(diǎn)x處具有一階j連續(xù)偏導(dǎo)數(shù)，向量組Vh(x),Vh(元)，,Vh(x)線性無(wú)關(guān)假設(shè)x是問(wèn)題12lminf(x);的局部極小點(diǎn)，s.t.h.(x)=0,j=1,2,，l那么3V.eR,j=1,2,l，使得jVf(x)-丈VVh(x)=0jjj=1稱L(x,v)=f(x)vTh(x)為L(zhǎng)agrange函數(shù)，其中h(x)=(h(x),h(x

14、),h(x)t.TOC o 1-5 h z12l稱v=(v,v，,v)T為L(zhǎng)agrange乘子向量.12l易見(jiàn)VL(x,v)這里VL(x,v)=Vf(x)vVh(x),VL(x,v)=h(x)xjjvj=1定理2設(shè)f:RnTR和h:RntR(j=1,2,l)在點(diǎn)xeRn處具有二階連續(xù)偏j導(dǎo)數(shù)，假設(shè)3veRl，使得VL(x,v)=0，并且，VzeRn,z主0，只要xztVh(x)=0,j=1,2,l，便有ztV2L(x,v)z0，那么x是問(wèn)題jxxminf(x);sth.(x)=0,j=1,2,lij的嚴(yán)格局部極小點(diǎn)例i試用最優(yōu)性條件求解rinf(x)=x2+號(hào)那么VL(x,v)=廠2x-vx1

15、22x-vx21.-(xx812s.th(x)=xx-8=0.12Lagrange函數(shù)為L(zhǎng)(x,v)=x2+x2-v(xx-8),1212從而得L(x,v)的平穩(wěn)點(diǎn)(p8,*8,2)t和(-x/8,-丫8,2)t，對(duì)應(yīng)有x=G/8/8)t,v=2和x=(-罷，-畐t,v=2.由于V2L(x,v)xx20 xx11221利用定理2,所得的兩個(gè)可行點(diǎn)元=(耳島t和x=(8,78)T都是問(wèn)題的嚴(yán)格局部極小點(diǎn).2.3不等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件定義設(shè)S匸Rn,xeclS,deRn,d豐0，假設(shè)350，使得，x+九deS,VXe(0,8),那么稱d為集合S在點(diǎn)x處的可行方向.這里clS=xIxeRn

16、,SN(x)H0,V50.5令D=dId豐0,380,使x+XdeS,VXe(0,8),F=dIVf(x)Td0,i=1,2,m,i其中f:RntR,g:RnTR(i=1,2,，m)i令I(lǐng)(x)=iIg(x)=0,i=1,2,m，其中x是上述問(wèn)題1的可行點(diǎn).i定理2設(shè)x是問(wèn)題1的可行點(diǎn)，f(x)和g(x)(ieI(x)在點(diǎn)x處可微，ig(x)(i電I(x)在點(diǎn)x處連續(xù)，如果x是問(wèn)題1的局部極小點(diǎn)，那么iFG=0，00其中G=dIVg(x)Td0,ieI(x)0i定理3設(shè)x是問(wèn)題1的可行點(diǎn)，f(x)和g(x)(ieI(x)在點(diǎn)x處可微，ig(x)(i電I(x)在點(diǎn)x處連續(xù)，假設(shè)x是問(wèn)題1的局部極

17、小點(diǎn)，那么存在不全i為0的非負(fù)數(shù)u,u(ieI(x)，使0iuVf(x)一工uVg(x)=0 x稱為FritzJohn點(diǎn)0_iiieI(x)如果g(x)(i電I(x)在點(diǎn)x處也可微，那么存在不全為0的非負(fù)數(shù)u,u,u,i01m使uVf(x)-uVg(x)=0,i占0iix稱為FritzJohn點(diǎn)i=1ug(x)=0,i=1,2,，m.iiminf(x)=一x;1例1試判斷x=(1,0)T是否為FritzJohn點(diǎn).,Vg(x)=廠0、,Vg(x)=卩1I0J1J1丿2J1丿設(shè)0.22因?yàn)閂f(x)=且I(x)=1,2，所以為使FritzJohn條件u0(-1u廠0、ur0=r00丿1J1丿21

18、丿0即可，因此x是FritzJohn點(diǎn).012定理4設(shè)X是問(wèn)題1的可行點(diǎn)，f(x)和g(x)(igI(x)在點(diǎn)x處可微,ig(x)(i電I(x)在點(diǎn)x處連續(xù)，并且Vg(x)(igI(x)線性無(wú)關(guān)假設(shè)x是問(wèn)題1ii的局部極小點(diǎn)，那么存在u0(igI(x)，使得iVf(x)工uVg(x)=0 x稱為K-T點(diǎn)iiiGI(x)如果g(x)(i電I(x)在點(diǎn)x處也可微，那么存在u0(i=1,2,m)，使得iiVf(x)-u.Vg.(x)=0,，稱為KT點(diǎn)iix稱為K-T點(diǎn)i=1ug(x)=0,i=1,2,m.ii例2求最優(yōu)化問(wèn)題qminf(x)=(x一1)2+x;12s.fg(x)=x一x+20,112

19、的K-T點(diǎn).r2(x1)1,Vg(x)=r1,Vg(x)=r011丿1(-1丿2L1丿g2(x)=x20解因?yàn)閂f(x)=所以K-T條件為2(x1)+u=0,111+uu=0,12vu(xx+2)=0,112ux=0,22u0,u0.12假設(shè)u=0，2那么u=1，1這與u0矛盾故u0，從而x=0；122假設(shè)一x+2=0，那么u=2，這與u0矛盾故u=0，從而u=1,x=1；111121由于u0,u0，且x=(1,0)t為問(wèn)題的可行點(diǎn)，因此x是K-T點(diǎn).12定理5設(shè)在問(wèn)題1中，f(x)和-g(x)(i=1,2,m)是凸函數(shù)，x是可彳亍點(diǎn),i并且f(x)和g(x)(igI(x)在點(diǎn)x處可微假設(shè)x是

20、問(wèn)題1的K-T點(diǎn)，那么xi是問(wèn)題1的全局極小點(diǎn)2.4一般約束最優(yōu)化問(wèn)題的最優(yōu)性條件考慮等式和不等式約束最優(yōu)化問(wèn)題minf(x)；0,i=1,2,m,1ih(x)=0,j=1,2,，l,其中f:RntR,g:RnTR(i=1,2,m),h:RntR(j=1,2,l).ij并把問(wèn)題1的可行域記為SVxGS,I(x)=iIg(x)=0,i=1,2,m.i定理1設(shè)x為問(wèn)題1的可行點(diǎn)，f(x)和g(x)(iGI(x)在點(diǎn)x處可微，iTOC o 1-5 h zh(x)(j=1,2,l)在點(diǎn)x處具有一階連續(xù)偏導(dǎo)數(shù)，g(x)(i電I(x)在點(diǎn)x處連續(xù),ji并且向量組Vh(x),Vh(x),Vh(x)線性無(wú)關(guān)假

21、設(shè)x是問(wèn)題1的局部極小12l點(diǎn)，那么FH=0,000這里F=dIVf(x)Td0,igI(x),00iH=dIVh(x)Td=0,j=1,2,l0j定理2設(shè)x為問(wèn)題1的可行點(diǎn)，f(x)和g(x)(igI(x)在點(diǎn)x處可微，ih(x)(j=1,2,l)在點(diǎn)x處具有一階連續(xù)偏導(dǎo)數(shù)，g(x)(i電I(x)在點(diǎn)x處連ji續(xù)假設(shè)x為問(wèn)題1的局部極小點(diǎn)，那么存在不全為0的數(shù)u,u(iGI(x)和0iv(j=1,2,l)，且u,u0(igI(x)，使TOC o 1-5 h zj0iuVf(x)一工uVg(x)一工vVh(x)=0 x稱為FritzJohn點(diǎn)0iijjiGI(x)j=1假設(shè)g(x)(i電I(x

22、)在點(diǎn)x處也可微，那么存在不全為0的數(shù)u,u(i=1,2,m)和i0iv(j=1,2,l)，且u,u0(i=1,2,m)，使j0iuVf(x)一區(qū)uVg(x)一工vVh(x)=0,tv0iijjx稱為FritzJohn點(diǎn)i=1j=1ug(x)=0,i=1,2,，m.Jiiminf(x)=x2+x2;12例1試判斷x=(1,0)t是否為FritzJohn點(diǎn).s.tg(x)=x3-x0,112g(x)=x0,22h(x)=(x1)2+x=0.12r2,Vg(x)=廠0、,Vh(x)=廠0、0丿21丿1丿I(x)=2，且Vf(x)=，且I(x)=1,2,0r2ur0vr0、=r0、0丿21丿1丿0(

23、igI(x)和v(j=1,2,l)，使1jVf(x)工uVg(x)XvVh(x)=0 x稱為K-T點(diǎn)iijjIgI(x)j=1如果g(x)(i電I(x)在點(diǎn)x處也可微，那么存在數(shù)u0(i=1,2,m)和iiv(j=1,2,l)，使jx稱為K-T點(diǎn)Vf(x)瓦uVg(x)工vVh(x)=0,iijji=ij=1ug(x)=0,i=1,2,，m.ii令g=(冒),，,gm(x)T,g)=W,h2，,hlu=(u,u，u)t,v=(v,v，v)t，12m12l稱u與v為廣義Lagrange乘子向量或K-T乘子向量.Vf(x)Vg(x)tuVh(x)tv=0,0.令L(x,u,v)=f(x)uTg(x

24、)vTh(x)為廣義Lagrange函數(shù)稱L(x,u,v)為廣義Lagrange函數(shù)那么K-T條件為VL(x,u,v)=0,xvUTg(x)=0,u0.定理4設(shè)在問(wèn)題1中，f(x)和-g.(x)(i=1,2,m)是凸函數(shù)，ihj(x)(j=z,1)是線性函數(shù)，x是可行點(diǎn)并且f(x)和g(x)(ie1(x)在點(diǎn)x處可微假設(shè)x是問(wèn)題1的K-T點(diǎn)，那么x是問(wèn)題1的全局極小點(diǎn).例2求解最優(yōu)化問(wèn)題vminf(x)-(x3)2+(x1)2；12s.tg(x)-x2+x0,12h(x)-2x+x30.12解廣義Lagrange函數(shù)為L(zhǎng)(x,u,v)-f(x)ug(x)vh(x)-(x3)2+(x1)2u(x

25、2+x)v(2x+x3).121212因?yàn)長(zhǎng)(x,u,v)-2(x3)+2ux2v,dx111dL(x,u,v)dx2-2(x1)uv2所以K-T條件與約束條件為下面分兩種情況討論(1)設(shè)u-0，那么有2(x3)+2ux2v0,112(x1)uv-0,2u(x2+x)-0,12x2+x0,122x+x30,12u0.2(x3)2v-0,1v2(x1)v-0,22x+x30.12由此可解得x-7,x-丄,v-8，但x-(?,)T不是可行點(diǎn)，因而不是K-T點(diǎn).1525555(2)設(shè)u0，那么有2(x-3)+2ux-2v=0,ii2(x1)uv0,V2x2+x0,122x+x30.12由此可得一x2

26、一2x+30，解得x1或x3。從而x1或x9于是u1111122或u11這與u0矛盾v1或v27由此可知x(1,1J是問(wèn)題的K-T點(diǎn)，但x(3,9)t不是問(wèn)題的K-T點(diǎn).易見(jiàn)，f(x)是R2上的凸函數(shù)，g(x)是R2上的凹函數(shù)，h(x)是線性函數(shù)，因此由定理4知，x(1,1是問(wèn)題的全局最優(yōu)解.定理5設(shè)x為問(wèn)題的可行點(diǎn)，f(x),gWCeI(x)和忖)()-1,1)在點(diǎn)x處具有二階連續(xù)偏導(dǎo)數(shù)，并且存在乘子向量u(u,u，,u)T0和12mv(v,v,v)t0使K-T條件成立，即12mVL(x,u,v)0,xuTg(x)0.假設(shè)對(duì)于任何滿足ztVg(x)0,ieI(x)且u0,iivztVg(x)

27、0,ieI(x)且歷0,iiZTVh(x)0,j1,2,1ij的向量z豐0,都有ZTV2L(x,u,v)z0，那么x是問(wèn)題1的嚴(yán)格局部極小點(diǎn).xxminf(x)-工C;x例3求解最優(yōu)化問(wèn)題Vi1is.t.g(x)x0,i1,2,，n,iih(x)-工axb0,iii1其中常數(shù)a0,c0,i1,2,n;b0.TOC o 1-5 h zii解該問(wèn)題的廣義Lagrange函數(shù)為L(zhǎng)(x,u,v)ux一v(工axb)xiiiii1ii1i1因?yàn)閐L（x,u,v）c=fu一av,i=1,2,，ndXX2iiii所以問(wèn)題的K-T條件與約束條件為一一f-u-av=0,i=1,2,，n,x2iiiux=0,i=

28、1,2,n,ii0,i=1,2,n,iax-b=0,iii=1u0,i=1,2,，n.Ii由第1式、第3式知x0（i=1,2,n），從而由第二式解得u=0,i=1,2,n于ii是再由第1式知v0,i=1,2，n，x3i因此V2L(x,U,v)是正定矩陣根據(jù)定理5,x為問(wèn)題的嚴(yán)格局部極小點(diǎn).xx第三章常用優(yōu)化算法介紹3.1一維搜索給定x,deRn，令申（九）=f（x+九d）,X0.kkkkminp（九）X0定義如果求得步長(zhǎng)九k，使得f（x+九d）=minf（x+九d）或申（九）=TOC o 1-5 h zkkk九0kkk那么稱這樣的一維搜索為最優(yōu)一維搜索或準(zhǔn)確一維搜索.*叫做最優(yōu)步長(zhǎng)Iminf(

29、x);定理1對(duì)于問(wèn)題L%eS設(shè)f：STR是可微函數(shù)是從xk出發(fā)沿方向dk作最優(yōu)一維搜索得到的，那么有Vf(x)Td=0.k+1k定義如果選取九,使目標(biāo)函數(shù)f沿方向d取得適當(dāng)?shù)目沙惺艿南陆盗?，即使得下降kk量f(x)-f(x)0是我們可承受的，那么稱這樣的一維搜索為可承受一維搜索或非準(zhǔn)確kk+1一維搜索.定義設(shè)p:RTR,*G0,刈，并且p(兀)=minp(九).如果對(duì)于a,bu0,刈有*0*ea,b，那么稱a,b是問(wèn)題minp(*)的搜索區(qū)間.*0定義設(shè)p:RTR,a,buR,假設(shè)存在*ea,b，使得p(*)在a,*上嚴(yán)格單調(diào)減少，在*,b上嚴(yán)格單調(diào)增加，那么稱a,b是p(九)的單谷區(qū)間，p(

30、九)是a,b上的單谷函數(shù)或單峰函數(shù).定理2設(shè)p:RTR,a,b為p(*)的單谷區(qū)間，九,九ea,b，且九*，那么1212假設(shè)p(*)p(*)，那么*,b是p(*)的單谷區(qū)間.121算法3-1進(jìn)退法Stepl選取初始數(shù)據(jù)。給定初始點(diǎn)*，初始步長(zhǎng)h0，加倍系數(shù)a1一般取=2，00計(jì)算p=p(九)，置k=0.00TOC o 1-5 h zStep2試探令*=*+h，計(jì)算p=p(*)k+1kkk+1k+1Step3比擬目標(biāo)函數(shù)值.假設(shè)p0,t=0.618.11Step2計(jì)算最初兩個(gè)試探點(diǎn)：九=a+（1P）（b-a），卩=a+（b-a），求岀11111111申（九）,P（卩），并置k=1.11Step3

31、檢查九一卩P（卩），轉(zhuǎn)Step6kkkkStep5向左搜索.令a：=a,b=卩，卩=九,p（卩）=p（九）k+1kk+1kk+1kk+1k并計(jì)算九=a+（1-P）（b一a）,p（九），轉(zhuǎn)Step7.k+1k+1k+1k+1k+1Step6向右搜索.令a=X,b:=b,九=卩,p（九）=p（卩）.k+1kk+1kk+1kk+1k并計(jì)算卩k+1=a+T（ba）,p（卩），轉(zhuǎn)Step7.k+1k+1k+1k+1Step7置k:=k+1，轉(zhuǎn)Step3.定義Fibonacci數(shù)是指滿足下述條件的數(shù)列f：kF=F=1,V01F=F+F,k=1,2，.Jk+1kk-1用數(shù)學(xué)歸納法可以證明，F(xiàn)ibonacci

32、數(shù)可由下式表示:n+1I2丿,n=0,1,2,.3.2.2算法3-3Fibonacci法ST選取初始數(shù)據(jù).給定初始搜索區(qū)間叫引和允許誤差*0，區(qū)分系數(shù)，求搜索次數(shù)n，使b-a11Step2計(jì)算最初兩個(gè)試探點(diǎn)：九=a+尋2（ba）,卩=a+（ba）,求函數(shù)11F1111F11nn值申（九）和9（卩），并置k=1.11Step3檢查9（九）9（卩）?是，轉(zhuǎn)Step4；否，轉(zhuǎn)Step5.kkStep4向左搜索令a：=a?b=卩=九,9（卩）9（九）TOC o 1-5 h zk+1kk+1kk+1kk+1k并計(jì)算九k+1二a+1+節(jié)_（bk+i-a+1）和94+1），轉(zhuǎn)Step6-n-kStep5向右

33、搜索.令a二九,b:二b,九二卩,9（九）=9（卩）.k+1kk+1kk+1kk+1k并計(jì)算卩=a+nk1（ba）和9（卩），轉(zhuǎn)Step6.k+1k+1Fk+1k+1k+1nkStep6置k：=k+1，假設(shè)kn1，轉(zhuǎn)Step3；假設(shè)k=n1，轉(zhuǎn)Step7.Step7令九二九,卩二九+S，計(jì)算9（九）和9（卩）。假設(shè)9（九）0，置k=0.0Step2檢查9，()|0，令k=0.0Step2檢查是否滿足終止準(zhǔn)那么計(jì)算W(x)，假設(shè)|Vf(xk)|0，故由上式解出Vf(x)TVf(x)kk-Vf(x)TQVf(x)kk于是x=xk+1kVf(xk)Vf(x)tVf(x)kkVf(x)TQVf(x)k

34、k例1用最速下降法求解問(wèn)題minf(x)=4x2+x212其中x二（x,X.取初始點(diǎn)x（o）二（1,1J，允許誤差=0.1.12f是正定二次函數(shù)，且(80)I。J=f在點(diǎn)X=(x,x)T處的梯度Vf(x)=(8x,2X)T.1212第一次迭代：令搜索方向d(o)=-Vf(x(o)=(-&2)t,|d(0)|=“4+4=2j!7,從點(diǎn)x(0)出發(fā)沿d(0)68九(0)=0.130769,520 x(1)=(1,1)T+0.130769(-8,-2)T=(-0.046152,0.738462)T第二次迭代：令d(i)=-Vf(x(i)=(0.369216,-1.476924)t,|dd)|=J2.

35、18305=1.522375,從點(diǎn)x(1)出發(fā)沿d(1)x(2)=(0.101537,0.147682)T.第三次迭代：令d(2)=-Vf(x(2)=(-0.812296,-0.295364)t,|d|=J0.747056=0.864329,x(3)=(-0.009747,0.107217)T.第四次迭代：令d(3)=-Vf(x)=(0.077976,-0.214434)t,|d|=(0.052062=0.228171,x(4)二(0.019126,0.027816)t.第五次迭代：令d(4)二-Vf(x(4)二(0.15300&0.055632)t,|d|=、.0.026506=0.1628

36、07e,x(5)二(0.001835,0.020195)t.此時(shí)，|Vf(x(5)1=20.0018470，令k=0.0Step2檢查是否滿足終止準(zhǔn)那么計(jì)算Vf(x)，假設(shè)|Vf(xj|8，迭代終止，xkkkStep3構(gòu)造Newton方向.計(jì)算V2/(x)-1，取d=V2/(x)-1Vf(x)kkkkStep4求下一個(gè)迭代點(diǎn).令x=x+d，k：=k+1，返回Step2.k+1kk例2x(0)=(1,1)T，允許誤差8=0.1.(80)解Vf(x(o)=(8,2)t，V2f(x(o)=02，故02V2f(x(0)-11/2丿d(0)=V2f(x(0)-1Vf(x(0)=x(1)=x(0)+d(0

37、)=(1,1)T(1,1)T=(0,0)T.由于|Vf(x(1)|=00，令k=0.0TOC o 1-5 h zStep2檢查是否滿足終止準(zhǔn)那么計(jì)算Vf(x)，假設(shè)|Vf(x|0kkxx+九d.k+1kkk令k:k+1，返回Step2例3用阻尼Newton法求解下面問(wèn)題：minf(x)(1-x)2+2(x-x2)2121其中x(x,x.取初始點(diǎn)x(0)(0,0)T，允許誤差80.112解第一次迭代：Vf(x)V2f(x)-2(1-x)-8(x-x2)x1211TOC o 1-5 h z4(x-x2)丿2116x2一8(x一x2)+2-8x1211-8x4丿1Vf(x(0)(-2,0)t,JVf

38、(x(0)|28,V2f(x(0)0、0即求minf(x(0)+九d(0)min(1九)2+2九4的最優(yōu)解，得到九(0)-.令九02xx(0)+九(0)d(0)(1/2,0)t.Vf(x(1)(0,-1)T,第二次迭代：8-4、111、,V2f(x(1)-1-0 x0128的最優(yōu)解，得到九二2令x=x(1)+九(1)d(1)=(i,iy.Vf(x(1)=(0,-1)T,|Vf(x(1)1=1此時(shí)，Vf(x(2)=(0,0)T,|Vf(x(2)|=000Step2選取初始搜索方向計(jì)算Vf(x)，求岀d，使Vf(x)Td0，令k=00000Step3檢查是否滿足終止準(zhǔn)那么假設(shè)|Vf(x)|0kkx

39、=x+九dk+1kkkTep5選取搜索方向求d使k+1dTQd=0,j=0,1,k，k+1j令k:=k+1，返回Step3.如果用共軛方向法求解正定二次函數(shù)的無(wú)約束最優(yōu)化問(wèn)題minf(x)=xtQx+bTx+c2其中QGRnxn為正定矩陣，bGRn,CGR此時(shí)算法中的正定矩陣應(yīng)與二次函數(shù)的正定矩陣一致，那么容易推出迭代公式為Fletcher-ReevesFR公式:x=xk+1kdTQdkk岡(x址岡(xk)|2Polak-Ribiere-PolyakPRP公式：akTep5Step6檢查迭代次數(shù).假設(shè)k+1=n，Step7構(gòu)造共軛方向.用FR公式取z“八亠=Vf(x)tvf(x)Dixon-M

40、yersDM公式：a=-k+k+-；kdTvf(x)kkVf(x)tVf(x)-Vf(x)k+k+kVf(x)tVf(x)kk算法3-9FR共軛梯度法Step1選取初始數(shù)據(jù).選取初始點(diǎn)x，給定允許誤差e0.0Step2檢查是否滿足終止準(zhǔn)那么計(jì)算Vf(x0)，假設(shè)|Vf(x0)|0kkd=-Vf(x)+ad，k+1k+1kkaVf(xk+1)卩k|Vf(x)|2令k:二k+1，返回Step4.注意，如果算法3-9的Step7中的形式改為DM公式或PRP公式，那么分別得到DMk共軛梯度法和PRP共軛梯度法.x(o)二(0,0)t，允許誤差二0.1.解因?yàn)榭?、(2(1-x)-8(x-x2)xI4(

41、x2-x12)丿所以Vf(x(o)=(-2,0)t,|Vf(x(o)|=2.令d(O)=-Vf(x(0)二(2,0)T，從x(0)出發(fā)，沿d(O)進(jìn)展一維搜索，得九(0)二1/4,x(1)=x(0)+九(0)d(0)=(1/2,0)t.從而Vf(x(1)=(0,-1)T,|Vf(x(1)1=1.由FR公式有|Vf(x(0)|214因此，新的搜索方向?yàn)閐(1)=-Vf(x(1)+ad(0)=(1/2,1)t.0從x(1)出發(fā)，沿d(1)進(jìn)展一維搜索，得九(1)=1,x=x+九(1)d=(1,1J.此時(shí)Vf(x(2)=(0,0)T,|Vf(x(2)|=00，令k=0.0Step2進(jìn)展一維搜索.從x

42、出發(fā)，沿坐標(biāo)軸方向e進(jìn)展一維搜索，求九和x，使k-1kk-1k得f(x+九e)=minf(x+九e)，k-ik-ik九k-ikx=x+九e.kk-1k-1kStep3檢查迭代次數(shù).假設(shè)k=n，轉(zhuǎn)Step4；否那么，令k：=k+1，返回Step2.Step4檢查是否滿足終止準(zhǔn)那么.假設(shè)卜一xj|.再?gòu)狞c(diǎn)x出發(fā)沿e進(jìn)展一維搜索，得14154九=一,x=x+九e=(,)t2821v84從點(diǎn)x(4)出發(fā)沿e2進(jìn)展一維搜索，得x=4,x(4)=x+入e=(1515)t3432、816再?gòu)狞c(diǎn)x(4)出發(fā)沿ei進(jìn)展一維搜索，得36315,x=x+人e=(,)t；324i3216從點(diǎn)x(5)出發(fā)沿e2進(jìn)展一維

43、搜索，得九=A,x=x5646363+X5e2=(莎習(xí)爪再?gòu)狞c(diǎn)x(6)出發(fā)沿ei進(jìn)展一維搜索，得325563TOC o 1-5 h z人=,x=x+人e=(,)t61286112864從點(diǎn)x(7)出發(fā)沿e2進(jìn)展一維搜索，得丄,x=x(7)+九e=(竺竺)T；25672128256255255x=(,)T128256(2,1)T3.8Powell法算法3-11Powell法TOC o 1-5 h zStepl選取初始數(shù)據(jù)選取初始點(diǎn)x，n個(gè)線性無(wú)關(guān)的初始搜索方向d,d，,d,001n-1給定允許誤差80，令k=0Step2進(jìn)展根本搜索令y=x，依次沿d,d，d進(jìn)展一維搜索對(duì)一切0k01n-1j=1

44、,2,n，記f(y+九d)=minf(y+九d),j-1j-1j-1九j-1j-1y=y+九djj一1j一1j一1Step3檢查是否滿足終止準(zhǔn)那么.取加速方向d=y-y，假設(shè)dII,迭代終止,nn0n得y為問(wèn)題的近似最優(yōu)解；否那么，轉(zhuǎn)Step4.nStep4確定搜索方向.按f(y)-f(y)=maxf(y)-f(y)m0jn-1j卄1確定m，假設(shè)f(y)-2f(y)+f(2y-y)8，所以要確定調(diào)整方向由于9f(y(0)=0，f(y)=0,f(y)=-4f(y(1)-f(y(2)=maxf(y(j)-f(y(j+1)|j=0,1因此m=1，并且9f(y(m)-f(y(m+1)=f(y(1)-f

45、(y)=43又因f（2yy（o）=0 x=y=（-,0）t.厶第二次迭代：3取y（0）=x（1）=（牙,0）T，從點(diǎn)y（0）出發(fā)沿d作一維搜索，得20TOC o 1-5 h z HYPERLINK l bookmark14 333九=,y（i）=y（o）+九d=（,）t.040024接著從點(diǎn)y（i）出發(fā)沿方向d作一維搜索，得1 HYPERLINK l bookmark18 3153九=-,y=y+九d=（丁汕181184由此有加速方向33d-=y一y（o）=（84）t因?yàn)閨dj|=3J5/88，所以要確定調(diào)整方向.45,f（y（2）=獸16649f（y（0）=一4f（y）=一m=0，并且9f（

46、y（m）f（y（m+1）=f（y（0）f（y）=-16由于45f（2yy（o）=16y出發(fā)沿d-作一維搜索，得九=,x（2）=y+九d=（2,1）t。2322同時(shí)，以d替換d0,即下一次迭代的搜索方向組取為第三次迭代：33do=（1，0）T，di=（8,4）T-取y（o）二x=（2,1）t，類似地可求得y（1）二（2,1）t,y二（2,1）t,d=y一y（o）=（0,0）t.2因?yàn)閨d|=0 x=y=（2，1）t.3.9罰函數(shù)法一、外法函數(shù)法考慮約束非線性最優(yōu)化問(wèn)題minf(x)；0,i=1,2,m,ih(x)=0,j=1,2,l,Jj其中f(x),g(x)(i=1,2,m)和h(x)(j=1

47、,2,l)都是定義在Rnsij對(duì)于等式約束問(wèn)題minf(x);Vs.th(x)=0,j=1,2,l,1j定義罰函數(shù)F(xQ)=f(x)+c工h2(x),1jj=1其中參數(shù)ominF(x,o)xeRn1對(duì)于不等式約束問(wèn)題Jminf(x);s.g(x)0,i=1,2,，m,i定義罰函數(shù)F(x,)=f(x)+max0,-g(x)2,2ii=1其中ominF(x,o)xeRn2F(x,o)=f(x)+oP(x)，其中o是很大的正數(shù)，P(x)具有以下形式P(x)=遲嘰g(x)+1L機(jī)h(x).iji=1j=1p和e是滿足以下條件的實(shí)值連續(xù)函數(shù):申(y)=0,當(dāng)y0時(shí),p(y)0,當(dāng)y0,當(dāng)y豐0時(shí).函數(shù)

48、p和e的典型取法為P(y)=max0,-ya,e(y)=lyIP,其中a1和卩1是給定的常數(shù)，通常取作1或2.minF(x,Q)=f(x)+QP(x)XRn其中a是很大的正數(shù)，P(X)是連續(xù)函數(shù).算法3-12外罰函數(shù)法Stepl選取初始數(shù)據(jù)給定初始點(diǎn)a,k:=k+1，返回Step2.kk+1k二、罰函數(shù)法S的部intS=xIxgRn,g(x)0,i=1,2,，mi為了保持迭代點(diǎn)始終含于intS，我們引入另一種罰函數(shù)G(x,r)=f(x)+rB(x)，初始罰因子a0，放大系數(shù)a1，允許誤01差0，令k二1Step2求解無(wú)約束問(wèn)題以X為初始點(diǎn)，求解無(wú)約束問(wèn)題k-1minF(x,a)=f(x)+aP

49、(x)xeRn設(shè)其最優(yōu)解為XkStep3檢查是否滿足終止準(zhǔn)那么假設(shè)aP(x)0，縮小系數(shù)0丘(0,1)，01允許誤差e0，令k=1.Step2求解無(wú)約束問(wèn)題.以x為初始點(diǎn)，求解無(wú)約束問(wèn)題k-1minG(x,r)=f(x)+rB(x);kks.t.xgintS,設(shè)其最優(yōu)解為xkStep3檢查是否滿足終止準(zhǔn)那么.假設(shè)rB(x)，那么迭代終止，kkxr=0r,k:=k+1，返回Step2.kk+1k附錄5最優(yōu)化方法復(fù)習(xí)題1、設(shè)AgRnxn是對(duì)稱矩陣，bgRn,cgR，求f(x)=xtAx+bTx+c在任意點(diǎn)x處2的梯度和Hesse矩陣.解Vf(x)=Ax+b,Vf(x)=A.2、設(shè)p(t)=f(x+

50、td)，其中f:RntR二階可導(dǎo)，xeRn,deRn,teR,試求q(t)解0(t)=Vf(x+td)Td,p(t)=dTV2f(x+td)d3、設(shè)方向deRn是函數(shù)f(x)在點(diǎn)x處的下降方向，令H=/_ddTVf(x)Vf(x)tdTVf(x)Vf(x)TVf(x)其中I為單位矩陣，證明方向p=-HVf(x)也是函數(shù)f(x)在點(diǎn)x處的下降方向.證明由于方向d是函數(shù)f(x)在點(diǎn)x處的下降方向，因此Vf(x)Td0,從而Vf(x)Tp=-Vf(x)THVf(x)-Vf(x)T(I-ddrdTVf(x)Vf(x)Vf(x)tVf(x)tVf(x)Vf(x)=-Vf(x)TVf(x)+Vf(x)Td

51、2,Vx,x,xeS,x,x,x的一切12m12m凸組合都屬于S證明充分性顯然下證必要性設(shè)S是凸集，對(duì)m用歸納法證明當(dāng)m=2時(shí),由凸集的定義知結(jié)論成立，下面考慮m=k+1時(shí)的情形令x=野九x，iii=1其中xeS,九0,i=1,2,，k+1，且九=1不妨設(shè)九豐1不然x=xeS，TOC o 1-5 h ziiik+1k+1i=1有x=(1一九)y+九xk+1k+1k+1結(jié)論成立記y=丈x1入ii=1k+1=1，0,i=1,2，,k,丈ik+11九i=1k+1那么由歸納假設(shè)知，yeS，而xeS，且S是凸集，故xeS.k+15、設(shè)S匸Rn為非空開(kāi)凸集，f:StR在S上可微，證明：f為S上的凸函數(shù)的充

52、要條件是f(x)f(x)+Vf(x)T(xx),Vx,xeS2112112證明必要性設(shè)f是S上的凸函數(shù)，那么Vx,xeS與Xe(0,1)，有12f(XX2+(i)X1)4f(X2)+(i)f(X1)于是f(珥+九(r卩f(*-f(%2)-f(X1)因S為開(kāi)集，f在S上可微，故令九t0+，得Vf(X1)T(X-*f(x)+Vf(x)T(xx),Vx,xeS，112112那么VXe0,1，取x=Xx+(1X)xeS，從而12f(x)f(x)+Vf(x)T(xx)，f(x)f(x)+Vf(x)T(xx)，122將上述兩式分別乘以X和1X后，相加得Xf(x1)+(1X)f(x2)f(x)+Vf(x)T

53、(Xx1+(1X)x2x)=f(x)=f(X曽(1-X)叮，所以f為凸函數(shù)6、證明：凸規(guī)劃minf(x)的任意局部最優(yōu)解必是全局最優(yōu)解.xeS證明用反證法設(shè)xeS為凸規(guī)劃問(wèn)題minf(x)的局部最優(yōu)解，即存在x的某xeS個(gè)5鄰域N(x)，使f(x)f(x),VxeN(x)“S假設(shè)x不是全局最優(yōu)解，那么o5存在xeS，使f(x)f(x)由于f(x)為S上的凸函數(shù)，因此VXe(0,1)，有f(Xx+(1X)x)Xf(x)+(1X)f(x)f(x)當(dāng)X充分接近1時(shí)，可使X元+(1X)xeN(x)nS，于是f(x)0,VxeSxeS證明必要性假設(shè)x為問(wèn)題minf(x)的最優(yōu)解反設(shè)存在xeS，使得xeS

54、Vf(x)T(x-x)0,VxeSxeS充分性假設(shè)Vf(x)T(x-x)0,VxeS反設(shè)存在xeS，使得f(x)f(x)/(無(wú)+九(免x)/(元)_/(九免+(1一九)元)一/(無(wú))X_XXf(x)+(1-X)f(無(wú))f(x)_f(x)-f(x)0(VX(0,1),因S為凸集，f在S上可微，故令XT0+，得Vf(x)T(x-x)f(x)-f(x)0，這與條件矛盾，故x是問(wèn)題minf(x)的最優(yōu)解.xeS8、設(shè)函數(shù)f(x)具有二階連續(xù)偏導(dǎo)數(shù)，x是f(x)的極小點(diǎn)的第k次近似，利用kf(x)在點(diǎn)x處的二階Taylor展開(kāi)式推導(dǎo)Newton法的迭代公式為kxk+1_x-V2f(x)-1Vf(x)TO

55、C o 1-5 h zkkk證明由于f(x)具有二階連續(xù)偏導(dǎo)數(shù)，故f(x)u申(x)_f(x)+Vf(x)t(x-x)+(x-x)tV2f(x)(x-x)kkk2kkk且V2f(x)是對(duì)稱矩陣，因此9(x)是二次函數(shù)為求申(x)的極小點(diǎn)，可令kV9(x)_0，即Vf(x)+V2f(x)(x-x)_0,假設(shè)V2f(x)正定，那么上式解出的kkkk9(x)的平穩(wěn)點(diǎn)就是9(x)的極小點(diǎn)，以它作為f(x)的極小點(diǎn)的第k+1次近似，記為x，即x_x-V2f(x)-1Vf(x)，這就得到了Newton法的迭代公式.k+1k+1kkk9、表達(dá)常用優(yōu)化算法的迭代公式.itX_a+(1-T)(ba)10.618

56、法的迭代公式：(kkk/|H_a+T(ba).kkkkX_a+nk1(ba),kkFkk2Fibonacci法的迭代公式：彳n-k+1(k_1,2,n-1)Fp_a+n-k(ba)kkFkkn-k+13Newton一維搜索法的迭代公式：t_t-k+1k9(t)k最速下降法用于問(wèn)題minf(x)=-xtQx+bTx+c的迭代公式:2x=xVf(x)k+ikVf(x)TQVf(x)丿kkk5Newton法的迭代公式：x=x-V2f(x)-iVf(x).k+1kkk共軛方向法用于問(wèn)題minf(x)=-xtQx+bTx+c的迭代公式:2x=xk+1kdTQdkk10、線性規(guī)劃：minf(x)=2x一x

57、+x;TOC o 1-5 h z23s.t3x+x+x60,123x一2x+2x10,123x+x-x01231用單純形法求解該線性規(guī)劃問(wèn)題的最優(yōu)解和最優(yōu)值2寫(xiě)出線性規(guī)劃的對(duì)偶問(wèn)題；3求解對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值解1引進(jìn)變量x,x,x，將給定的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式：456minf(x)=2x一x+x;TOC o 1-5 h z123s.t3x+x+x+x=60,12340.v126x1x2x3x4x5x6x431110060 x51-2201010 x611*-100120-21-10000X420210-140X530001250X211-100120-30000-1-20所給問(wèn)題的最優(yōu)

58、解為X二(0,20,0)T，最優(yōu)值為f=-20.2所給問(wèn)題的對(duì)偶問(wèn)題為：maxg(y)=-60y10y20y;TOC o 1-5 h z123s.t3yyy2,1123y+2yy1,123y2y+y.1233將上述問(wèn)題化成如下等價(jià)問(wèn)題：minh(y)=60y+10y+20y;TOC o 1-5 h z123s.t3yyy2,123y+2yy1,123y2y+y1,123y,y,y.123引進(jìn)變量y,y,y,將上述問(wèn)題化為標(biāo)準(zhǔn)形式:456minh(y)=60y+10y+20y;1232s.t3yyy+y=2,1234y+2yy+y=1,1235y2y+y+y=1,1236y,y，yn0.126y

59、1y4y5-3-1yyyyy23456-1-110022-1*010-1y6-1-210011h-60-10-200000y4-2-301-103y31-210101y6-2000110h-40-5000-20020問(wèn)題2的最優(yōu)解為y二(0,0,1)T，最優(yōu)值為h=20最小值.問(wèn)題1的最優(yōu)解為y二(0,0,1)T，最優(yōu)值為g=-20最大值.11、用0.618法求解min申(t)=(t-3)2，要求縮短后的區(qū)間長(zhǎng)度不超過(guò)0.2，初始區(qū)間取0,10解第一次迭代：取a,b=0,10,s=0.2.11確定最初試探點(diǎn)九，卩分別為11九二a+0.382(b一a)=3.82，卩=a+0.618(b一a)=6

60、.18.11111111求目標(biāo)函數(shù)值：*(九)=(3.823)2=0.67，*(卩)=(6.183)2=10.11.11比擬目標(biāo)函數(shù)值：*(九)0.2=s.11第二次迭代：a=a=0,b=p=6.1&p=九=3.82,*(p)=*(九)=0.67.1212121九二a+0.382(ba)=0.382(6.180)=2.36,*(九)=(2.363)2=0.4.2222*(九)s.2222第三次迭代：a=a=0,b=p=3.82,p=X=2.36,*(p)=*(九)=0.4.2323232九二a+0.382(b-a)二0.382(3.82-0)二1.46,甲(九)二(1.46-3)2二2.37.