最优化设计课后习题答案

《最优化设计课后习题答案》由会员分享，可在线阅读，更多相关《最优化设计课后习题答案（30页珍藏版）》请在装配图网上搜索。

1、最优化方法-习题解答张彦斌计算机学院2014年10月20日Contents1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、412第二章线搜索算法-P27习题2、4、643第三章最速下降法和牛顿法P41习题1,2,374第四章共轭梯度法P51习题1,3，6(1)105第五章拟牛顿法P73-2126第六章信赖域方法P86-8147第七章非线性最小二乘问题P98-1，2，6188第八章最优性条件P112-1，2,5,6239第九章罚函数法P132，1-(1)、2-(1)、3-(3),62610第十一章二次规划习题11P178-1(1),5291第一章最优化理论基础-P13习题1(1)

2、、2(3)(4)、3、41. 验证下列各集合是凸集:S=(X,x2)|2x1+x21,x12x21；需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)ES及任意的实数入G0,1都有入x+(1一入)yGS.即,(Ax1+(1入)yp入x2+(1入)y2)GS证：由x(x1,x2),y(y1,y2)GS得到，2x1+x21,x12x21(1)2y1+y21,y12y21(1)入(2x+込)+(1入)(2y+y2)21,入(x2x2)+(1A)(y12y2)1合并同类项，2（入力+（1入）y）+（入x2+（1入）y2）1,（入x+（1入）yj2（入x2+（1入）y2）1证毕.2.

3、判断下列函数为凸（凹）函数或严格凸（凹）函数：（3）f（x）=x122x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5,f在凸集上是（I）凸函数的充分必要条件是f（x）对一切x为半正定；（II）严格凸函数的充分条件是72f（x）对一切x为正定。2f(x)=(22)半正定矩阵(4)4132f(x)=120(5)304正定矩阵3. 证明f(x)=xTGx+bTx为严格凸函数当且仅当Hesse矩阵G正定。证明：根据严格凸函数定义证明。对任意x=y,及任意实数入G(0,1)都有f(入x+(1入)y)0G正定保障了严格不等式成立。2反之，必要性：严格凸函数=Hesse矩阵G正定.类似

4、，当对任意x=y,及任意实数入G(0,1)都有f(Ax+(1入)y)04. 若对任意xG況n及实数00都有f(0x)=Of(x),证明f(x)在況n上为凸函数的充要条件是Vx,yG血,f(x+y)f(x)+f(y)证明：根据严格凸函数定义证明。定义：对任意x=y,及任意实数AG(0,1)都有f(Ax+(1A)y)Af(x)+(1A)f(y).充分条件：Vx,yG況有f(x+y)f(x)+f(y)对任意x=y,及任意实数AG(0,1)都有f(Ax+(1A)y)f(Ax)+f(1A)y)利用f(0x)=Of(x),f(Ax+(1A)y)f(Ax)+f(1A)y)=Af(x)+(1A)f(y).充分

5、性证毕；必要性：f(x)在況n上为凸函数=Vx,yG況n,f(x+y)f(x)+f(y)根据定义有对任意x=y,及任意实数AG(0,1)都有f(Ax+(1A)y)Af(x)+(1A)f(y).不妨取A=1，则2f(2x+(12)y)2f(x)+(12)f(y).利用f(0x)=0f(x),f(2(x+y)=2f(x+y)2(f(x)+f(y)Vx,yG肌f(x+y)epsilon)|(hdelta)if(phipphiq)b=q;phib=phiq;q=p;phiq=phip;h=b-a;p=a+(1-t)*h;phip=feval(phi,p);elsea=p;phia=phip;p=q;p

6、hip=phiq;h=b-a;q=a+t*h;phiq=feval(phi,q);endk=k+1;G(k,:)=a,p,q,b;endds=abs(b-a);dphi=abs(phib-phia);if(phip=phiq)s=p;phis=phip;elses=q;phis=phiq;endE=ds,dphi;运行：s,phis,k,G,E=golds(inlines3一2*s+1/),0,3,0.15,0.01);结果ak,pk,qk,bk01.14591.85413.000000.70821.14591.854100.43770.70821.14590.43770.70820.8754

7、1.1459(6)0.70820.87540.97871.14590.70820.81150.87540.97870.70820.77210.81150.87540.77210.81150.83590.8754s,phis,k,G,E=golds(inline(/s3一2*s+1/),0,3,0.15,0.001);GG=01.14591.85413.000000.70821.14591.854100.43770.70821.14590.43770.70820.87541.14590.70820.87540.97871.1459(7)0.70820.81150.87540.97870.7082

8、0.77210.81150.87540.77210.81150.83590.87540.77210.79650.81150.83590.79650.81150.82080.8359第4题：clearall;s,phis,k,ds,dphi,S=qmin(inline(/s3一2*s+1/),0,3,1e一2,1e-4);ss=0.8165第6题functionf=fun(x)f=100*(X(2)X(1)2)2+(1X(1)2；functiongf=gfun(x)gf=400*(x(2)x(1)2)*x(1)一2*(1一x(1),200*(x(2)x(1)2)/；functionmk=armi

9、jo(xk,dk)beta=0.5；sigma=0.2；m=0；mmax=20；while(mj=mmax)if(fun(xk+betam*dk)=fun(xk)+sigma*betam*gfun(xk)/*dk)mk=m；break；endm=m+1;endalpha=betamknewxk=xk+alpha*dkfk=fun(xk)newfk=fun(newxk)clearall;xk=-1,1;dk=1,1;mk=armijo(xk,dk)alpha=0.0020newxk=-0.99801.0020fk=4newfk=3.9956mk=93第三章最速下降法和牛顿法P41习题1,2,3第

10、1题：functionf=funone(x)f=3*x(l)2+2*x(2)24*x(1)6*x(2);functiongf=gfunone(x)gf=6*x(1)一4,4*x(2)一6/;x0=0,1;xvalk=grad(funone,gfunone,x0)x=0.66671.5000val=-5.8333k=10第2题：(1)牛顿法functionf=funtwo1(x)f=4*x(1)2+x(2)2一8*x(1)一4*x(2);functiongf=gfuntwo1(x)gf=8*x(1)一8,2*x(2)一4/;x0=0,1;xvalk=grad(funtwo1,gfuntwo1,x

11、0)x=12val=-8k=2(2)阻尼牛顿法functionHe=Hesstwo(x)n=length(x);He=zeros(n,n);He=8,0;0,2;x0=0,1;xvalk=dampnm(funtwo1,gfuntwo1,Hesstwo,x0)x=12val=-8k=1第3题.functionf=fun(x)f=(x(1)2)4+(x(1)2*x(2)2;functiongf=gfun(x)gf=4*(x(1)-2)3+2*(x(1)-2*x(2),-4*(x(1)-2*x(2);clearall;x0=03;v,val,k=grad(fun,gfun,x0)9x=2.01391

12、.0070val=3.7685e-008k=21114第四章共轭梯度法P51习题1,3,6(1)1.证明向量a1=(1,0)T和a2=(3,2)T关于矩阵A=(3235)(8)共轭.验证aTAa2=0.123.设f(x)=1xTHx+bTx,其中H=(2442),b=(33)(9)(1证明d0=(1,0)T与d=(1,2)t关于H共轭；(2)以x0=(0,0)T为初始点d0和d为搜索方向，用精确线搜索f的极小点、验证(1)dTHd=0.(2)首先，g(X)=Vf(X)=HX+b=(2442)(xx2)+(33)(10)用定理4.1,也就是算法.1产生的迭代序列，则每一步迭代点+1都是f(x)在

13、x0和方向da,d、，.，d所张成的线性流形，S=x|x=x+刀ka.d.,Va中的0kk0i=0iii极小点，特别地，xn=x*=G-1b是问题的唯一极小点精确线搜索得到步长因子牛具有如下性质，dk=0.(11)Xk+1=Xk+akdkgkT+dk=0#gTGdod0TGd0利用定理.1可知gTd.=0(i=0,1)计算过程：2ig(x)=Gx+b=8448xx21+012(13)G=8484(14)d0=g(x0)=Gxb=448)(01.5012=82(15)%i=x+a。do=(0.581+a02=82aa00+01.5(16)xk+i=Xk+akdk，即X1=Xo+a0d0；g(-X

14、1)=g1=g(X)=hX+b,；gTd0=0a0=-3/4,用=(3/4,0)T,f(X)=9/8;同理，利用(11)迭代，即/X2=X1+aidi(12)g2Td1=0a1=1/4；X2=(1/2,1/2)T,f(X2)=3/2,f(X2)f(Xj,定理4.1保证了极小点为X2=(1/2,1/2)t6.(1)f(x)=4x2+4x2一4Xx2一12x2,取初始点力0=(0.5,1)t；121220g(x)=Vf(x)=Gx+b,G(x)=V2f(x)=G;共轭方向的构造过程，取初始方向d0=g0，令x=x0+a0d，其中Vf(xjTd。=gfd0=0,在力处，用f在力的负梯度方向g与d0的

15、组合来生成d,即d=g+00d0，然后选取系数0，使得d与d0关于G共轭，即令TGd0=0确定00.因此，0。=dGd,gg0=G(xx0)=a0Gc011#Vf(x1)Td0=g1Td0=0g1Td0=848482aa00+01.5+012T82=0(17)#a0=17/104,x1=(21/26,69/52)t沁(0.80769,1.32692)tg1=(15/13,-60/13)T0=gTGdo=225/676沁0.332840dTGdod1=-g1+0Od0=(3315/2197,23205/4394)t沁(1.5088757,5.281065)t；x2=X+a1d;Vf(x2)td=

16、gtd1=0x2(255a)/169+21/26(1785a)/338+69/52g2=15/13(1530a)/169(6120a)/16960/13(18)(19)由此可以求出Q=0.127450980392157;极值点为X2=(1,2)t；5第五章拟牛顿法P73-22.DFP程序算法调用极值点x=(0.2203x10-6,0.1599x10-6)；极小值val=1.2527x10-13附程序：functionx,val,k=dfp(fun,gfun,x0)%功能：用DFP算法求解无约束问题：minf(x)%输入：x0是初始点，fun，gfun分别是目标函数及其梯度%输出：x,val分别

17、是近似最优点和最优值，k是迭代次数。maxk=1e5;%给出最大迭代次数p=0.55;a=0.4;=1e-5;k=0;n=length(x0);%Hk=inv(feval(Hess,x0);%Hk=eye(n);Hk=21;11;while(kmaxk)gk=feval(gfun,x0);%计算梯度if(norm(gk),break;end%检验终止准则dk=-Hk*gk;%计算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步长if(feval(fun,x0+pm*dj0)Hk=Hk-(Hk*yk*yk*Hk)/(yk*Hk*yk)+(sk*sk)/(sk*yk);end

18、k=k+1;x0=x;endval=feval(fun,x0);(I)当H0=1211(20)x,val,k=dfp(fun,gfun,1,-1)x=1.0e-006*-0.220306134442640-0.159928197216675val=1.252658776679855e-013k=4(II)当采用Hk=inv(feval(Hess,x0);x,val,k=dfp(fun,gfun,1,-1)x=00val=0k=16第六章信赖域方法P86-88(1)gk=-6-3;Bk=4-4;-48;dta=1;d,val,lam,k=trustq(gk,Bk,dta)d=0.87028179

19、12195740.492554154744547val=-5.928777686124834lam=5.158202203432865k=5dta=2;d,val,lam,k=trustq(gk,Bk,dta)d=1.7265693820449381.009434577568092val=-10.321239036609670lam=1.813689513237923k=7dta=5;d,val,lam,k=trustq(gk,Bk,dta)d=3.7499999801556282.249999987787719val=-14.624999999999998lam=8.078453007598

20、365e-009k=4(2)gk=1-3-2;Bk=3-12;-120;204;dta=1;d,val,lam,k=trustq(gk,Bk,dta)d=-0.2626433660099540.8374331274466090.479295543075525val=-2.501140183861169lam=1.268746535391740k=7dta=2;d,val,lam,k=trustq(gk,Bk,dta)d=-0.3333333333333821.3333333333290360.666666666665635val=-2.833333333333333lam=6.26173652

21、9506079e-012k=5dta=5;d,val,lam,k=trustq(gk,Bk,dta)d=-0.3333333333334331.3333333331807220.666666666628600val=-2.833333333333333lam=2.286320834416492e-010k=47第七章非线性最小二乘问题P98-1，2，61.设有非线性方程组f1(x)=x3-2x2-1=0f2(x)=2x1+x2-2=0(1) 列出求解这个方程组的非线性最小二乘问题的数学模型；最小二乘问题的数学表达式：minxERif(x)=1|F(x)|=1】f2(x)(2)写出求解该问题的高

22、斯-牛顿法迭代公式的具体形式：Jk=F(x(k)=(VFX(x(k),VFm(x(k)T=(3x21,k2-4x12,k(22)17#dkGN=-JkTJk-1JkTF(xk)=3x2-4x12,k,k213x212,k-41x2,k-13x2-4x12,k,k初始点取为x0=2)T,迭代三次:x3-2x2-12x1,k+x2,k-(223)#迭代公式：Xk+1=Xk+dkGNX1=X0+d0GN=3.1071428571428593.785714285714287X2=X1+d1GN=5.1574316407151187.685136718569831X3=X2+d2GN=8.7666822

23、64589718#2.(24)16.466635470820520解答：(1)测得的t,t2和y共5组数据，分别代入关系式X.Xqty=13_11+x1t1+x2t20.13=x1x30.22=斗+工(25)(26)0.08=1十袒严21+x1+2x20.13=2Xix321+2x1+2x20.19=0*1X1x31+0.1x1F1(x)=x1x3-0.13(1+x1+x2)F2(x)=2x1x3-0.22(1+2x1+x2)F3(x)=x1x3-0.08(1+x1+2x2)F4(x)=2x1x3-0.13(1+2x1+2x2)F5(x)=0.1x1x3-0.19(1+0.1x1)最小二乘问题

24、模型表示为minxERnf(x)=|F(x)|=申刀笃佇(x)(2)高斯牛顿迭代公式的具体公式为：dkGN=-JkTJk-1JkTF(xk)192.(24)#2.(24)6.利用LM方法的matlab程序求解minf(x)=1刀5r2(x)其中2i=1ir(x)=x2+x2+x2-11123(27)r2(x)=x1+x2+x3-1r3(x)=x2+x2+(x3-2)2-13123r4(x)=x1+x2-x3+1、r5(x)=x3+3x2+(5x3一】+1)2一36tt为参数，可取t=0.5,1,5等，注意当t=1时，x*=(0,0,1)t是全局极小点，这时问题为零残量，比较不同参数的计算效果。

25、functionx,val,k=lmm(Fk,JFk,x0)%功能：用L-M方法求解非线性方程组：F(x)=0%输入：x0是初始点，Fk,JFk分别是求F(xk)及F(xk)的函数%输出：x,val分别是近似解及F(xk)的值，k是迭代次数.maxk=1000;%给出最大迭代次数#p=0.55;a=0.4;=norm(feval(Fk,x0);k=0;epsilon=1e-6;n=length(x0);while(kmaxk)fk=feval(Fk,x0);%计算函数值jfk=feval(JFk,x0);%计算Jacobi阵gk=jfk*fk;dk=(jfk*jfk+“k*eye(n)gk;%

26、解方程组Gk*dk=-gk,计算搜索方向if(norm(gk)jepsilon)break;end%检验终止准则m=0;mk=0;while(m20)%用Armijc搜索求步长newf=0.5*norm(feval(Fk,x0+pm*dk)2;oldf=0.5*norm(feval(Fk,x0)2;if(newfoldf+sigma*pm*gk*dk)mk=m;break;endm=m+1;endx0=x0+pmk*dk;muk=norm(feval(Fk,x0);k=k+1;endx=x0;val=0.5*“2;%gval=norm(gfun(x);%目标函数(I)t=0.5function

27、y=Fk(x)y(1)=x(1)2+x(2)2+x(3)2-1;y(2)=x(1)+x(2)+x(3)-1;y(3)=x(1)2+x(2)2+(x(3)-2)2-1;y(4)=x(1)+x(2)-x(3)+1;y(5)=x(1)3+3*x(2)2+(5*x(3)x(1)+1)236*0.5;y=y(:);%Jacobi阵%functionJF=JFk(x)JF=2*x(1),2*x(2),2*x(3);1,1,1;2*x(1),2*x(2),2*(x(3)-2);1,1-1;3*x(1)22*(5*x(3)x(1)+1),6*x(2),10*(5*x(3)x(1)+1);x0=1,1,1/;x

28、,val,k=lmm(Fk/JFk,x0)x=0.339361063668441-0.2001835788046710.714384339944574val=0.486062168183995219k=(II) t=1；注意，这里x*=(0,0,1)T是全局极小点，这时问题为零残量。cleara;x0=1,1,1/;x,val,k=lmm(fFkf/JFk,x0)x=-0.0000000000000800.0000000000000870.999999999999985val=2.815888304992978e-027k=8(III) t=5;clearall;x0=1,1,1/;x,val

29、,k=lmm(/Fk/,/JFk/,x0)x=-0.4907138309295490.1031440261984632.384345136824180val=14.450411547247533k=14#(28)8第八章最优性条件P112-1，2,5,61.验证x=(2,1)T是否为下列最优化问题的KT点:mins.t.f(x)=(x13)2+(x22)2X2+X20.验证：计算f(x)=2(x12(x2-32)-2-2,h(X)=x=xg1(x)=2x12x2-4-2,g2(x),g3(x)f(x)-h(x)人W(x)=0214102“2入12入20入31=0(29)(30)(31)23(2

30、8)#(28)令&=0入=0解得=3人=3所以/(x)h(x)刀33入gi(X)=0入風仗)=0,入0，i=】2,3这表明X是KT点,(X,(,)是KT对，其中=2,A=(3,0,0)T.332.对于最优化问题:minf(x)=4x33x2s.t.(x33)2+x2+10,4x3x20,x2+70.求满足KT条件的点。解:类似第1题#4A2(XA3)A1A0312131=0(34)(35)(36)(37)(38)f(x)=-3=-3,Vh(x)=0x=xL7/、一2(x3)/_、一1/_、0Vg1(x)=11J,Vg2(x)=_訂，Vg3(x)=1令/Vf(x)-Vh(x)刀3，.Vg.(X)

31、=0iil入風(x)=0,入0，i=12,3即：(X3)2+4X+1=0=X=1或X=4当X=4时，亍？=0,A=7/3,&=2/3,不满足0舍去;当X=1时,X?=3,A=7/3,&=16/3,满足召0；5. 利用KT条件推出线性规划minz=cTXs.tAx0，i=12Vg1(x)=A,Vg2(x)=I,其拉格朗日函数为L(x,入,入2)=cTx一AT(b一Ax)一ATx对上述函数关于x求极小.令VxL(x,入i，入2)=C入2+AT1=0,由(39)入22(x)=入2x=0,令入2=0,因此最优性条件为：(40)c+At入=0入(b一Ax)=0,A106. 设二次规划minf(x)=1x

32、THx+cTx2(41s.t.Ax=b,其中H为n阶对称正定矩阵，矩阵A行满秩，求其最优解并说明解的唯一性。解：首先写出该问题的拉格朗日函数为L(x,A)=xTHx+cTx一At(Ax一b).对上述函数关于x求极小.由于H对称正定，故函数L(x,A)关于x为凸函数.令V%L(x,A)=Hx+c一ATA=0,H对称正定，以及等式约束条件x=b,25Hx+cAt入=0,x+H-CH-AT入=0,Ax+AH-1cAH-1At入=0,b+AH-1cAH-1At入=0,H对称正定，A行满秩，因此,AH-iAT可逆(需要简单证明)入=(AH-1At)-1(b+AH-1c),因此有拉格朗日乘子的唯一性解，也

33、就有了最优解=H-1c+H-1At入的唯一性。9第九章罚函数法P132,1-(1)、2-(1)、3-(3),61- (1)用:外罚函数法求解下列约束优化问题：mins.t.fx-=x11,2(42)解：由等式约束得x2=W121化问题1代入目标函数得到一个无约束的单变量极小min0(X)=X士1x2现在要使构造的罚函数P(x)，满足P(x)=0,0,x2+x21=012x2+x21=0,12(43)只要令戸(X)=(X2+X21)2即可.现在考察目标函数和上述罚函数的组合P(x,a)=f(x)+P(x)=XX2+b戸(x)其中b0是充分大的正数，称为罚因子(罚参数)。求这个组合函数的极小点.由

34、dP(x,o)=dP(x,o)=0dXdx?得1+4bX(x2+x21)=0-1+4ax2(x2+x21)=0丁，当(7TX,X=0(舍去)和X=由此可得X=x2=0，因此X(2x21)=1。所以X=x2=1,minf(x)=a/2.2- (1).用内点法求解下列约束优化问题：1)(45)minf(X)=X1+X2S.t.X2+X20；12(47)解：PHR算法：我们回到一般约束优化问题(9.28,9.33)(书上),我们来构造求解(47)的乘子法.此时,增广拉格朗日函数为(x，“，入=f(%)刀1=1如他(x)+刀i=1h2(x)+2刀mt/wf0,叫(x)-入川2入2)z_-乘子迭代公式为

35、(k+丄=(kL叫(xk)，i=1,2厂,1(入k+1)=max0,(入k)agi(xk)y,i=12,，m令0=(马=怦(叫)+Em=1mingi(xk),于2)2则终止准则为0k重-要(x,A,a)=f(x)+2-(min0,ax1入J2入f)令dXd砂tdx2=2X=0,if(ax1入)0(48)=2x2=0-数值方法角度取初始点x0=(0,0)t,入=1,a1=2,=1e5x1=x2=0,minf(x)=01x2=0；或者X=0,x2=01)271)#atx,X=0,x2=0;minf(x)=01)#6.略。10第十一章二次规划习题11P178-1(1)，51.用拉格朗日方法求解下列二

36、次规划问题：(1)minf(x)=2x21+x22+x1x2-x1-x2,(49)s.t.x1+x2=1;首先写出该问题的拉格朗日函数为L(x,入)=1xTHx+cTx一入(AX1).H=1412,c=-1,A=(1,1),(50)对上述函数关于x求极小.由于H对称正定，故函数L(x,入)关于x为凸函数.令xL(x,入)=Hx+c一At入=0,H对称正定，以及等式约束条件x=1,-AAT)(x)=(C(51)(I一1)(I2卜(1)(52)解得(x；)=(3/4),(53)(54)5设A6Rmxn行满秩，a6Rn,证明二次规划问题min1(xa)T(xa),s.t.Ax=b;的解以及相应的拉格

37、朗日乘子分别为：x*=a+At(AAt)-i(bAa),A*=(AAt)-i(bAa)证明：mins.t.1xTHxaTx+iaTa,Ax=b；2(55)其中H单位矩阵E,对上述函数关于x求极小.令由于H对称正定，故函数L（x,入）关于x为凸函数.%L(x,入)=HxaAT入=0,H对称正定，以及等式约束条件x=b,HxaAT入=0,x+H1(a)H1At入=0,Ax+AH-1(a)AH-1AT入=0,b+AH-1(a)AH-1At入=0,其中H单位矩阵E,A行满秩，因此，AAt可逆(需要简单证明)入=(AAt)-1(bAa),因此有拉格朗日乘子的唯一性解,也就有了最优解=H-1(a)+H-1AT入=a+AT(AAT)1(bAa)的唯一性。29