最优化方法试题+答案

`一、填空题21xx1.若f(x)xx1131，则f(x)，1212xx222f(x).2.设f连续可微且f(x)0，若向量d满足，则它是f在x处的一个下降方向。3.向量(1,2,3)T关于3阶单位方阵的所有线性无关的共轭向量有.4.设f:RnR二次可微，则f在x处的牛顿方向为.5.举出一个具有二次终止性的无约束二次规划算法：.6.以下约束优化问题：minf(x)x1s.t.h(x)xx21021g(x)xx012的K-K-T条件为：.7.以下约束优化问题：minf(x)x2x212s.t.xx112的外点罚函数为（取罚参数为）.二、证明题（7分+8分）1.设g:RnR,i1,2,m和h:RnR,im1,m都是线性函数，证明下i1i1面的约束问题：nminf(x)x2kk1s.t.g(x)0,iI{1,m}i1h(x)0,jE{m1,,m}j1是凸规划问题。2.设f:R2R连续可微，aRn，hR，i1,2,m，考察如下的约束条件问题：iiWord文档`minf(x)s.t.aTxb0,iI{1,2m}ii1aTxb0,iE{m1,m}ii1设d是问题minf(x)Tds.t.aTd0,iIiaTd0,iEi||d||1的解，求证：d是f在x处的一个可行方向。三、计算题（每小题12分）1.取初始点x(0)(1,1)T.采用精确线性搜索的最速下降法求解下面的无约束优化问题（迭代2步）：minf(x)x22x2122.采用精确搜索的BFGS算法求解下面的无约束问题：1minf(x)x2x2xx212123.用有效集法求解下面的二次规划问题：minf(x)x2x22x4x1212s.t.xx1012x0,x0.124.用可行方向算法（Zoutendijk算法或FrankWolfe算法）求解下面的问题（初值设为x(0)(0,0),计算到x(2)即可)：1minf(x)x2xxx22x211221s.t.3xx312x0,x0.12Word文档`参考一、填空题4x2x1421.122x4x324122.f(x)Td03.(2,1,0)T，(3,0,1)T（答案不唯一）。4.2f(x)1f(x)5.牛顿法、修正牛顿法等（写出一个即可）6.12x0L(x,,)1x0xx210210,xx0,(xx)0121217.F(x)x2x2(xx1)212212二、证明题1.证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。一方面，由于f二次连续可微，2f(x)2I正定，根据凸函数等价条件可知目标函数是凸函数。另一方面，约束条件均为线性函数，若任意x,yD可行域，则g(x(1)y)g(x)(1)g(y)0iIiiih(x(1)y)h(x)(1)h(y)0iEjjj故x(1)yD，从而可行域是凸集。2.证明：要证d是f在x处的一个可行方向，即证当xD，dRn时，0，使得xdD，(0,]当iI时，aTxb0，aTd0，故aT(xd)baTxbaTd0；iiiiiiii当iE时，aTxb0，aTd0，故aT(xd)baTxbaTd0.iiiiiiii因此，d是f在x处的一个可行方向。Word文档`三、计算题1.解：()f(xd)(xd)22(xd)21122dx2dx2x令'()0得1122；f(x)1d22d24x12222第一次迭代：f(x(0))，d(0)f(x(0))，()f(x(0)d(0))，44令'()0，求得5/18；0488999第二次迭代：x(1)x(0)d(0)，f(x(1))，d(1)f(x(1))，01229990()f(x(1)d(1))，令'()0，求得1/2，故x(2)x(1)d(1)，由1100于f(x(2))，故x(2)为最优解。0kx(k)f(x(k))d(k)k0(1,1)T(2,4)T(2,4)T5/181(4/9,1/9)T(8/9,2/9)T(8/9,2/9)T1/22(0,0)T2.解：取x(0)(1,1)TBI0xxf(x)122xx21第一步迭代：00f(x(0))d(0)B1f(x(0))，101Word文档`1()f(x(0)d(0))(1)2，令'()0，求得1/2；20第二步迭代：110x(1)x(0)d(0)1，f(x(1))2，s(0)x(1)x(0)102021y(0)f(x(1))f(x(0))2110001/213/21B10101121212d(1)B1f(x(1))，()f(x(1)d(1))，令'()0，求得2。故111400x(2)x(1)d(1)，由于f(x(2))，故x(2)为最优解。100kx(k)f(x(k))d(k)k0(1,1)T(0,1)T(0,1)T1/221(1,1/2)T(1/2,0)T(1/2,1/4)T2(0,0)T3.解：取初始可行点x(0)(0,0),AA(x(0)){2,3}.求解等式约束子问题0mind2d22d4d1212s..td0,d012得解和相应的Lagrange乘子d(0)(0,0)T,(2,4)T故得x(1)x(0)(0,0)T,AA\{3}{2}10转入第二次迭代。求解等式约束子问题Word文档`mind2d22d4d1212s..td01得解d(1)(0,2)T0计算baTx(1)baTx(1)1min{1,iii1,3,aTd(1)0}111aTd(1)iaTd(1)2ii令x(2)x(1)d(1)(0,1)T,AA{1}{1,2}121转入第三次迭代。求解等式约束子问题mind2d22d2d1212s..tdd0,d0121得解和相应的Lagrange乘子d(2)(0,0)T,(2,0)T由于(2)0，故得所求二次规划问题的最优解为xx(2)(0,1)T，相应的Lagrange乘子为(2,0,0)T4.解：计算梯度得f(x)(2xx2,2xx)T1221当k0时，x(0)(0,0)，f(x)(2,0)T.y(0)是下面线性规划问题的解：minf(x(0))y2y1s.t.3yy312y0,y0.12解此线性规划（作图法）得y(0)(2/3,0)T，于是d(0)y(0)x(0)(2/3,0)T.由线性搜索Word文档`24minf(x(0)td(0))t2t0t193得t1.因此，x(1)x(0)td(0)(2/3,0)T.重复以上计算过程得下表：00kx(k)f(x(k))y(k)d(k)tk01(0,0)T(2,0)T(2/3,0)T(2/3,0)T11(2/3,0)T(2/3,2/3)T(0,2)T(2/3,2)T252162(,)T2525Word文档