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

1、一、填空题( 寸2 1Y x1若 f =1 5 2，则 Vf (x)=v 2 f 3)二 设f连续可微且Vf (x)丰0,若向量d满足，则它是f在x处的一个下降方向。向量(1,2,3)t关于3阶单位方阵的所有线性无关的共轭向量有6.以下约束优化问题：min f (x) = xs.t. h(x) = x - x2 +1 = 0g (x) = x - x 0的K-K-T条件为：.7.以下约束优化问题：min f (x) = x2 + x2 s.t. x + x = 1设f : Rn T R二次可微，则f在x处的牛顿方向为 举出一个具有二次终止性的无约束二次规划算法:.的外点罚函数为(取罚参数为R

2、) 、证明题(7分+8分)1设g ： R R,/ = 1，2,气和h.:肱TR，i = m +1，m都是线性函数，证明下 面的约束问题：min f (x) = W x 2k=1s.t. g (x) 0,h (x) = 0,i e I = 1,m j e E = m +1,m是凸规划问题。2.设f : R2 T R连续可微，a e Rn，e R，i = 1,2,m，考察如下的约束条件问题:min f (x)s.t. aTx - b 0, i e I = 1,2 m a Tx - b = 0, i e E = m +1,m设d是问题min Vf (x) t ds.t. aTd 0, i e IaT

3、d = 0, i e EIId ll 0 x 0,x 0.用可行方向算法(Zoutendijk算法或Frank Wolfe算法)求解下面的问题(初值设 为x(0) = (0,0),计算到x(2)即可):min f (x) = 2 x2 - x x + x2 - 2xst. 3x + x 0,x 0.参考答案一、填空题 TOC o 1-5 h z (Ax +2x +1)f42)i 2,2x + 4x + 3 )(24 ,127V7Vf(x)rd 0(2,-l,0)r , (3,0,-l)r (答案不唯一)。4. -V2f(x)-iVf(x)牛顿法、修正牛顿法等(写出一个即可)6.V L(x,X,

4、 MO =Xfl-X + 2|Ux )1X 尤2 +1 = 0 TOC o 1-5 h z 21X 0,x -x 2 0,人(尤-x ) = 012127. F (x) = x2+x2+ pi(x +x -1)2 |112212二、证明题1.证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。一方面，由于f二次连续可微，V2f(x) = 27正定，根据凸函数等价条件可知目标函 数是凸函数。另一方面，约束条件均为线性函数，若任意可行域，则g (ou + (l a)y)=0Cg + (1 oc)g (j)0 iel iiih (cu + (l-oc)j) = ah (x) + (l-oc)/

5、z (j) = 0 i e E jjj故ocx + (l-oc)y e D ,从而可行域是凸集。2.证明：要证d是了在X处的一个可行方向，即证当xgD, d&Rn时，士 0,使得 x + ad e D , oc e (0,5当 i e I 时，aTx-b 0 , aTd 0,故 (x + oui) =aTx-b +CLa Td0 ;i iiii i i i当 i e E 时，a Tx-b = 0 , aTd = 0 ,故 (x + oui) -Z? =aTx-b +QLaTd = 0.因此，d是了在x处的一个可行方向。三、计算题1.解： 她)=f (x + ad)=(气 +ad 1)2 + 2

6、(x2 +ad2)2令（以）=0得a =d x +2d xd2 + 2d 22；Vf (x)=第一次迭代:Vf (x (0)=令(a) = 0，求得a 0 = 5/18 ；,、(-2) ,、,d (0) = -Vf (x (0) =, (a) = f (x (0) +ad (0),I- 4 7第二次迭代：xd) = x(0) +a 0d(0)(4（8、(8)91，Vf (x (1)=92，d =-Vf (x (1)=92-6I 9 7i- 9 19 7 (a) = f (x +ad )，令 (a) = 0 ,求得 a 1 = 1/2 ,故 x (2)=,(0 ) x(1) +a d=101口7

7、.(0)于Vf (x (2)=，故x (2)为最优解。10 7kx (k)Vf (x (k)d (k)ak0(1,1)丁(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.解：取折）=g B0 = ,(I 2 x12 x 2 x1 7第一步迭代：I0 7v7Vf (x)=Vf (x (0)=d (0) =- B0-1Vf (x (0)=(以)=f (x (0)+ad (0) = 2 + (1 一以)2 +以，令 (以)=0,求得 a 0 = 1/2 ；第二步迭代:f1 )f 1)f 0 )x=x(0) +a

8、 d(0)=01，Vf (x (1)=2，s (0) = x 一 x(0)=1k 2 J0 U J-3 k 2 Jy (0) = Vf (x )一Yf (x (0)=d =一 B：Vf (x(i)=f 1 2-14) (a) = f (x +ad ),令(a) = 0，求得a i = 2。故1000+1/2-=3/2-_01_01-12 _-12 _B =i一、f 0)由于Vf (x)=，故x为最优解。k 0 ),f 0 ) x(2) = x(1) +a d=10kx (k)Vf (x (k)d (k)ak0(1,1)T(0,1) T(0,-1) T1/21(1,1/2) T(1/2,0) T

9、(-1/2,-1/4) t22(0,0) T3.解：取初始可行点x(0) = (0,0), A0 = A(x(0) = 2,3.求解等式约束子问题min d2 + d2 - 2d -4ds.t d = 0, d = 0得解和相应的Lagrange乘子d (0) = (0,0) t ,人=(-2, -4)t故得x=x(0) = (0,0) t , A1 = A。3 = 2转入第二次迭代。求解等式约束子问题min d 2 + d 2 - 2d - 4ds.t d 0得解d(0,2) t。0计算b -工. 1 c 一八】b - QED 1 a. nin 1,-1I 1,3,aTd 0，故得所求二次规划问题的最优解为X* X=(0,1)t，相应的Lagrange乘子为人 * (2,0,0) t4.解：计算梯度得Vf (X) = (2x - X - 2,2x - x )t当k 0时，X(0) (0,0)，Vf (X) = (-2,0)t . y(0)是下面线性规划问题的解：min Vf ( x (0) y -2 yis.t. 3y + y 0,y2 0.解此线性规划(作图法)得y(0) (2/3,0)T，于是d(0) y(0) - X(0) (2/3,0)t .由线性搜索2t 2 -9min f (x(0)+ td(0)=0t 1得10 = 1.