最优化方法复习题

1、?最优化方法?复习题一、简述题1、怎样判断一个函数是否为凸函数.(例如：判断函数f(x)X122x1X22x210X15x2是否为凸函数)2、写出几种迭代的收敛条件.3、熟练掌握利用单纯形表求解线性规划问题的方法(包括大 M 法及二阶段法)见书本 61 页(利用单纯形表求解)；69 页例题(利用大 M 法求解、二阶段法求解);4、简述牛顿法和拟牛顿法的优缺点.简述共腕梯度法的根本思想.写出 Goldstein、Wolfe 非精确一维线性搜索的公式.5、表达常用优化算法的迭代公式.(3)Newton 一维搜索法的迭代公式：xk1xkGgk.1T一 xGxbxc 的迭代公式:2word范文(1)0

2、.618 法的迭代公式:kak(1)(bka)kak(b(bkak).).(2)Fibonacci 法的迭代公式:akakFnk1Fnk1FnkFnk1(bkak),(k1,2,L,n1).ak)(4)推导最速下降法用于问题 minf(x)xk1xkTgkgkgkTGkgxkf(xk)(5)Newton 法的迭代公式:21xk1xkf(xk)f(xk).1TT-xQxbxc 的迭代公式:2f(xJTdjrTTT；dk,dkQdk双折线法练习题课本 135 页例 3.9.1FR 共腕梯度法例题：课本 150 页例 4.3.5二次规划有效集：课本 213 页例 6.3.2,所有留过的课后习题.三、

3、练习题：1 T1、设 AR 是对称矩阵,bRn,cR,求 f(x)-xTAxbTxc 在任意点x处的梯度和 Hesse 矩阵.解f(x)Axb,2f(x)A.2、设(t)f(xtd),其中f:RnR二阶可导,xRn,dRn,tR,试求(t).解(t)f(xtd)Td,(t)dT2f(xtd)d.3、证实：凸规划 minf(x)的任意局部最优解必是全局最优解.xS证实用反证法.设 xS 为凸规划问题 minf(x)的局部最优解,即存在 x 的某xS个邻域N(x),使f(x)f(x),xN(x)IS.假设 x 不是全局最优解,那么存在%S,使f(%f(x).由于f(x)为 S 上的凸函数,因此(0

4、,1),有f(x(1)%f(x)(1)f(x%f(x).当充分接近 1 时,可使x(1)%N(x)IS,于是f(x)f(x(1)%,矛盾.从而 x 是全局最优解.word范文minf(x)2x1x2x3;s.t3xix2x360,4、线性规划：xi2x22x310,x1x2x320,xi,x2,x30.(1)用单纯形法求解该线性规划问题；(6)共腕方向法用于问题 minf(x)XkiXk(2)写出线性规划的对偶问题;解(1)引进变量人,%6,将给定的线性规划问题化为标准形式:minf(x)2x1x2x3;s.t3x1x2x3x460,X2x22x3xs10,x2x3x20,X,x2,L,40.

5、所给问题的最优解为x(0,20,0)、最优值为f20.(2)所给问题的对偶问题为：maxg(y)60y110y220y3；s.t3y1y2y32,乂 2y2V31,y12y2y31,y1,y2,y30.5、用 0.618 法求解min(t3)2,要求缩短后的区间长度不超过 0.2,初始区间取0,10.解第一次迭代：取0,10,0.2.确定最初试探点1,1分别为1a10.382(b1a1)3.82,140.618(b1a1)6.18.求目标函数值：(I)(3.823)20.67,(I)(6.183)210.11.word范文比拟目标函数值：(1)(1).比拟iai6.1800.2第二次迭代:0,

6、b216.18,213.82,(2)(1)0.67.2a20.382(b2a2)0.382(6.180)2.36,_22)(2.363)(2)(2),2a23.82第三次迭代:a3a20,b323.82,322.36,(3)2)0.4.3a30.382(b3a3)0.382(3.820)1.46,3)_2(1.463)2.37.(3)(3,b33.821.46第四次迭代:a431.46,b4b33.82,432.36,(4)(3)4a40.618(b4a4)1.460.0.618(3.821.46)2.918,(4)0.0067.(4)(4),b43.822.36第五次迭代:a542.36,b

7、s3.82,542.918,(5)(4)0.0067.5a50.618(b5a5)3.262,(5)0.0686.(5)(5),5a53.2622.36第六次迭代:a6a52.36,b63.262,2.918,(6)(5)0.0067.6a60.382(b6a6)2.7045,(6)0.087.(6)(6),b63.2622.7045word范文第七次迭代:ay62.7045,byb7a70.618(0a7)(7)(7),b77第八次迭代：a872.918,b8b78a80.618(b8a8)(8)(8),8a8第九次迭代：a9a82.918,b989a90.382也a9)(9)(9),9a9

8、故 x-_93.024.26、用最速下降法求解次.解f(x)(2x12x21将f(x)与成f(x)一23.262,762.918,(7)3.049,(7)0.002.3.262,873.049,(8)3.131,(8)0.017.3.131,993.049,(9)2.999,(9)0.000001.3.0492.91822minf(x)x12x1x22x24x14,2为4x23)T,22TGxbTx的形式,贝UQ24(6)0.0067.(7)0.002.(8)0.002.3x2,取x(0)(1,1)T,迭代两4,b b3第一次迭代:x(1)x(0)xx(0)、T(0)f(X)f(x)f(0)了

9、/(0)、T/(叭f(x)f(x)Gf(x)word范文7、用 FR 共腕梯度法求解2/、2/minf(x)(xx2必)(xx2x3)(x1两次.假设给定0.01,判定是否还需进行迭代计算.解f(x)3(x；x212x32)2(x1x2x1x3*2x3),1T_再写成f(x)xTGx,G2第二次迭代:0(0,3)322(0,3)2411/4(2)(1)xx、Tf(x)f(x)T(1)f(x)Gf(x)f(x(1)11/4(3/2,0)3/20223/2(32403/207/41/4x2x3)2,取 x(0)11T( (- -,1,1,- -2),迭代622262,f(x)Gx.226第一次迭代

10、:从x出发,沿d0进行一维搜索,即求 minf(x(0)d0)216482的最优解,-(1)_Td1f(x()0d0(4/3,8/9,4/3).word范文f(x(0)(0,4,0)T,令4f(x(0)(0,4,0)T,第一次迭代:01/6,x(1)x(0)0d0(1/2,1/3,1/2)T.f(x(1)(4/3,0,4/3)T.IIf(x)2f(x(0)29从x(1)出发,沿di进行一维搜索,即求minf(x(1)di)(141814121312438943的最优解,此时1/2(1)x1d11/31/24/38/94/3(0,0,0)Tf(x(2)(0,0,0)T,f(x) )0.01得问题

11、的最优解为x(0,0,0)T,无需再进行迭代计算.8、求解问题(方法不限定)1212minfxx1x25x110 x222s.t2x3x230取初始点 0,5T.x14x220 x1,x209 9、采用精确搜索的 BFGSBFGS 算法求解下面的无约束问题：122minf(x)-x1x2x1x2解：取x(0)(1,1)TB0If(x)x1x22x2x1第一步迭代：f(x(0)0 0d(0)B.1f(x(0)0 0111o()f(x(0)d(0)2(1)2,令()0,求得.1/2；第二步迭代：word范文22mind1d22dl4d2s.td10,d20得解和相应的 LagrangeLagran

12、ge 乘子d(0)(0,0)T,(2,4)T故得x(1)x(0)(0,0)T,AAO32转入第二次迭代.求解等式约束子问题2,2mind1d22dl4d2std10得解x(0)110d(0)1,f(x(1)2,s(0)x(1)x(0)2 20 01y(0)f(x)f(x(0)2110001/21B10101123/2112d(1)B11f(x(1)12,()f(x(1)d(1),令()0,求得12.故14x x(2)x x(1)1 1d d0 0, ,由于f(xf(x) )0,0,故x为最优解.1010、用有效集法求解下面的二次规划问题：22cminf(x)x1x22x1st.x1x210 x

13、10,x20.4x2解：取初始可行点x(0)(0,0),A0A(x(0)2,3.求解等式约束子问题word范文d(1)(0,2)T0计算T(1)T(1)biax.TOT.(i)cibiaximin1,T-T(i1,3,ad0-T-T(aidd令xx(1)1d(0,1)T,A2AU11,2转入第三次迭代.求解等式约束子问题mind；d；2dl2d2s.td1d20,d10得解和相应的 LagrangeLagrange 乘子d(0,0)T,(2,0)T由于0,故得所求二次规划问题的最优解为x(0,1)二相应的 LagrangeLagrange 乘子为(2,0,0)T最速下降法的优缺点：优点：方法简

14、单,计算量较小；最速下降法为全局收敛,对初始点的要求很少.缺点：最速下降法的收敛速度与变量的尺度关系很大,对有些例子,在极小点附近产生显著的锯齿现象,收敛十分缓慢；最速下降法的最速下降仅是一种局部性质,即从局部来看目标函数的值下降得最快,但从总体来看它可能走了许多弯路.牛顿法的优缺点：优点：牛顿法的收敛速度快,为二阶收敛；公式简单,计算方便.word范文缺点：牛顿法要求 fx二阶可微,迭代中需屡次计算;牛顿法具有局部收敛性,对初始点的要求比拟苛刻.共腕梯度法的优缺点：优点：计算公式简单,存储量较小,对初始点要求很少,对二次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之问,对高维n 较大的非线性函数具有较高的效率.对于二次函数具有二次终止性,一般情况下优于共腕梯度法.缺点：共腕