最优化方法复习题含答案

附录5《最优化方法》复习题1、设AeRnxn是对称矩阵，bgRn,cgR,求f(x)=-xtAx+bTx+c在任意点x处2的梯度和Hesse矩阵.解yf(x)=Ax+b,V2f(x)=A.2、设①(t)=f(x+td),其中f:RnfR二阶可导，xeRn,deRn,teR,试求①"(t).解①'(t)=Vf(x+td)Td,①〃(t)=drV2f(x+td)d.3、设方向deRn是函数f(x)在点x处的下降方向，令T ddr Vf(x)Vf(x)t=I -drVf(x)Vf(x)tVf(x)其中I为单位矩阵，证明方向p=-HVf(x)也是函数f(x)在点x处的下降方向.证明由于方向d是函数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是函数f(x)在点x处的下降方向.4、S屋Rn是凸集的充分必要条件是Vm>2,Vx1,x2,L,xeS,x1,x2,L,x的一切凸组合都属于S.证明充分性显然.下证必要性.设S是凸集，对m用归纳法证明.当m=2时，由凸集的定义知结论成立，下面考虑m=k+1时的情形.令x=寸1九x.,i=1其中xeS,九i>0,i=1,2,L,k+1,且t1九.二1.不妨设九丰1(不然x=xeS,i=1结论成立)，记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则由归纳假设知，yeS,而x+1eS,且S是凸集,故、'S.5、设S之Rn为非空开凸集，f:SfR在S上可微，证明：f为S上的凸函数的充要条件是f(x2)>f(x)+Vf(x)T(x2一\),V%],x2eS.证明必要性.设f是S上的凸函数，则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为凸函数.6、证明：凸规划minf(x)的任意局部最优解必是全局最优解.xeS证明用反证法.设xeS为凸规划问题minf(x)的局部最优解，即存在x的某xeS个5邻域N§(x)，使f(x)<f(x),Vxe%(x)IS.若x不是全局最优解，则存在%eS，使f(坳<f(x).由于f(x)为S上的凸函数，因此VXe(°,1)，有f(Xx+(1-X)坳<Xf(x)+(1-X)f(x)<f(x).当九充分接近1时，可使九元+(1—九)%eN<X)IS，于是f(X)<f(入X+(1—九)%,o矛盾.从而X是全局最优解.7、设S之Rn为非空凸集，f:SfR是具有一阶连续偏导数的凸函数，证明：X是问题minf(x)的最优解的充要条件是：Vf(X)t(x-X)>0,VxeS.xeS证明必要性.若X为问题minf(x)的最优解.反设存在%eS，使得XeSVf(X)t(%-X)<0，则d=%-X是函数f(x)在点X处的下降方向，这与X为问题minf(x)的最优解矛盾.故Vf(X)t(x-x)>0,VxeS.XeS充分性.若Vf(x)t(x-X)>0,VxeS.反设存在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)的最优XeS解．8、设函数f(x)具有二阶连续偏导数，x是f(x)的极小点的第k次近似，利用kf(x)在点x^处的二阶Taylor展开式推导Newton法的迭代公式为Xk+1_Xk-[V2f(Xk)]-1Vf(Xk)．证明由于f(x)具有二阶连续偏导数，故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)是二次函数.为求叭x)的极小点，可令kV①(x)_0,即Vf(xk)+V2f(xk)(x-xk)=0,若V2f(x)正定，则上式解出的叭x)的平稳点就是叭x)的极小点，以它作为f(x)的极小点的第k+1次近似，记为Xk+1，即xk+1_xk-[V2f(xk)卜1Vf(xk)，这就得到了Newton法的迭代公式.9、叙述常用优化算法的迭代公式．

(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、已知线性规划：minf(x)=2x—x+x;s.t3x+x+x<60,<x—2x+2x<10,x+x—x<20,x,x,x>0.(1)用单纯形法求解该线性规划问题的最优解和最优值;(2)写出线性规划的对偶问题；(3)求解对偶问题的最优解和最优值.解(1)引进变量x4,x5,x6，将给定的线性规划问题化为标准形式: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所给问题的最优解为元=（0,20,0"，最优值为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，将上述问题化为标准形式: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)的最优解为了=(0,0,1”，最优值为h=20(最小值).问题(1)的最优解为y=(0,0,1”，最优值为g=-20(最大值).11、用0.618法求解min①Q)=(t-3)2，要求缩短后的区间长度不超过0.2,初始区间取[0,10]．解第一次迭代：取[a1,b]=[0,10],£=0.2.确定最初试探点々，片分别为\=a1+0.382(b1-a1)=3.82,r1=a1+0,618(b1-a1)=6.18.求目标函数值：叭>1)=(3.82-3)2=0.67,叭匕)=(6.18-3)2=10.11.比较目标函数值：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⑵一⑴一发(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)出发，沿d0进行一维搜索，即求ininf(x(0)+入d0)=2-16入+48入2的最优解，得九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⑴出发，沿d进行一维搜索，即求1min心0一一14.1于(min心0一一14.1于(x(1)+入d)=(2一3入，§一(6-21-2-26-2-2f1-4小2318.———人39的最优解，得f-4/31此时+入d=

的最优解，得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.得问题的最优解为x=(0,0,0)T，无需再进行迭代计算.14、用坐标轮换法求解minf(x)=x2+2x2-4x-2xx，取x(0)=(1,1T，迭代1 2 1 12步.解从点X(0)=(1,1>出发，沿e=(1,0)r进行一维搜索，1即求minf(X(0)+入e)=Q—4入—3的最优解，得X>0 1九二2,x(i)=X(0)+九e=(3,1)r.再从点X⑴出发，沿e=(0,1)r进行一维搜索，2即求minf(X(1)+入e)=2M—2X-7的最优解，得入>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)出发沿d进行一维搜索，易得0九=0,y(1)=y(0)+九d=(0,0)r；接着从点y(1)出发沿d进行一维搜索，得133入=—,y(2)=y(1)+入d=(-,0)r1 2 11 23由此有加速方向d=y(2)-y(0)=(一,0)r.22因为|d2b3/2>e，所以要确定调整方向.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)式不成立.于是，不调整搜索方向组，并3令X(1)=y(2)=(—,0)r.2第二次迭代：3取y(0)=x(1)=(-,0)r,从点y(0)出发沿d作一维搜索，得20TOC\o"1-5"\h\z\o"CurrentDocument"3 33人——,y(1)—y(0)+入d—(一,—)T.0 4 00 24接着从点y⑴出发沿方向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>£，所以要确定调整方向.因9 45 189f(y(0))=--,f(y(1))=- ,f(y(2))=--，4 16 64故按(8.4.17