最優(yōu)化方法復(fù)習(xí)題含答案

附錄5《最優(yōu)化方法》復(fù)習(xí)題1、設(shè)AeRnxn是對稱矩陣，bgRn,cgR,求f(x)=-xtAx+bTx+c在任意點x處2的梯度和Hesse矩陣.解yf(x)=Ax+b,V2f(x)=A.2、設(shè)①(t)=f(x+td),其中f:RnfR二階可導(dǎo)，xeRn,deRn,teR,試求①"(t).解①'(t)=Vf(x+td)Td,①〃(t)=drV2f(x+td)d.3、設(shè)方向deRn是函數(shù)f(x)在點x處的下降方向，令T ddr Vf(x)Vf(x)t=I -drVf(x)Vf(x)tVf(x)其中I為單位矩陣，證明方向p=-HVf(x)也是函數(shù)f(x)在點x處的下降方向.證明由于方向d是函數(shù)f(x)在點x處的下降方向，因此Vf(x)rd<0，從而Vf(x)rp=-Vf(x)tHVf(x)ddr Vf(x)Vf(x)t、=-Vf(x)t(I- - )V=-Vf(x)t(I-drVf(x)Vf(x)rVf(x)」=-Vf(x)TVf(x)+Vf(x)Td<0,所以，方向p是函數(shù)f(x)在點x處的下降方向.4、S屋Rn是凸集的充分必要條件是Vm>2,Vx1,x2,L,xeS,x1,x2,L,x的一切凸組合都屬于S.證明充分性顯然.下證必要性.設(shè)S是凸集，對m用歸納法證明.當(dāng)m=2時，由凸集的定義知結(jié)論成立，下面考慮m=k+1時的情形.令x=寸1九x.,i=1其中xeS,九i>0,i=1,2,L,k+1,且t1九.二1.不妨設(shè)九豐1(不然x=xeS,i=1結(jié)論成立)，記y=W—芻一x，有x=(1-X)y+kx,1-X i k+1 k+1k+1i=1 k+1

又3r2°，i=1,2,L,k,h3r=1，k+1 i=1 k+1則由歸納假設(shè)知，yeS,而x+1eS,且S是凸集,故、'S.5、設(shè)S之Rn為非空開凸集，f:SfR在S上可微，證明：f為S上的凸函數(shù)的充要條件是f(x2)>f(x)+Vf(x)T(x2一\),V%],x2eS.證明必要性.設(shè)f是S上的凸函數(shù)，則Vx1,x2eS及九e(°,1)，有f(九x+(1—九)x)<Xf(x)+(1—九)f(x),2 1 2 1于是f(工+入(x21一"”<f(x)_f(x),九 2 1因S為開集，f在S上可微，故令九f°+，得VfVf(x1)T(x2-x1)<f(x2)-f(xJ，即f(x)>f(x)+Vf(x)t(x-x),Vx,xeS.充分性.若有f(x)>f(x)+Vf(x)t(x-x),Vx,xeS,則VXe[°,1],取x=Xx1+(1-九)x2eS，從而f(x)>f(x)+Vf(x)T(x1-x)，f(x2)>f(x)+Vf(x)T(x2-x)，將上述兩式分別乘以X和1-X后，相加得九f(x1)+(1-X)f(x2)>f(x)+Vf(x)T(Xx1+(1-X)x2-x)=f(x)=f(Xx+(1-X)x)所以f為凸函數(shù).6、證明：凸規(guī)劃minf(x)的任意局部最優(yōu)解必是全局最優(yōu)解.xeS證明用反證法.設(shè)xeS為凸規(guī)劃問題minf(x)的局部最優(yōu)解，即存在x的某xeS個5鄰域N§(x)，使f(x)<f(x),Vxe%(x)IS.若x不是全局最優(yōu)解，則存在%eS，使f(坳<f(x).由于f(x)為S上的凸函數(shù)，因此VXe(°,1)，有f(Xx+(1-X)坳<Xf(x)+(1-X)f(x)<f(x).當(dāng)九充分接近1時，可使九元+(1—九)%eN<X)IS，于是f(X)<f(入X+(1—九)%,o矛盾.從而X是全局最優(yōu)解.7、設(shè)S之Rn為非空凸集，f:SfR是具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)，證明：X是問題minf(x)的最優(yōu)解的充要條件是：Vf(X)t(x-X)>0,VxeS.xeS證明必要性.若X為問題minf(x)的最優(yōu)解.反設(shè)存在%eS，使得XeSVf(X)t(%-X)<0，則d=%-X是函數(shù)f(x)在點X處的下降方向，這與X為問題minf(x)的最優(yōu)解矛盾.故Vf(X)t(x-x)>0,VxeS.XeS充分性.若Vf(x)t(x-X)>0,VxeS.反設(shè)存在J%eS，使得f(X)<f(X).f(X+九(%-X))-f(X)_f(九%+(1-九)X)-f(x)X X<Xf(%)+(1-X)x)_f(X)-f(X)<0(VX(0,1),X因S為凸集，f在S上可微，故令Xf0+，得Vf(X)T(%-X)<f(X)-f(X)<0,這與已知條件矛盾，故X是問題minf(x)的最優(yōu)XeS解．8、設(shè)函數(shù)f(x)具有二階連續(xù)偏導(dǎo)數(shù)，x是f(x)的極小點的第k次近似，利用kf(x)在點x^處的二階Taylor展開式推導(dǎo)Newton法的迭代公式為Xk+1_Xk-[V2f(Xk)]-1Vf(Xk)．證明由于f(x)具有二階連續(xù)偏導(dǎo)數(shù)，故f(X)氏中(X)_f(X)+Vf(X)T(X-X)+1(X-X)TV2f(X)(X-X).k k k2k k k且V2f(X)是對稱矩陣，因此叭x)是二次函數(shù).為求叭x)的極小點，可令kV①(x)_0,即Vf(xk)+V2f(xk)(x-xk)=0,若V2f(x)正定，則上式解出的叭x)的平穩(wěn)點就是叭x)的極小點，以它作為f(x)的極小點的第k+1次近似，記為Xk+1，即xk+1_xk-[V2f(xk)卜1Vf(xk)，這就得到了Newton法的迭代公式.9、敘述常用優(yōu)化算法的迭代公式．

(1)0.618法的迭代公式:九=a+(1-t)(b一a),旦=a+T(b-(1)0.618法的迭代公式:(2)Fibonacci法的迭代公式:X=a+nki(baa),

kkF(2)Fibonacci法的迭代公式:< n一k+1 (k=1,2,L,n—1).F|lx=a+—n—k(b—a)kkFkkn—k+1(3)Newton一維搜索法的迭代公式：t=t-駕).k+1k8'(t)(4)最速下降法用于問題minf(x)=1xtQx+bTx+c的迭代公式:^2Vf(x)TVf(x)、x二x- k k—Vf(x)k+1 kVf(x)TQVf(x)」kkkNewton法的迭代公式：xjx—[V2f(x)]-1Vf(x).(6)共軛方向法用于問題minf(x)=-xtQx+bTx+c的迭代公式:^2xk+1=xkVf(xjTdkxk+1=xk10、已知線性規(guī)劃：minf(x)=2x—x+x;s.t3x+x+x<60,<x—2x+2x<10,x+x—x<20,x,x,x>0.(1)用單純形法求解該線性規(guī)劃問題的最優(yōu)解和最優(yōu)值;(2)寫出線性規(guī)劃的對偶問題；(3)求解對偶問題的最優(yōu)解和最優(yōu)值.解(1)引進變量x4,x5,x6，將給定的線性規(guī)劃問題化為標(biāo)準(zhǔn)形式:minf(x)=2x—x+x;s.t3x+x+x+x=60,<x—2x+2x+x=10,x+x—x+x=20,x,x,L,x>0.

XXXXXXX31110060X1-2201010X11*-100120f-21-10000X20210-140X30001250X11-100120f-30000-1-20所給問題的最優(yōu)解為元=（0,20,0"，最優(yōu)值為f=-20.(2)所給問題的對偶問題為：一maxg(y)=-60y1-10y2-20y3;S.-3yi-y2-y^2,2 3, F+2y2-y3--1，一y1-2y2+y3-1,、y-y2,y3>0.(3)將上述問題化成如下等價問題：'minh(y)=60乂+10y2+20y3;Ss"3y1-y2-y3-2： 3, 71+2y273--1，一y1-2y2+y3-I、yjy2,y3>0.引進變量y4,y5,y6，將上述問題化為標(biāo)準(zhǔn)形式:minh(y)=60y+10y+20y;sst-3y1-y2-y3+y4=2,-y1+2y2-y3+y5=-1,（1）（2）-y1-2y2+y3+y6=1,y1,y2,L,y（1）（2）y1y2y3y4y5y6y4-3-1-11002y5-12-1*010-1y6-1-210011h-60-10-200000y4-2-301-103y31-210101y6-2000110h-40-5000-20020問題(2)的最優(yōu)解為了=(0,0,1”，最優(yōu)值為h=20(最小值).問題(1)的最優(yōu)解為y=(0,0,1”，最優(yōu)值為g=-20(最大值).11、用0.618法求解min①Q(mào))=(t-3)2，要求縮短后的區(qū)間長度不超過0.2,初始區(qū)間取[0,10]．解第一次迭代：取[a1,b]=[0,10],￡=0.2.確定最初試探點々，片分別為\=a1+0.382(b1-a1)=3.82,r1=a1+0,618(b1-a1)=6.18.求目標(biāo)函數(shù)值：叭>1)=(3.82-3)2=0.67,叭匕)=(6.18-3)2=10.11.比較目標(biāo)函數(shù)值：3九1)〈3R1).比較R1-a1=6.18-0>0.2=￡.第二次迭代：a=a=0,b=r=6.18,r=X=3.82,①(r)=①(九)=0.67.九2=a2+0.382(b2-a2)=0.382(6.18-0)=2.36,3X2)=(2.36-3)2=0.4.①(X)<中(r),r-a=3.82>￡.第三次迭代:a=a=0,b=從=3.82,從二九二2.36,中（從）二中（九）=0.4.八臺=a3+0.382（b3—a3）=0.382（3.82—0）=1.46,3九J二（1.46—3）2=2.37.叭九J>3匕）,4—九3=3.82-1.46>8.第四次迭代：a二九二1.46,b=b=3.82,九二從二2.36,①（九）二中（從）=0.4.從4=a4+0.618（b4-a4）=1.46+0.0.618（3.82-1.46）=2.918,中（電）=0.0067.①（九J>中（nJ,b4-九4=3.82-2.36>8.第五次迭代：a5=%=2.36,b5=b4=3.82,X5=N4=2.918,3九）=叭從/=0.0067.2=a5+0.618（b5-a5）=3.262,叭&）=0.0686.3九5）〈3N5）,2-a5=3.262-2.36>8.第六次迭代：a6=a5=2.36,b6=2=3.262,廉=九5=2.918,3NJ=3九5）=0.0067.九6=a6+0.382（b6-a6）=2.7045,3九J=0.087.①（九J>中（從J,b6-九6=3.262-2.7045>8.第七次迭代：a7=心=2.7045,b7=b6=3.262,X7=廉=2.918,3九）=3晨）=0.0067.從7=a7+0.618（b7-a7）=3.049,3從/=0.002.①（九）>中（從）,b一九>8.第八次迭代：a8=%=2.918,4=b7=3.262,%="=3.049,3九J=叭昨）=0.002.晨=a8+0.618（b8-a8）=3.131,3%）=0.017.①（九）〈①（從）,n-a>8.

第九次迭代:a=a=2.918,b=日=3.131,pi=X=3.049,甲(日)=(pQ)=0.002.9 8 9 8 9 9 9 8X=a+0.382(/?-a)=2.999,(p(X)=0.000001.(p(X)<(p(^t),pi故工(p(X)<(p(^t),pi故工=9X+ji—9 2,-a=3.049-2.918<8.9 9=3.024.12、用最速下降法求解min/(x)12、用最速下降法求解min/(x)=X2+2xx+2x2-4x-3x,取x(o)=代兩次.解Vf(x)=(2x+2x-4,2x+4x-3",

’ 1 2 1 2將/(%)寫成/(%)= +的形式，則。二將/(%)寫成/(%)= +的形式，則。二2、4>,b二第一次迭代:Vf(X(0))TVf(第一次迭代:Vf(X(0))TVf(OT)X(D-x(o) Vf(x(o))Vf(x(0))tQW(x(o))(0,3)(0,3)11/勾第二次迭代:X⑵一⑴一發(fā)(x⑴”?、?可口⑴)

W(x⑴)TQW3D)11/4、 (-3/2,0)'-3111/4、 (-3/2,0)'-312、<°>(-3/2、/7/4、7(-3/2,0)y22丫-3/2)(0T,迭代13、用FRT,迭代minf(x)=(%—x+x)2+(-x+x+x)2+(x+x-x' 1 2 3 1 2 3 1 2 3兩次.若給定￡=0.01,判定是否還需進行迭代計算.解/(x)=3(x2+%2+x2)-2(xx+xx+xx),1 2 3 12 13 23

(6 -2-2、再寫成f(X)=1xTGx, G=-2 6 -2 ,yf(x)= Gx.2 1-2 -2 6,第一次迭代：yf(x(0))=(0,4,0)T，令do=-Vf(x(0))=(0,-4,0)T,從x(0)出發(fā)，沿d0進行一維搜索，即求ininf(x(0)+入d0)=2-16入+48入2的最優(yōu)解，得九0二1/6,x(1)=x(0)+九0d0=(1/2,1/3,1/2)t.JVfJVf(x(1))『|vf(x(0)中9Vf(x(1))=(4/3,0,4/3)T.a0d=-Vf(x⑴)+ad=(-4/3,-8/9,-4/3)t.00從x⑴出發(fā)，沿d進行一維搜索，即求1min心0一一14.1于(min心0一一14.1于(x(1)+入d)=(2一3入，§一(6-21-2-26-2-2f1-4小2318.———人39的最優(yōu)解，得f-4/31此時+入d=

的最優(yōu)解，得f-4/31此時+入d=

111/3+3-8/9=(0,0,0)T?1-4/3JVf(x⑵)=(0,0,0)T,|yf(x(2))I=0<0.01=8.得問題的最優(yōu)解為x=(0,0,0)T，無需再進行迭代計算.14、用坐標(biāo)輪換法求解minf(x)=x2+2x2-4x-2xx，取x(0)=(1,1T，迭代1 2 1 12步.解從點X(0)=(1,1>出發(fā)，沿e=(1,0)r進行一維搜索，1即求minf(X(0)+入e)=Q—4入—3的最優(yōu)解，得X>0 1九二2,x(i)=X(0)+九e=(3,1)r.再從點X⑴出發(fā)，沿e=(0,1)r進行一維搜索，2即求minf(X(1)+入e)=2M—2X-7的最優(yōu)解，得入>0 2九二1/2,x(2)=x(1)+九e=(3,3/2)r.15、用Powell法求解minf(x)=x2+x2-3x-xx,取x(0)=(0,0)r,初始搜索方1 2 1 12向組d0=(0,1)r,4=(1,0)r，給定允許誤差￡=0.1(迭代兩次).解第一次迭代：令y(0)=X(0)=(0,0)r，從點y(0)出發(fā)沿d進行一維搜索，易得0九=0,y(1)=y(0)+九d=(0,0)r；接著從點y(1)出發(fā)沿d進行一維搜索，得133入=—,y(2)=y(1)+入d=(-,0)r1 2 11 23由此有加速方向d=y(2)-y(0)=(一,0)r.22因為|d2b3/2>e，所以要確定調(diào)整方向.9由于f(y(0))=0,f(y(1))=0,f(y(2))=-4,按(8.4.17)式有f(y⑴)-f(y⑵)=max{f(y(j))-f(y(j+1))?j=0,1}，因此m=1,并且f(y(m))-f(y(m+1))=f(y⑴)-f(y(2))=9?

4又因f(2y(2)-y(0))=0，故(8.4.18)式不成立.于是，不調(diào)整搜索方向組，并3令X(1)=y(2)=(—,0)r.2第二次迭代：3取y(0)=x(1)=(-,0)r,從點y(0)出發(fā)沿d作一維搜索，得20TOC\o"1-5"\h\z\o"CurrentDocument"3 33人——,y(1)—y(0)+入d—(一,—)T.0 4 00 24接著從點y⑴出發(fā)沿方向d作一維搜索，得1\o"CurrentDocument"3 153入=-,y⑵=y(1)+入d=(―,-)T-8 11 84由此有加速方向33d2=y(2)-y(0)=(8,4)T因為|d2||—3j5/8>￡，所以要確定調(diào)整方向.因9 45 189f(y(0))=--,f(y(1))=- ,f(y(2))=--，4 16 64故按(8.4.17