最优化方法知识题一

1、习题一2 2、考虑二次函数 f(x)= Xi2XlX2 3X2XiX21 TT1) 写出它的矩阵一向量形式：f(X)= - x Qx b x2) 矩阵Q是不是奇异的？3)证明：f(x)是正定的4)f(x)是凸的吗？5)写出f(x)在点x =(2,i)处的支撑超平面(即切平面)方程解:1) f(x)=2Xi2XiX223X2Xi X22)3)4)其中因为XiX2x=XiX22Q=2因为|2|>0,Xi +X2,Q=所以|Q|=XiX2i,b=i=8>0 即可知Q是非奇异的=8>0 ,所以Q是正定的,故f(x)是正定的f(x)= 2226，所以12 2f (X) |=8>0

2、,故推出 f (X)是正定的，即f(x)是凸的5)因为f(x)= (2xi2x2-i,2xi6x2Ti)，所以f(x) =(5,ii)所以f(x)在点X处的切线方程为5(Xi2)+ii(X2 i)=0求下列函数的梯度问题和Hesse矩阵2i) f(x)=2 Xi + XiX29Xi X323X2 +X2X32X2解：1) f (x) = ( 4%X29X3,Xi6X2 X32，9X1X2)2 rf(x)= 192) f (x)=(X12X12X2X1 2X2XX2Xi2X1XX22 )Xi2 rf (X)=2三、设 f(x)= X13X2是f(x)在点X2X2 22Xi2X1X22(x2 X1

3、X2 X2)2 2X14 X1 X2 X22X1(x2 X1X22X12 X1X24X1X22X22X2)2£x£_X1X2 X2)22X32X2X3 X2(1)处的一个下降方向，并计算(X12X3，取点minf( t 0X1X2 X2)(1)X +tT(1)(1,1,1).验证 d(1,0,-1)(1)d )证明：f(x)= (2 x1,3x2 2X3 1,4X3 2x2 介Tf(X1)(2,4,5)2d f(X1) =(1,0,-1)4 = -3<05(1) (1)所以d 是f(x)在x 处的一个下降方向(1) (1)f( x +t d )=f(1+t,1,1-t

4、)222=(1 t) 12(1 t) 2(1 t) 1 (1 t) 3t 3t 4(1)(1)f( x +t d )=6t-3=0 所以 t=0.5>0min(1)(1)所以 f( +t )=3*0.25-3*0.5+4=3.25t 0四、设aj ，b ， Cj( j=1,2,)考虑问题Minf(x)=n Cj j 1 Xjs.t.nj GiXjbXj 0(j=1,2,.,n)1) 写出其Kuhn Tuker 条件2）证明问题最优值是1b n 1(ajCj)2解：1 ）因Xj（j 1,.,n）为目标函数的分母故 Xj0所以 j （j=1,n）都为0所以Kuhn Tuker 条件为 f (

5、x)h(x) 0C12X1C22X2a1a2 =0Cn2Xn3n2）将 XjCj代入ajh（x）=0 只有一点najCjb1n故有Xj.ajCj j 1b所以最优解是 丄n ()2b j 1(ajCj)2五、使用Kuhn Tuker 条件，求问题22min f(x)= (x1 1) (x2 2)x2 x1 1s.t.x1 x2 2x1 0,x2 0的 Kuhn Tuker 点，并验证此点为问题的最优解解： x=(1/2,3/2)0 故 1 ， 2=0则 f (x)1 h1(x)2h2(x) 0即2x1 211102x2 41210,112220T2而2 f (x)02故 x f (x)x 8

6、0即其为最优解六、在习题五的条件下证明L( x , , )L(x,)L(x,)其中 L(x, ,)=f(x)+(x2x1 1)(x1 x22)证明： L( xJJ)=f(x )+(x2x1 1)(x1 x22)= f(x)= f(x )+(x2 x1 1)+ (x1x2 2)=L(x= f(x)f(x)f (x)(x2x1 1)(x1 x22)=L(x, , )习题二、设 f(x) 为定义在区间 a,b 上的实值函数， x 是问题 minf(x)|a x b 的最优解。证明：f(x)是a,b上的单谷函数的充要条件是对任意Xi，X2a,b，XiX2满足 f(x1(1)x2 )<maxf(

7、x1),f( x2),(0,1)证明：不妨设 X1< X2 , 则X1<X1(1) X2X2“必要性”若 X1(1)X2X则由单谷函数定义知f(X1(1)X2)f (X1)故有 f( X1 (1) X2) maXf (X1), f(X2)"充分性”由X-I, x2的任意性取 X-I = X时，f( x2)>f( Xi)则 X2>X1(1)X2>X1=X 且 f(X1(1)X2)<f(X2)若取 X2= X 时, f( X1 )>f( X2)X=X1<X1(1)X2<X2且 f(X1(1)X2)<f(X1)满足单谷函数的定义、

8、设 X1< X2 , f (X1) 0, f (X2) 01）证明：满足条件（X1）f（X1）,（X1）f（X1）,（x2）f （x2）的二次函数（x）是（严格）凸函数2 ）证明：由二次插值所得f（x）的近似极小值点（即（x）的驻点）是(X2 X1)f(X2)X f (X2) f (X1)或者（X2 X1）f（X1）X1 f（X2）f（X1）2 ,证明：1 )设(x)=ax bx c ( a 0)(x)2ax（X1）（X2）2aX12aX2f(X2) f(X1)0,bX1（f（X2）f（X1）2(X2X1)(X2 X1)f (X2)X2(f(X2)f(X1)(X2X1)故1）得证2）（x

9、）的驻点为2aX2X1（X2 X1）f（X1） f（X2）f（X1）X1)f(X2) f (X2)(X2f（X1）设 f(x)= 1XTQx bTx c,QT0试证：共轭梯度法的线性搜索中(k)丄(k)、mii0n f(xtd )(k)f(xtkd(k，有tkT (k) 其中 T(d(k) Qd(k)(k)gk f(x)证明：由已知，得 f(x) Qx b令(t)f(x(k)丄 (k)td)为t的凸二次函数。要使点，故满足(tk)0(k ).(k)、(k)而(tk)f (xtd)d=Q(<(k)td(k) bTd(k)tk是(t)的极小点即为驻= Qx(k) b tQd(k)fd(k)=

10、 gTd(k)t(d(k)TQd(k)T ( k)心 T(k)故有 gkd tk(d(k)Qd 0得tkT(k)gkd (d(k)TQd(k)四、用共轭梯度法求解：3 21 2 2min f(x)= -xi2X2 X1X2 2x，x R(1) xT取初始点x(2,4)解：易知312Ab1 10第一次迭代：f(x)(3x1TX2 2,X2 X1)g1f(X1)(1) 、df(x)T(12, 6)线性搜索得步长T(12,6)T (1)T (1)12(12,6) 6(d(1) Ad(12, 6)1 1217从而x(2)x1d26第二次迭代:Tf(x(2)(§咚)(17,17)T n(1)g

11、2Ad(d(1)TAd(1)1738g2T(驚)29890g21d289210289线性搜索得步长:1.7(3)x(2)x(2)2dg3f(x ) (0,0)所以最优解为xT(1,1)五、用拟Newton 法求解:min2f (x)X122X2 2XX224川R取初始点(1) Tx()(1,1)解: 1) DFC取初始对称矩阵H1第一次迭代:T计算得gi ( 4,2)，TdiHigi (4, 2)经一维线性搜索得：1 =0.25X2XiidiT(2,0.25)yig2(1,(3,T0.5)T4)i, 2)T1 yi Tyi Hiyi0.20.2HiHi0.2H2yiT1 yiTHyyi Hi0

12、.7280.204ylHiYi0.7040.472第二次迭代d2T2g2(°.32,0.24)经一维线性搜索得:=6.25X3X22d 2T(4,2)g3T(0,0)故最优解为：xX3T(4,2)取定初始对称矩阵Hi第一次迭代:T计算得gi ( 4,2)，TdiHigi (4, 2)经一维线性搜索得：1 =0.25TX2 xiidi (2,0.25)0.2 0同DFP法，初始修正矩阵Hi 00.2H2HiTyi H i yiTTT(ii i Hiyii iyiHiiyiTi yi0.360.020.020.i4第二次迭代:Td2 H2g2 (0.4,0.3)经一维线性搜索得：2 5T

13、X3 X22d 2 (4,2)Tg3(0,0)*T故最优解为：x1、给定问题习题二2 2minf(x)Xi X1X2 2X2 6Xi 14X2XX2X32st.Xi2X2 3Xi0，X20, X30(1)T取初始点X，用简约梯度法求其最优解XiX2X32解：约束条件为X12x23Xi°X °，X30(1) T则 x()(1,1,0)，A111012 0 1f(x)(2xi X2 6Xi 4x2 14T0 0)Tgi 39 0 0Ii 12X fBN1N3 91-31-3N d NB(dT1Xo 鋼d4- 3XI74一 3仪o24一 364一 921口1maxmi n4得21

14、min ,max-(2)(1)(1)15Txx1d(-0 0)3311Tg27003得981-31-311一 3712A oN43一 9101 9N d NB(2)d 0T,(2)故x(<1500)为问题的K-T点'332、用梯度投影法求解问题22mins.t.(1)取初始点xf(x)(対2"叹0X2 4T1XiXi02)3(X23)解： f (x)(2xi 4,2x2迭代(1) g1 (10,6)T4)1TAi2投影矩阵P I3TTAi(AiAi)1Ai2136§1341313Pg1(1)f(x66 44、荷亦）66(1)d)(3132) (144133)1

15、088131321339故(2)X1d134444(|0)g2 (7,T6)I21,3投影矩阵TtA2(A2A2)a(2)dPg2T(0,0)(2)令uT 1(A2A2) A2g2(2,9)故x(2)(3，0)为其K-T占八、3、用可行方向法求解问题2 2min f(x) (x1 2) (x2 1)2X1 4X27st.2X1 X2 2X1 0X 0(1)T取初始点 xT解：f(x)(2x14,2x22)(1) t迭代一：f(x ) ( 4, 2)3,4确定下降方向min -4d12d2i=1,2d1S.t. J?di1解得d1d21且其最优值为-6，即处的搜索方向d（i）T(1,1)线性搜索f(x(i)、d )32maxmin 7,26 f3 7X7min 2,66(2)x1d迭代f（x）（(7 7)(6,6)T51)3,3)11确定下降方向5min -31d1 3d2s.t. 2d14d2 0 i=1,2di得 d (1,1)且其最优值为-2线性搜索(2)f(x(2)1318max518.,57 min , 18 6 mi nJ,©2 18 18(3)x(2) (2)