《最优化方法》复习题.docVIP

《最优化方法》复习题 简述题 1、怎样判断一个函数是否为凸函数. （例如: 判断函数是否为凸函数） 2、写出几种迭代的收敛条件. 3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）. 见书本61页(利用单纯形表求解); 69页例题 (利用大M法求解、二阶段法求解); 4、简述牛顿法和拟牛顿法的优缺点. 简述共轭梯度法的基本思想. 写出Goldstein、Wolfe非精确一维线性有哪些信誉好的足球投注网站的公式。 5、叙述常用优化算法的迭代公式． （1）0.618法的迭代公式： （2）Fibonacci法的迭代公式：． （3）Newton一维有哪些信誉好的足球投注网站法的迭代公式： ． （4）推导最速下降法用于问题的迭代公式： （5）Newton法的迭代公式：． （6）共轭方向法用于问题的迭代公式： ． 二、计算题 双折线法练习题 课本135页 例3.9.1 FR共轭梯度法例题：课本150页 例4.3.5 二次规划有效集：课本213页例6.3.2, 所有留过的课后习题. 三、练习题： 1、设是对称矩阵，，求在任意点处的梯度和Hesse矩阵． 解 ． 2、设，其中二阶可导，，试求． 解 ． 3、证明：凸规划的任意局部最优解必是全局最优解． 证明 用反证法．设为凸规划问题的局部最优解，即存在的某个邻域，使．若不是全局最优解，则存在，使．由于为上的凸函数，因此 ，有 ． 当充分接近1时，可使，于是，矛盾．从而是全局最优解． 4、已知线性规划： （1）用单纯形法求解该线性规划问题； （2）写出线性规划的对偶问题； 解 （1）引进变量，将给定的线性规划问题化为标准形式： 所给问题的最优解为，最优值为． （2）所给问题的对偶问题为： 5、用0.618法求解 ，要求缩短后的区间长度不超过0.2，初始区间取． 解 第一次迭代： 取． 确定最初试探点分别为 ，． 求目标函数值：，． 比较目标函数值：． 比较． 第二次迭代： ． ． ． 第三次迭代： ． ． ． 第四次迭代： ． ． ． 第五次迭代： ． ． ． 第六次迭代： ． ． ． 第七次迭代： ． ． ． 第八次迭代： ． ． ． 第九次迭代： ． ． ． 故． 6、用最速下降法求解 ,取,迭代两次． 解　， 将写成的形式，则． 第一次迭代： ． 第二次迭代： ． 7、用FR共轭梯度法求解 ，取，迭代两次．若给定判定是否还需进行迭代计算． 解 ， 再写成，，． 第一次迭代： ，令， 从出发，沿进行一维有哪些信誉好的足球投注网站，即求的最优解，得 ． 第一次迭代： ．， ． 从出发，沿进行一维有哪些信誉好的足球投注网站，即求 的最优解，得 ． 此时 ． 得问题的最优解为，无需再进行迭代计算． 8、求解问题 （方法不限定） 取初始点. 9、采用精确有哪些信誉好的足球投注网站的BFGS算法求解下面的无约束问题： 解：取 第一步迭代： ，，令，求得； 第二步迭代： ，， ，，令，求得。故，由于，故为最优解。 10、用有效集法求解下面的二次规划问题： 解：取初始可行点求解等式约束子问题 得解和相应的Lagrange乘子 转入第二次迭代。求解等式约束子问题 得解 令 转入第三次迭代。求解等式约束子问题 得解和相应的Lagrange乘子 由于，故得所求二次规划问题的最优解为 ， 相应的Lagrange乘子为 最速下降法的优缺点： 优点：方法简单，计算量较小；最速下降法为全局收敛，对初 始点的要求很少。 缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些 例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最 速下降法的最速下降仅是一种局部性质，即从局部来看目标函数 的值下降得最快，但从总体来看它可能走了许多弯路。 牛顿法的优缺点： 优点：牛顿法的收敛速度快，为二阶收敛；公式简单， 计算方便。 缺点：牛顿法要求f(x)二阶可微，迭代中需多次计算 ；牛顿法具有局部收敛性，对初始点的要求比较苛刻。 共轭梯度法的优缺点： 优点：计算公式简单，存储量较小，对初始点要求很少，对二 次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之 间，对高维（n 较大）的非线性函数具有较高的效率。对于二 次函数具有二次终止性，一般情况下优于共轭梯度法。 缺点：共轭梯度法的收敛性依赖于精确的一维有哪些信誉好的足球投注网站，计算量较 大；共轭梯度法的一些理论背