第8讲 无约束问题求解(2)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,无约束极值问题算法（,1,）,（,2,学时）,无约束极值问题算法（,2,）,（,2,学时）,第,4,章 无约束极值问题,共轭梯度法,（,1,学时）,步长加速法,（,1,学时）,第,7,讲 无约束极值问题算法（,2,）,重 点：共轭梯度法、模式搜索法。,难 点：共轭方向的构造。,基本要求：理解共轭方向的定义及性质，掌握共轭梯度法的搜索,方向的构造过程，计算步骤，了解共轭梯度法的优缺点；了解模,式搜索法的基本思想和计算步骤。,首先考虑,二次函数,的无约束极小问题,共轭梯度法,令,将,(1),化为,显然，（,3,）式经,n,次一维搜索可得最优解,为对角阵,1,定义：设 为,n,阶正定阵，若,n,维方向 满足,（一）共轭方向,则称 是 共轭的。,2,性质：设 为,n,阶正定阵，若 是 共轭的，则必线性无关,1,共轭梯度法思想：,将共轭性与最速下降方法结合，利用已知点处的梯度构造一组共轭方向，并沿此组方向进行搜索，求出极小点。,适用范围：凸函数,（二）共轭梯度法,2 FR,共轭梯度法,考虑问题：,其中： 为对称正定阵,（,1,）算法步骤：,步骤,1,任选初始点 令,步骤,2,若 ，则停止；否则转下一步,令,其中：,步骤,5,置,k=k+1,返回步骤,2,步骤,3,步骤,4,定理,设向量 为 共轭，则从点 出发，相继以 为搜索方向的下述算法：,经,n,次一维搜索收敛于问题（,I,）的极小点,FR,共轭梯度法的理论推导*,问题,(I),证明：由式,(1),得,则有,由于一维搜索时 为最佳步长，故,即：,2 FR,公式推导,证明,(1),式：,由于一维搜索时 为最佳步长，故,证明,(2),式：,(i),(ii),设,k=m-1,时,(2),式成立,，,(iii) k=m,T,用,FR,共轭梯度法求解,（,2,）算法举例,解：,第一次迭代,第二次迭代,共轭搜索方向：,例,2,用共轭梯度法求解下列问题：,第,一,次,迭,代,第二次迭代,非二次型的共轭梯度法,设,为某一严格凸函数， 具有二阶连续偏导,用二阶泰勒展开近似表示,迭代公式：,（三）共轭梯度法的优缺点,优点,（,1,）,程序简单，占内存少；,（,2,）,收敛速度较快，介于梯度法和牛顿法之间。,缺点,（,1,）当 较小时计算 可能带来较大的,舍入误差，甚至引起不稳定；,（,2,）不进行“,n,步重新开始”一直作下去，收敛很,慢，甚至不收敛。,适用场合,各种问题，对于高维问题效果尤佳。,模式搜索法（步长加速法）,探测移动：,依次沿,n,个坐标轴进行，用于确定新的基,点和有利于函数值下降的方向。,模式移动：,沿相邻两个基点连线方向进行，试图,使函数值更快减少。,（一）模式搜索法的思路,探测性搜索：,模式搜索,（二）,模式搜索法的,迭代步骤,例,3,用步长加速法求解下列问题：,优点,(1),编制程序比较简单,(2),对函数的要求宽松,不需函数的导数信息。,缺点,收敛速度比较慢，,适用场合,对变量不多的问题可以使用，另外，还可用于求解非线,性目标规划问题。,（三）模式搜索法的优缺点,作业：习题,4 3,（,1,），,5,，,6,（选做）,