1、最优化方法复习题一、 简述题1、怎样判断一个函数是否为凸函数.（例如: 判断函数 是否为凸函数）21212 50)( xxxf 2、写出几种迭代的收敛条件.3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大 M 法及二阶段法）. 见书本 61 页(利用单纯形表求解);69 页例题 (利用大 M 法求解、二阶段法求解); 4、简述牛顿法和拟牛顿法的优缺点.简述共轭梯度法的基本思想.写出 Goldstein、Wolfe 非精确一维线性搜索的公式。5、叙述常用优化算法的迭代公式（1）0.618 法的迭代公式： (1),.kkaba（2）Fibonacci 法的迭代公式： 11(),(12,)nk
2、kkkkknFnaba（3）Newton 一维搜索法的迭代公式： kkxGg（4）推导最速下降法用于问题 的迭代公式：mi()2Tfbxc1()kk kTgxf（5）Newton 法的迭代公式： 211kkkfxf（6）共轭方向法用于问题 的迭代公式：min()TfxQbc1)kk kTfd二、计算题双折线法练习题 课本 135 页 例 3.9.1FR 共轭梯度法例题：课本 150 页 例 4.3.5二次规划有效集：课本 213 页例 6.3.2, 所有留过的课后习题.三、练习题： 1、设 是对称矩阵， ，求 在任意点nAR,nbRc1()2TfxAbxc处的梯度和 Hesse 矩阵x解 2(
3、),()fxfA2、设 ，其中 二阶可导， ，试求ttd:nR,nxRdt()解 2(),()()TTtfxttdfxt 3、证明：凸规划 的任意局部最优解必是全局最优解minxSf证明 用反证法设 为凸规划问题 的局部最优解，即存在 的某min()xSf x个 邻域 ，使 若 不是全局最优解，则存在()Nx(),ffxN，使 由于 为 上的凸函数，因此xSf()，有(0,1)(1)()1()fxfxfx当 充分接近 1 时，可使 ，于是 ，(NS(1)fx矛盾从而 是全局最优解x4、已知线性规划：123123123min();.60,.fxxstx（1）用单纯形法求解该线性规划问题；（2）写
4、出线性规划的对偶问题；解 （1）引进变量 ，将给定的线性规划问题化为标准形式：456,x12312345612min();. 0,.fxxstx所给问题的最优解为 ，最优值为 (0,)T20f（2）所给问题的对偶问题为：123123123max()6;.,0.gyysty5、用 0.618 法求解 ，要求缩短后的区间长度不超过 0.2，初2min()t始区间取 0,解 第一次迭代：取 1,.2ab确定最初试探点 分别为1,， 10.38()3.8a110.68()6.8aba求目标函数值： ， 21(.).72.310.比较目标函数值： 1)比较 16.80.2a第二次迭代：21212121,
5、.,3.8,()0.67b20.38()0(6.6,(3).4aa222(),.第三次迭代：323232320,.8,.6,()0.4ab23.()0(14(163).7a33(),.第四次迭代：434343431.6,.82,.6,()0.4ab0()160.821.98,().67a 444(),.第五次迭代：545454542.36,.82,.918,()0.67ab01()36()06a555(),.第六次迭代：656565652.3,3.2,2.918,()0.67ab08()704()07a666(),.第七次迭代：767676762.045,3.2,2.918,()0.7ab18
6、()049()0a777(),第八次迭代：878787872.91,3.26,3.049,()0.2ab06()1()1a888(),第九次迭代：98989982.1,3.1,3.04,()0.2ab03()2()1a999(),.04.8故 .2x6、用最速下降法求解 ,取 ,迭代22112min()43fxxx(0)1T两次解 ，1212()4,3)Tfx将 写成 的形式，则 fTfxGb24,3Qb第一次迭代： (0)(0)(1)(0) (0)Tfxfxfx(,3)1201/4,4第二次迭代： (1)(1)(2)(1) (1)TfxfxfxG3/2(/,0)/7/41/40132,47、
7、用 FR 共轭梯度法求解 ，取 ，迭222131313min()()()fxxxx(0),1)2Tx代两次若给定 判定是否还需进行迭代计算0.,解 ，22131232()()fxxx再写成 ， ， 1()2TfxG62()fxG第一次迭代：，令 ，(0),4)Tfx(0)0,4)Tdfx从 出发，沿 进行一维搜索，即求 的最优()0 (0 2min21648fxd解，得(1)(0)0/6,(1/2,3/)Txd第一次迭代： ，(1)4/3,0)Tfx2(1)009fx(1)10(4/3,8/)Tdfd从 出发，沿 进行一维搜索，即求()x1(1)0 1423648148min(,)223939
8、1423fxd 的最优解，得(2)(1)1/24/33, 89(0,)8/Txd此时(2) (2)0,)0.1Tfxfx得问题的最优解为 ，无需再进行迭代计算,8、求解问题 （方法不限定）取初始点 .211212min50.304,fxxxstx0,5T9、采用精确搜索的 BFGS 算法求解下面的无约束问题： 2121)(minxxf解：取 Tx)1,()0IB0 12f第一步迭代：，1)(0xf 0)(10)(xfd，令 ，求得 ；2)()0(f 0)(2/10第二步迭代：， ，21)0()0()1(dx021)(xf 21)0()1()(xs1)()(01)0( xffy 21/32/01
9、1B， ，令 ，求得 。)1(d41)(1xf )()1()dxf0)(21故 ，由于 ，故 为最优解。0)1()1()2(dx0)(2xf)2(x10、用有效集法求解下面的二次规划问题： .0,1. 4)(min21 212xtsf解：取初始可行点 求解等式约束子问题(0) (0)0,2,3.xAx211min4.,ddst得解和相应的 Lagrange 乘子(0)(1)(0)10,(2,),32TTxA故 得转入第二次迭代。求解等式约束子问题2112min4.0ddst得解 (1) (1) (1)(1)1,2min,302T TTi iT ibaxbaxiaddd计 算令(2)(1)(1)
10、210,TxA转入第三次迭代。求解等式约束子问题2112min.,ddst得解和相应的 Lagrange 乘子(2)0,(,0)TTd由于 ，故得所求二次规划问题的最优解为(2)0，(2)0,1Tx相应的 Lagrange 乘子为(,)T最速下降法的优缺点：优点：方法简单，计算量较小；最速下降法为全局收敛，对初始点的要求很少。缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最速下降法的最速下降仅是一种局部性质，即从局部来看目标函数的值下降得最快，但从总体来看它可能走了许多弯路。牛顿法的优缺点：优点：牛顿法的收敛速度快，为二阶收敛；公式简
11、单，计算方便。缺点：牛顿法要求 f(x)二阶可微，迭代中需多次计算；牛顿法具有局部收敛性，对初始点的要求比较苛刻。共轭梯度法的优缺点：优点：计算公式简单，存储量较小，对初始点要求很少，对二次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之间，对高维（n 较大）的非线性函数具有较高的效率。对于二次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：共轭梯度法的收敛性依赖于精确的一维搜索，计算量较大；共轭梯度法的一些理论背景至今尚不清楚，如周期性的重新开始，初始搜索放心的选取，一维搜索的精确性等，对共轭梯度法执行的影响仍有待进一步研究。拟牛顿法的优缺点：优点：拟牛顿法具有较快的收敛速度（是超线性的） ；对于二次函数具有二次终止性，一般情况下优于共轭梯度法。缺点：拟牛顿法需要的存储量较大，对大型计算不便；DFP 法远不如 BFGS 法数值稳定性好，BFGS 法具有较强的数值计算稳定性。
