《最优化方法》复习题

《最优化方法》复习题一、简述题1、怎样判断一个函数是否为凸函数.（例如:判断函数2122212151022)(xxxxxxxf是否为凸函数）2、写出几种迭代的收敛条件.3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.见书本61页(利用单纯形表求解);69页例题(利用大M法求解、二阶段法求解);4、简述牛顿法和拟牛顿法的优缺点.简述共轭梯度法的基本思想.写出Goldstein、Wolfe非精确一维线性搜索的公式。5、叙述常用优化算法的迭代公式．（1）0.618法的迭代公式：(1)(),().kkkkkkkkabaaba（2）Fibonacci法的迭代公式：111(),(1,2,,1)()nkkkkknknkkkkknkFabaFknFabaF．（3）Newton一维搜索法的迭代公式：11kkkkxxGg．（4）推导最速下降法用于问题1min()2TTfxxGxbxc的迭代公式：1()TkkkkkTkkkggxxfxgGgx（5）Newton法的迭代公式：211[()]()kkkkxxfxfx．（6）共轭方向法用于问题1min()2TTfxxQxbxc的迭代公式：1()TkkkkkTkkfxdxxddQd．二、计算题双折线法练习题课本135页例3.9.1FR共轭梯度法例题：课本150页例4.3.5二次规划有效集：课本213页例6.3.2,所有留过的课后习题.三、练习题：1、设nnAR是对称矩阵，,nbRcR，求1()2TTfxxAxbxc在任意点x处的梯度和Hesse矩阵．解2(),()fxAxbfxA．2、设()()tfxtd，其中:nfRR二阶可导，,,nnxRdRtR，试求()t．解2()(),()()TTtfxtddtdfxtdd．3、证明：凸规划min()xSfx的任意局部最优解必是全局最优解．证明用反证法．设xS为凸规划问题min()xSfx的局部最优解，即存在x的某个邻域()Nx，使()(),()fxfxxNxS．若x不是全局最优解，则存在xS，使()()fxfx．由于()fx为S上的凸函数，因此(0,1)，有((1))()(1)()()fxxfxfxfx．当充分接近1时，可使(1)()xxNxS，于是()((1))fxfxx，矛盾．从而x是全局最优解．4、已知线性规划：123123123123123min()2;..360,2210,20,,,0.fxxxxstxxxxxxxxxxxx（1）用单纯形法求解该线性规划问题；（2）写出线性规划的对偶问题；解（1）引进变量456,,xxx，将给定的线性规划问题化为标准形式：123123412351236126min()2;..360,2210,20,,,,0.fxxxxstxxxxxxxxxxxxxxx所给问题的最优解为(0,20,0)Tx，最优值为20f．（2）所给问题的对偶问题为：123123123123123max()601020;..32,21,21,,,0.gyyyystyyyyyyyyyyyy5、用0.618法求解2min()(3)tt，要求缩短后的区间长度不超过0.2，初始区间取[0,10]．解第一次迭代：取11[,][0,10],0.2ab．确定最初试探点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.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．第四次迭代：434343431.46,3.82,2.36,()()0.4abb．444440.618()1.460.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.618()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．故993.0242x．6、用最速下降法求解22112212min()2243fxxxxxxx,取(0)(1,1)Tx,迭代两次．解1212()(224,243)Tfxxxxx，将()fx写成1()2TTfxxGxbx的形式，则224,243Qb．第一次迭代：(0)(0)(1)(0)(0)(0)(0)()()()()()TTfxfxxxfxfxGfx0(0,3)1013220131/4(0,3)243．第二次迭代：(1)(1)(2)(1)(1)(1)(1)()()()()()TTfxfxxxfxfxGfx3/2(3/2,0)13/27/40223/21/401/4(3/2,0)240．7、用FR共轭梯度法求解222123123123min()()()()fxxxxxxxxxx，取(0)11(,1,)22Tx，迭代两次．若给定0.01,判定是否还需进行迭代计算．解222123121323()3()2()fxxxxxxxxxx，再写成1()2TfxxGx，622262226G，()fxGx．第一次迭代：(0)()(0,4,0)Tfx，令(0)0()(0,4,0)Tdfx，从(0)x出发，沿0d进行一维搜索，即求(0)200min()21648fxd的最优解，得(1)(0)0001/6,(1/2,1/3,1/2)Txxd．第一次迭代：(1)()(4/3,0,4/3)Tfx．2(1)02(0)()29()fxfx，(1)100()(4/3,8/9,4/3)Tdfxd．从(1)x出发，沿1d进行一维搜索，即求(1)10142362214181418min()(,,)262233923392261423fxd的最优解，得(2)(1)1111/24/333,1/38/9(0,0,0)881/24/3Txxd．此时(2)(2)()(0,0,0),()00.01Tfxfx．得问题的最优解为(0,0,0)Tx，无需再进行迭代计算．8、求解问题（方法不限定）22121212121211min51022..2330420,0fxxxxxstxxxxxx取初始点0,5T.9、采用精确搜索的BFGS算法求解下面的无约束问题：21222121)(minxxxxxf解：取Tx)1,1()0(IB012212)(xxxxxf第一步迭代：10)()0(xf10)()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(d4121)()1(11xfB，)()()1()1(dxf，令0)('，求得21。故00)1(1)1()2(dxx，由于00)()2(xf，故)2(x为最优解。10、用有效集法求解下面的二次规划问题：.0,001..42)(min2121212221xxxxtsxxxxxf解：取初始可行点(0)(0)0(0,0),(){2,3}.xAAx求解等式约束子问题22121212min24..0,0ddddstdd得解和相应的Lagrange乘子(0)(1)(0)10(0,0),(2,4)(0,0),\{3}{2}TTTdxxAA故得转入第二次迭代。求解等式约束子问题2212121min24..0ddddstd得解(1)(1)(1)(1)111(1)(1)(0,2)01min{1,1,3,0}2TTTTiiiTTiidbaxbaxiadadad计算令(2)(1)(1)121(0,1),{1}{1,2}TxxdAA转入第三次迭代。求解等式约束子问题221212121min22..0,0ddddstddd得解和相应的Lagrange乘子(2)(0,0),(2,0)TTd由于(2)0，故得所求二次规划问题的最优解为(2)(0,1)Txx，相应的Lagrange乘子为(2,0,0)T