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