规划数学 第8讲 无约束问题求解ppt课件.ppt

《规划数学 第8讲 无约束问题求解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无约束极值问题算法（1）（2学时）无约束极值问题算法（2）（2学时）第4章无约束极值问题共轭梯度法（1学时）步长加速法（1学时）第7讲无约束极值问题算法（2）重点：共轭梯度法、模式搜索法。难点：共轭方向的构造。基本要求：理解共轭方向的定义及性质，掌握共轭梯度法的搜索方向的构造过程，计算步骤，了解共轭梯度法的优缺点；了解模式搜索法的基本思想和计算步骤。首先考虑二次函数的无约束极小问题共轭梯度法令将(1)化为显然，（3）式经n次一维搜索可得最优解为对角阵1定义：设为n阶正定阵，若n维方向满足（一）共轭方向则称

2、是共轭的。2性质：设为n阶正定阵，若是共轭的，则必线性无关1共轭梯度法思想：将共轭性与最速下降方法结合，利用已知点处的梯度构造一组共轭方向，并沿此组方向进行搜索，求出极小点。适用范围：凸函数（二）共轭梯度法2FR共轭梯度法考虑问题：其中：为对称正定阵（1）算法步骤：步骤1任选初始点令步骤2若，则停止；否则转下一步令其中：步骤5置k=k+1返回步骤2步骤3步骤4定理设向量为共轭，则从点出发，相继以为搜索方向的下述算法：经n次一维搜索收敛于问题（I）的极小点FR共轭梯度法的理论推导*问题(I)证明：由式(1)

3、得则有由于一维搜索时为最佳步长，故即：2FR公式推导证明(1)式：由于一维搜索时为最佳步长，故证明(2)式：(i)(ii)设k=m-1时(2)式成立，(iii)k=mT用FR共轭梯度法求解（2）算法举例解：第一次迭代第二次迭代共轭搜索方向：例2用共轭梯度法求解下列问题：第一次迭代第二次迭代非二次型的共轭梯度法设为某一严格凸函数，具有二阶连续偏导用二阶泰勒展开近似表示迭代公式：（三）共轭梯度法的优缺点优点（1）程序简单，占内存少；（2）收敛速度较快，介于梯度法和牛顿法之间。缺点（1）当较小时计算可能带来较大

4、的舍入误差，甚至引起不稳定；（2）不进行“n步重新开始”一直作下去，收敛很慢，甚至不收敛。适用场合各种问题，对于高维问题效果尤佳。模式搜索法（步长加速法）探测移动：依次沿n个坐标轴进行，用于确定新的基点和有利于函数值下降的方向。模式移动：沿相邻两个基点连线方向进行，试图使函数值更快减少。（一）模式搜索法的思路探测性搜索：模式搜索（二）模式搜索法的迭代步骤例3用步长加速法求解下列问题：优点(1)编制程序比较简单(2)对函数的要求宽松,不需函数的导数信息。缺点收敛速度比较慢，适用场合对变量不多的问题可以使用，

5、另外，还可用于求解非线性目标规划问题。（三）模式搜索法的优缺点作业：习题43（1），5，6（选做）