《《最优化方法》复习题.pdf》由会员分享，可在线阅读，更多相关《《最优化方法》复习题.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.1/9 最优化方法复习题 一、简述题 1、怎样判断一个函数是否为凸函数.（例如:判断函数2122212151022)(xxxxxxxf是否为凸函数）2、写出几种迭代的收敛条件.3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M 法与二阶段法）.见书本61 页(利用单纯形表求解);69 页例题(利用大 M 法求解、二阶段法求解);4、简述牛顿法和拟牛顿法的优缺点.简述共轭梯度法的基本思想.写出 Goldstein、Wolfe 非精确一维线性搜索的公式。5、表达常用优化算法的迭代公式（1）0.618 法的迭代公式：(1)(),().kkkkkkkkabaaba（2）Fibonacci 法的
2、迭代公式：111(),(1,2,1)()n kkkkkn kn kkkkkn kFabaFknFabaF （3）Newton 一维搜索法的迭代公式：11kkkkxxG g（4）推导最速下降法用于问题1min()2TTf xx Gxb xc的迭代公式：1()TkkkkkTkkkggxxf xg G gx（5）Newton 法的迭代公式：211()()kkkkxxf xf x （6）共轭方向法用于问题1min()2TTf xx Qxb xc的迭代公式：1()TkkkkkTkkf xdxxdd Qd 二、计算题 双折线法练习题 课本 135 页 例 3.9.1 FR 共轭梯度法例题：课本 150 页
3、 例 4.3.5 二次规划有效集：课本 213 页例 6.3.2,.2/9 所有留过的课后习题.三、练习题：1、设n nAR是对称矩阵，,nbRcR，求1()2TTf xx Axb xc在任意点x处的梯度和 Hesse 矩阵 解 2(),()f xAxbf xA 2、设()()tf xtd，其中:nfRR二阶可导，,nnxRdR tR，试求()t 解 2()(),()()TTtf xtddtdf xtd d 3、证明：凸规划min()x Sf x的任意局部最优解必是全局最优解 证明 用反证法设xS为凸规划问题min()x Sf x的局部最优解，即存在x的某个邻域()Nx，使()(),()f x
4、f 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,20,0.f xxxxstxxxxxxxxxx x x（1）用单纯形法求解该线性规划问题；（2）写出线性规划的对偶问题；解 （1）引进变量456,xxx，将给定的线性规划问题化为标准形式：123123412351236126min()2;.360,22
5、10,20,0.f xxxxstxxxxxxxxxxxxx xx.3/9 所给问题的最优解为(0,20,0)Tx，最优值为20f （2）所给问题的对偶问题为：123123123123123max()601020;.32,21,21,0.g yyyystyyyyyyyyyy yy 5、用 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.1
6、83)10.11 比较目标函数值：11()()比较116.1800.2a 第二次迭代：212121210,6.18,3.82,()()0.67aab 2222220.382()0.382(6.180)2.36,()(2.363)0.4aba 2222()(),3.82a 第三次迭代：323232320,3.82,2.36,()()0.4aab 2333330.382()0.382(3.820)1.46,()(1.463)2.37aba 3333()(),3.821.46b .4/9 第四次迭代：434343431.46,3.82,2.36,()()0.4abb 444440.618()1.46
7、0.0.618(3.821.46)2.918,()0.0067aba 4444()(),3.822.36b 第五次迭代：545454542.36,3.82,2.918,()()0.0067abb 555550.618()3.262,()0.0686aba 5555()(),3.2622.36a 第六次迭代：656565652.36,3.262,2.918,()()0.0067aab 666660.382()2.7045,()0.087aba 6666()(),3.2622.7045b 第七次迭代：767676762.7045,3.262,2.918,()()0.0067abb 777770.6
8、18()3.049,()0.002aba 7777()(),b 第八次迭代：878787872.918,3.262,3.049,()()0.002abb 888880.618()3.131,()0.017aba 8888()(),a 第九次迭代：989899982.918,3.131,3.049,()()0.002aab 999990.382()2.999,()0.000001aba 9999()(),3.0492.918a .5/9 故993.0242x 6、用最速下降法求解 22112212min()2243f xxx xxxx,取(0)(1,1)Tx,迭代两次 解 1212()(224,
9、243)Tf xxxxx，将()f x写成1()2TTf xx Gxb x的形式，则224,243Qb 第一次迭代：(0)(0)(1)(0)(0)(0)(0)()()()()()TTf xf xxxf xf xG f x 0(0,3)1013220131/4(0,3)243 第二次迭代：(1)(1)(2)(1)(1)(1)(1)()()()()()TTf xf xxxf xf xG f x 3/2(3/2,0)13/27/40223/21/401/4(3/2,0)240 7、用FR共轭梯度法求解 222123123123min()()()()f xxxxxxxxxx，取(0)11(,1,)22
10、Tx，迭代两次若给定0.01,判定是否还需进行迭代计算 解 222123121 323()3()2()f xxxxx xx xx x，再写成1()2Tf xx Gx，622262226G，()f xGx 第一次迭代：(0)()(0,4,0)Tf x，令(0)0()(0,4,0)Tdf x，.6/9 从(0)x出发，沿0d进行一维搜索，即求(0)200min()2 1648f 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
11、 xd 从(1)x出发，沿1d进行一维搜索，即求(1)10142362214181418min()(,)262233923392261423f xd 的最优解，得(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,0f xxxxxstxxxxx x取初始点0,5T.9、采用精确搜索的 BFGS 算法求解下面的无约束问题：21222121)(minxxx
12、xxf.7/9 解：取Tx)1,1()0(IB 012212)(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(xxs 121)()()0()1()0(xfxfy 2112/32112/1100010011B)1(d4121)()1(11xfB，)()()1()1(dxf，令0)(，求得21。故00)1(1)1()2(dxx，由于00)()2(xf，故)2(x为最优解。10、用有效集法求解下面的二次规划问题：.
13、0,001.42)(min2121212221xxxxtsxxxxxf 解：取初始可行点(0)(0)0(0,0),()2,3.xAA x求解等式约束子问题 22121212min24.0,0ddddst dd 得解和相应的 Lagrange 乘子.8/9(0)(1)(0)10(0,0),(2,4)(0,0),32TTTdxxAA 故得 转入第二次迭代。求解等式约束子问题 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(
14、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 最速下降法的优缺点：优点：方法简单，计算量较小；最速下降法为全局收敛，对初 始点的要求很少。缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些 例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最 速下降法的最速下降仅是一种局部性质，即从局部来看目标函数 的值下降得最快，但从总
15、体来看它可能走了许多弯路。.9/9 牛顿法的优缺点：优点：牛顿法的收敛速度快，为二阶收敛；公式简单，计算方便。缺点：牛顿法要求 f(x)二阶可微，迭代中需多次计算；牛顿法具有局部收敛性，对初始点的要求比较苛刻。共轭梯度法的优缺点：优点：计算公式简单，存储量较小，对初始点要求很少，对二 次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之 间，对高维（n 较大）的非线性函数具有较高的效率。对于二 次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：共轭梯度法的收敛性依赖于精确的一维搜索，计算量较 大；共轭梯度法的一些理论背景至今尚不清楚，如周期性的重新 开始，初始搜索放心的选取，一维搜索的精确性等，对共轭梯度 法执行的影响仍有待进一步研究。拟牛顿法的优缺点：优点：拟牛顿法具有较快的收敛速度（是超线性的）；对于二次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：拟牛顿法需要的存储量较大，对大型计算不便；DFP 法 远不如 BFGS 法数值稳定性好，BFGS 法具有较强的数值计算 稳定性。