最优化原理和方法(试题+答案)

《最优化原理与算法》试卷一、填空题（每小题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)(..)(min212121xxxgxxxhtsxxf的K-K-T条件为：.7.以下约束优化问题：1..)(min212221xxtsxxxf的外点罚函数为（取罚参数为）.二、证明题（7分+8分）1.设1,2,1,:miRRgni和mmiRRhni,1,:1都是线性函数，证明下面的约束问题：},,1{,0)(},1{,0)(..)(min1112mmEjxhmIixgtsxxfjinkk是凸规划问题。2.设RRf2:连续可微，niRa，Rhi，mi,2,1，考察如下的约束条件问题：},1{,0}2,1{,0..)(min11mmEibxamIibxatsxfiTiiTi设d是问题1||||,0,0..)(mindEidaIidatsdxfTiTiT的解，求证：d是f在x处的一个可行方向。三、计算题（每小题12分）1.取初始点Tx)1,1()0(.采用精确线性搜索的最速下降法求解下面的无约束优化问题（迭代2步）：22212)(minxxxf2.采用精确搜索的BFGS算法求解下面的无约束问题：21222121)(minxxxxxf3.用有效集法求解下面的二次规划问题：.0,001..42)(min2121212221xxxxtsxxxxxf4.用可行方向算法（Zoutendijk算法或FrankWolfe算法）求解下面的问题（初值设为)0,0()0(x,计算到)2(x即可)：.0,033..221)(min21211222121xxxxtsxxxxxxf参考答案一、填空题1.3421242121xxxx42242.0)(dxfT3.T)0,1,2(，T)1,0,3(（答案不唯一）。4.)()(12xfxf5.牛顿法、修正牛顿法等（写出一个即可）6.0)(,0,0010021),,(21212121xxxxxxxxLx7.2212221)1(21)(xxxxxF二、证明题1.证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。一方面，由于f二次连续可微，Ixf2)(2正定，根据凸函数等价条件可知目标函数是凸函数。另一方面，约束条件均为线性函数，若任意Dyx,可行域，则EiyhxhyxhIiygxgyxgjjjiii0)()1()())1((0)()1()())1((故Dyx)1(，从而可行域是凸集。2.证明：要证d是f在x处的一个可行方向，即证当Dx，nRd时，0，使得Ddx，],0(当Ii时，0iTibxa，0daTi，故0)(dabxabdxaTiiTiiTi；当Ei时，0iTibxa，0daTi，故0)(dabxabdxaTiiTiiTi.因此，d是f在x处的一个可行方向。三、计算题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)(kdk0T)1,1(T)4,2(T)4,2(18/51T)9/1,9/4(T)9/2,9/8(T)9/2,9/8(2/12T)0,0(2.解：取Tx)1,1()0(IB012212)(xxxxxf第一步迭代：10)()0(xf10)()0(10)0(xfBd，2)0()0()1(21)()(dxf，令0)('，求得2/10；第二步迭代：211)0(0)0()1(dxx，021)()1(xf，210)0()1()0(xxs121)()()0()1()0(xfxfy2112/32112/1100010011B)1(d4121)()1(11xfB，)()()1()1(dxf，令0)('，求得21。故00)1(1)1()2(dxx，由于00)()2(xf，故)2(x为最优解。k)(kx)()(kxf)(kdk0T)1,1(T)1,0(T)1,0(1/21T)2/1,1(T)0,2/1(T)4/1,2/1(22T)0,0(3.解：取初始可行点(0)(0)0(0,0),(){2,3}.xAAx求解等式约束子问题22121212min24..0,0ddddstdd得解和相应的Lagrange乘子(0)(1)(0)10(0,0),(2,4)(0,0),\{3}{2}TTTdxxAA故得转入第二次迭代。求解等式约束子问题2212121min24..0ddddstd得解(1)(1)(1)(1)111(1)(1)(0,2)01min{1,1,3,0}2TTTTiiiTTiidbaxbaxiadadad计算令(2)(1)(1)121(0,1),{1}{1,2}TxxdAA转入第三次迭代。求解等式约束子问题221212121min22..0,0ddddstddd得解和相应的Lagrange乘子(2)(0,0),(2,0)TTd由于(2)0，故得所求二次规划问题的最优解为(2)(0,1)Txx，相应的Lagrange乘子为(2,0,0)T4.解：计算梯度得Txxxxxf)2,22()(1221当0k时，)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(.由线性搜索tttdxft3492)(min2)0()0(10得10t.因此，Tdtxx)0,3/2()0(0)0()1(.重复以上计算过程得下表：k)(kx)()(kxf)(ky)(kdkt0T)0,0(T)0,2(T)0,3/2(T)0,3/2(11T)0,3/2(T)3/2,3/2(T)2,0(T)2,3/2(2512T)252,2516(