最优化方法考试试卷.pdf

一、填空题1.若f(x)x1 x121 x1则f(x)，x2 1312xx，222f(x).2.设f连续可微且f(x)0，若向量d满足，则它是f在x处的一个下降方向。3.向量(1,2,3)关于 3 阶单位方阵的所有线性无关的共轭向量有.4.设f:R R二次可微，则f在x处的牛顿方向为.5.举出一个具有二次终止性的无约束二次规划算法：.6.以下约束优化问题：nTmin f(x)x1s.t.h(x)x2 x121 0g(x)x1 x2 0的 K-K-T 条件为：.7.以下约束优化问题：2min f(x)x12 x2s.t.x1 x21二、证明题（7 分+8 分）的外点罚函数为（取罚参数为）.nn1.设gi:R R,i 1,2,m1和hi:R R,i m11,m都是线性函数，证明下面的约束问题：2min f(x)xkk1ns.t.gi(x)0,hj(x)0,是凸规划问题。iI 1,m1jE m11,mn22.设f:R R连续可微，ai R，hiR，i 1,2,m，考察如下的约束条件问题：最优化方法考试试卷min f(x)s.t.aix bi 0,iI 1,2m1aix bi 0,iE m11,m设d是问题TTminf(x)Tds.t.aid 0,iIaid 0,iE|d|1的解，求证：d是f在x处的一个可行方向。三、计算题（每小题 12 分）1.取初始点x（迭代 2 步）：2min f(x)x12 2x2(0)TT(1,1)T.采用精确线性搜索的最速下降法求解下面的无约束优化问题2.采用精确搜索的 BFGS 算法求解下面的无约束问题：min f(x)122x1 x2 x1x223.用有效集法求解下面的二次规划问题：2min f(x)x12 x2 2x1 4x2s.t.x1 x21 0 x1 0,x2 0.4.用可行方向算法（Zoutendijk 算法或 Frank Wolfe 算法）求解下面的问题（初值设为x(0)(0,0),计算到x(2)即可)：min f(x)122x1 x1x2 x2 2x12s.t.3x1 x2 3x1 0,x2 0.参考答案一、填空题1.4x1 2x212x 4x 321T42242.f(x)d 03.(2,1,0)，(3,0,1)（答案不唯一）。4.f(x)f(x)5.牛顿法、修正牛顿法等（写出一个即可）6.21TT1 2x10 xL(x,)0 x2 x121 0 0,x1 x2 0,(x1 x2)07.F(x)x1 x2221(x1 x21)22二、证明题1.证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。一方面，由于f二次连续可微，f(x)2I正定，根据凸函数等价条件可知目标函数是凸函数。另一方面，约束条件均为线性函数，若任意x,y D可行域，则2gi(x(1)y)gi(x)(1)gi(y)0hj(x(1)y)hj(x)(1)hj(y)0故x (1)yD，从而可行域是凸集。iIiE2.证明：要证d是f在x处的一个可行方向，即证当xD，d R时，0，使得nx d D，(0,当iI时，aixbi 0，aid 0，故ai(xd)bi aixbiaid 0；当iE时，aixbi 0，aid 0，故ai(xd)bi aixbiaid 0.因此，d是f在x处的一个可行方向。TTTTTTTTTT三、计算题1.解：()f(x d)(x1d1)2(x2d2)令()0得(0)(0)第一次迭代：f(x(0)，d f(x)22d1x12d2x2d1 2d22422；f(x)2x14x22(0)(0)()f(xd)，4令()0，求得0 5/18；第二次迭代：x(1)x(0)0d(0)848999，f(x(1)d(1)f(x(1)2129990()f(x(1)d(1)，令()0，求得11/2，故x(2)x(1)1d(1)0，由 于f(x(2)，故x00(2)为最优解。k0122.解：取x(0)x(k)(1,1)T(4/9,1/9)T(0,0)Tf(x(k)(2,4)T(8/9,2/9)Td(k)(2,4)T(8/9,2/9)Tk5/181/2(1,1)TB0 Ix1 x2f(x)2x x12第一步迭代：0f(x(0)1 0 1d(0)B0f(x(0)1，()f(x(0)d(0)(1)2，令()0，求得01/2；第二步迭代：12x(1)x(0)0d(0)1 101，f(x(1)2，s(0)x(1)x(0)1022y(0)1 f(x(1)f(x(0)2110001/213/21B10112120111 B1f(x(1)2，()f(x(1)d(1)，令()0，求得1 2。故14d(1)x(2)x(1)1d(1)00(2)(2)0，故x为最优解。0，由于f(x)k0123.解解：取初始可行点xx(k)(1,1)T(1,1/2)T(0,0)Tf(x(k)(0,1)T(1/2,0)Td(k)(0,1)T(1/2,1/4)Tk1/22(0)(0,0),A0 A(x(0)2,3.求解等式约束子问题2mind12d22d14d2s.t d1 0,d2 0得解和相应的 Lagrange 乘子d(0)(0,0)T,(2,4)T故得x(1)x(0)(0,0)T,A1 A032转入第二次迭代。求解等式约束子问题得解2mind12d22d14d2s.t d1 0d(1)(0,2)T 0计算biaiTx(1)b1a1Tx(1)1T(1)1 min1,T(1)i 1,3,aid 0T(1)aidaid2令x(2)x(1)1d(1)(0,1)T,A2 A111,2转入第三次迭代。求解等式约束子问题2mind12d22d12d2s.t d1d2 0,d1 0得解和相应的 Lagrange 乘子d(2)(0,0)T,(2,0)T由于(2)0，故得所求二次规划问题的最优解为(2)x x相应的 Lagrange 乘子为4.解：计算梯度得(0,1)T，(2,0,0)Tf(x)(2x1 x2 2,2x2 x1)T当k 0时，x(0)(0,0)，f(x)(2,0)T.y(0)是下面线性规划问题的解：minf(x(0)y 2y1s.t.3y1 y2 3y1 0,y2 0.解此线性规划（作图法）得y索(0)(2/3,0)T，于是d(0)y(0)x(0)(2/3,0)T.由线性搜min f(x(0)td(0)0t1224t t93得t01.因此，x(1)x(0)t0d(0)(2/3,0)T.重复以上计算过程得下表：k012x(k)(0,0)T(2/3,0)Tf(x(k)(2,0)Ty(k)(2/3,0)Td(k)(2/3,0)T(2/3,2)Ttk1(2/3,2/3)T(0,2)T125(162T,)25 25