2022年最优化原理和方法 .pdf

最优化原理与算法试卷一、填空题（每小题5 分）1. 若212121312112)(xxxxxxxf， 则)(xf，)(2xf . 2. 设f连续可微且0)(xf，若向量d满足，则它是f在x处的一个下降方向。3. 向量T)3,2, 1(关于 3 阶单位方阵的所有线性无关的共轭向量有 . 4. 设RRfn:二次可微，则f在x处的牛顿方向为 . 5. 举出一个具有二次终止性的无约束二次规划算法： . 6. 以下约束优化问题：0)(01)(.)(min212121xxxgxxxhtsxxf的 K-K-T 条件为： . 7. 以下约束优化问题：1. .)(min212221xxtsxxxf的外点罚函数为（取罚参数为） . 二、证明题（ 7 分+8 分）1. 设1,2, 1,:miRRgni和mmiRRhni, 1,:1都是线性函数，证明下面的约束问题：, 1, 0)(,1,0)(.)(min1112mmEjxhmIixgtsxxfjinkk是凸规划问题。2. 设RRf2:连续可微，niRa，Rhi，mi, 2, 1，考察如下的约束条件问题：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页, 1,02, 1,0.)(min11mmEibxamIibxatsxfiTiiTi设d是问题1|, 0,0. .)(mindEidaIidatsdxfTiTiT的解，求证：d是f在x处的一个可行方向。三、计算题（每小题12 分）1. 取初始点Tx)1 ,1 ()0(. 采用精确线性搜索的最速下降法求解下面的无约束优化问题（迭代 2 步） ：22212)(minxxxf2. 采用精确搜索的BFGS算法求解下面的无约束问题：21222121)(minxxxxxf3. 用有效集法求解下面的二次规划问题：.0,001.42)(min2121212221xxxxtsxxxxxf4. 用可行方向算法（Zoutendijk算法或Frank Wolfe算法）求解下面的问题（初值设为)0,0()0(x, 计算到)2(x即可 ) ：.0,033. .221)(min21211222121xxxxtsxxxxxxf精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页参考答案一、填空题1.3421242121xxxx42242. 0)(dxfT3. T)0 ,1,2(，T)1, 0,3(（答案不唯一） 。4. )()(12xfxf5. 牛顿法、修正牛顿法等（写出一个即可）6. 0)(, 0,0010021),(21212121xxxxxxxxLx7.2212221) 1(21)(xxxxxF二、证明题1. 证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。一方面，由于f二次连续可微，Ixf2)(2正定，根据凸函数等价条件可知目标函数是凸函数。另一方面，约束条件均为线性函数，若任意Dyx,可行域，则EiyhxhyxhIiygxgyxgjjjiii0)()1()()1 (0)()1()()1 (故Dyx)1(，从而可行域是凸集。2. 证明：要证d 是f在x处的一个可行方向，即证当Dx，nRd时，0，使得Ddx，,0(当Ii时，0iTibxa，0daTi，故0)(dabxabdxaTiiTiiTi；当Ei时，0iTibxa，0daTi，故0)(dabxabdxaTiiTiiTi.因此，d 是f在x处的一个可行方向。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页三、计算题1. 解：222211)(2)()()(dxdxdxf令0)( 得2221221122ddxdxd；2142)(xxxf第一次迭代：42)()0(xf，42)()0()0(xfd，)()()0()0(dxf，令0)( ，求得18/50；第二次迭代：9194)0(0)0()1(dxx，9298)()1(xf，9298)()1()1(xfd，)()()1()1(dxf，令0)( ，求得2/11，故00)1(1)1()2(dxx，由于00)()2(xf，故)2(x为最优解。k)(kx)()(kxf)(kdk0 T)1 , 1(T)4 ,2(T)4,2(18/51 T)9/1, 9/4(T)9/2, 9/8(T)9/2, 9/8(2/12 T)0,0(2. 解：取Tx)1 , 1()0(IB012212)(xxxxxf第一步迭代：10)()0(xf10)()0(10)0(xfBd，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页2)0()0()1(21)()(dxf，令0)( ，求得2/10；第二步迭代：211)0(0)0()1(dxx，021)()1(xf，210)0()1()0(xxs121)()()0()1()0(xfxfy2112/32112/1100010011B)1(d4121)()1(11xfB，)()()1()1(dxf，令0)( ，求得21。故00)1(1)1()2(dxx，由于00)()2(xf，故)2(x为最优解。k)(kx)()(kxf)(kdk0 T)1 , 1(T) 1 ,0(T)1,0(1/2 1 T)2/1 , 1 (T)0,2/1(T)4/1,2/1(2 2 T)0,0(3.解：取初始可行点(0)(0)0(0,0),()2,3.xAA x求解等式约束子问题22121212min24.0,0ddddst dd得解和相应的Lagrange 乘子(0)(1)(0)10(0,0) ,( 2, 4)(0,0),32TTTdxxAA故得转入第二次迭代。求解等式约束子问题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页2212121min24.0ddddst d得解(1)(1)(1)(1)111(1)(1)(0,2)01min1,1,3,02TTTTiiiTTiidba xba xia da da d计算令(2)(1)(1)121(0,1) ,11,2TxxdAA转入第三次迭代。求解等式约束子问题221212121min22.0,0ddddst ddd得解和相应的Lagrange 乘子(2)(0,0) ,(2,0)TTd由于(2)0，故得所求二次规划问题的最优解为(2)(0,1)Txx，相应的 Lagrange 乘子为(2,0,0)T4. 解：计算梯度得Txxxxxf)2,22()(1221当0k时，)0, 0()0(x，Txf)0,2()(.)0(y是下面线性规划问题的解：.0,033.2)(min21211)0(yyyytsyyxf解此线性规划（作图法）得Ty)0 , 3/2()0(，于是Txyd)0,3/2()0()0()0(.由线性搜索精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页tttdxft3492)(min2)0()0(10得10t.因此，Tdtxx)0 ,3/2()0(0)0()1(.重复以上计算过程得下表：k)(kx)()(kxf)(ky)(kdkt0 T)0 ,0(T)0,2(T)0 ,3/2(T)0 , 3/2(1 1 T)0, 3/2(T)3/2,3/2(T)2,0(T)2,3/2(2512 T)252,2516(精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页