2022年《最优化方法》复习题 .pdf

《2022年《最优化方法》复习题 .pdf》由会员分享，可在线阅读，更多相关《2022年《最优化方法》复习题 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化方法复习题一、简述题1、怎样判断一个函数是否为凸函数.（例如 : 判断函数2122212151022)(xxxxxxxf是否为凸函数）2、写出几种迭代的收敛条件.3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大 M 法及二阶段法） . 见书本 61 页(利用单纯形表求解 ); 69 页例题 (利用大 M 法求解、二阶段法求解 ); 4、简述牛顿法和拟牛顿法的优缺点. 简述共轭梯度法的基本思想. 写出 Goldstein、Wolfe 非精确一维线性搜索的公式。5、叙述常用优化算法的迭代公式（1）0.618 法的迭代公式：(1)(),().kkkkkkkkabaaba（2）Fibona

2、cci 法的迭代公式：111(),(1,2,1)()n kkkkkn kn kkkkkn kFabaFknFabaF（3）Newton一维搜索法的迭代公式：11kkkkxxGg（4）推导最速下降法用于问题1min( )2TTf xx Gxb xc的迭代公式：1()TkkkkkTkkkggxxf xgG gx（5）Newton法的迭代公式：211()()kkkkxxf xf x（6）共轭方向法用于问题1min( )2TTf xx Qxb xc的迭代公式：1()TkkkkkTkkf xdxxddQd二、计算题双折线法练习题课本 135 页 例 3.9.1 FR共轭梯度法例题：课本150 页 例 4

3、.3.5 二次规划有效集：课本213页例 6.3.2, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 所有留过的课后习题 . 三、练习题：1、设n nAR是对称矩阵，,nbRcR，求1( )2TTf xx Axb xc在任意点x处的梯度和 Hesse矩阵解2( ),( )f xAxbfxA2、 设()()tf x t d， 其中:nfRR二阶可导，,nnxRdRtR， 试求( ) t解2( )(),( )()TTtf xtdd

4、tdfxtd d3、证明：凸规划 min( )x Sf x 的任意局部最优解必是全局最优解证明用反证法设 xS为凸规划问题 min( )x Sf x 的局部最优解，即存在x 的某个邻域( )Nx，使( )( ),()fxf xxNxS若 x 不是全局最优解，则存在xS，使( )( )f xf x由于( )f x为 S上的凸函数，因此(0,1)，有(1) )( )(1)( )( )fxxf xf xf x当充分接近 1 时，可使(1)( )xxNxS，于是( )(1) )f xfxx，矛盾从而 x 是全局最优解4、已知线性规划：123123123123123min( )2;. 360,2210,

5、20,0.f xxxxstxxxxxxxxxx xx（1）用单纯形法求解该线性规划问题；（2）写出线性规划的对偶问题；解（1）引进变量456,xxx，将给定的线性规划问题化为标准形式：123123412351236126min( )2;. 360,2210,20,0.f xxxxstxxxxxxxxxxxxx xx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 所给问题的最优解为(0, 20,0)Tx，最优值为20f（2）所给问

6、题的对偶问题为：123123123123123max( )601020;.32,21,21,0.g yyyystyyyyyyyyyy yy5、用 0.618 法求解2min( )(3)tt，要求缩短后的区间长度不超过0.2，初始区间取0,10解第一次迭代：取11,0,10,0.2a b确定最初试探点11,分别为11110.382()3.82aba，11110.618()6.18aba求目标函数值：21()(3.823)0.67，21()(6.183)10.11比较目标函数值：11()()比较116.1800.2a第二次迭代：212121210,6.18,3.82,()()0.67aab2222

7、220.382()0.382(6.180)2.36,()(2.363)0.4aba2222()(),3.82a第三次迭代：323232320,3.82,2.36,()()0.4aab2333330.382()0.382(3.820)1.46,()(1.463)2.37aba3333()(),3.821.46b名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 第四次迭代：434343431.46,3.82,2.36,()()0.4a

8、bb444440.618()1.460.0.618(3.821.46)2.918,()0.0067aba4444()(),3.822.36b第五次迭代：545454542.36,3.82,2.918,()()0.0067abb555550.618()3.262,()0.0686aba5555()(),3.2622.36a第六次迭代：656565652.36,3.262,2.918,()()0.0067aab666660.382()2.7045,()0.087aba6666()(),3.2622.7045b第七次迭代：767676762.7045,3.262,2.918,()()0.0067ab

9、b777770.618()3.049,()0.002aba7777()(), b第八次迭代：878787872.918,3.262,3.049,()()0.002abb888880.618()3.131,()0.017aba8888()(),a第九次迭代：989899982.918,3.131,3.049,()()0.002aab999990.382()2.999,()0.000001aba9999()(),3.0492.918a名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页

10、，共 9 页 - - - - - - - - - 故993.0242x6、用最速下降法求解22112212min( )2243f xxx xxxx, 取(0)(1,1)Tx, 迭代两次解1212( )(224,243)Tf xxxxx，将( )f x写成1( )2TTf xx Gxb x的形式，则224,243Qb第一次迭代：(0)(0)(1)(0)(0)(0)(0)()()()()()TTf xfxxxf xf xGf x0(0,3)1013220131/ 4(0,3)243第二次迭代：(1)(1)(2)(1)(1)(1)(1)()()()()()TTf xfxxxf xf xGf x3/

11、2( 3/ 2,0)13/ 27 /40223/ 21/ 401/ 4( 3/ 2,0)2407、用 FR共轭梯度法求解222123123123min( )()()()f xxxxxxxxxx，取(0)11(,1, )22Tx，迭代两次若给定0.01,判定是否还需进行迭代计算解222123121323( )3()2()f xxxxx xx xx x，再写成1( )2Tf xx Gx，622262226G，( )fxGx第一次迭代：(0)()(0, 4,0)Tf x，令(0)0()(0,4,0)Tdf x，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

12、- - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 从(0)x出发，沿0d进行一维搜索，即求(0)200min()21648f xd的最优解，得(1)(0)0001/ 6,(1/2,1/ 3,1/ 2)Txxd第一次迭代：(1)()(4 / 3,0, 4 /3)Tf x2(1)02(0)()29()f xf x，(1)100()( 4 /3, 8/ 9, 4/ 3)Tdf xd从(1)x出发，沿1d进行一维搜索，即求(1)10142362214181418min()(,)262233923392261423f xd的最优

13、解，得(2)(1)1111/ 24 / 333,1/ 38 /9(0,0,0)881/ 24 / 3Txxd此时(2)(2)()(0,0,0) ,()00.01Tf xf x得问题的最优解为(0,0,0)Tx，无需再进行迭代计算8、求解问题（方法不限定）22121212121211min51022.2330420,0fxxxxxstxxxxx x取初始点 0,5T.9、采用精确搜索的BFGS算法求解下面的无约束问题：21222121)(minxxxxxf名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

14、 - - - 第 6 页，共 9 页 - - - - - - - - - 解：取Tx)1 , 1()0(IB012212)(xxxxxf第一步迭代：10)()0(xf10)()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(xxs121)()()0()1()0(xfxfy2112/32112/1100010011B)1(d4121)()1(11xfB，)()()1()1(dxf，令0)( ，求得21。故00)1(1)1()2(dxx，由于00)()2(xf，故)

15、2(x为最优解。10、用有效集法求解下面的二次规划问题：.0,001.42)(min2121212221xxxxtsxxxxxf解：取初始可行点(0)(0)0(0,0),()2,3.xAA x求解等式约束子问题22121212min24.0,0ddddst dd得解和相应的Lagrange 乘子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - (0)(1)(0)10(0,0) ,( 2, 4)(0,0),32TTTdxxAA故得转

16、入第二次迭代。求解等式约束子问题2212121min24.0ddddst d得解(1)(1)(1)(1)111(1)(1)(0,2)01min1,1,3,02TTTTiiiTTiidba xba xia da da d计算令(2)(1)(1)121(0,1) ,11,2TxxdAA转入第三次迭代。求解等式约束子问题221212121min22.0,0ddddst ddd得解和相应的Lagrange 乘子(2)(0,0) ,(2,0)TTd由于(2)0，故得所求二次规划问题的最优解为(2)(0,1)Txx，相应的 Lagrange 乘子为(2,0,0)T最速下降法的优缺点：优点：方法简单，计算量

17、较小；最速下降法为全局收敛，对初始点的要求很少。缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最速下降法的最速下降仅是一种局部性质，即从局部来看目标函数的值下降得最快，但从总体来看它可能走了许多弯路。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 牛顿法的优缺点：优点：牛顿法的收敛速度快，为二阶收敛；公式简单，计算方便。缺点：牛顿法要求f(x) 二阶可微，迭代中需多次计

18、算；牛顿法具有局部收敛性，对初始点的要求比较苛刻。共轭梯度法的优缺点：优点：计算公式简单，存储量较小，对初始点要求很少，对二次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之间，对高维（ n 较大）的非线性函数具有较高的效率。对于二次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：共轭梯度法的收敛性依赖于精确的一维搜索，计算量较大；共轭梯度法的一些理论背景至今尚不清楚，如周期性的重新开始，初始搜索放心的选取，一维搜索的精确性等，对共轭梯度法执行的影响仍有待进一步研究。拟牛顿法的优缺点：优点：拟牛顿法具有较快的收敛速度（是超线性的）；对于二次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：拟牛顿法需要的存储量较大，对大型计算不便；DFP法远不如 BFGS 法数值稳定性好， BFGS 法具有较强的数值计算稳定性。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -