最优化理论与方法课件.ppt

《最优化理论与方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无约束非线性规划2010-4-22主要内容（使用导数的方法）1、最速下降法2、牛顿法3、共轭梯度法4、拟牛顿法主要内容（不使用导数的方法：直接法）1、模式搜索法2、转轴法3、单纯形搜索法4、powell方法最速下降法问题：其中函数具有一阶连续偏导数算法思想：希望从某一点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点。函数在点处沿方向的变化率可用方向导数来表达，对于可微函数，方向导数等于梯度与方向的内积，即最速下降方向：最速下降法的迭代公式是：其中是从算法步骤：例：用最速下降法解问题最速下降法的锯齿现象结论：从局部看，最速下降方向确是函数值下降最快的方向。从全局看，由于锯齿现象的影

2、响，收敛较慢。所以，最速下降法一般适用于计算过程的前期迭代。牛顿法算法思想：牛顿法的“二次终止性”设有二次凸函数求极值：解析法：牛顿法：即1次迭代达到极小点牛顿法的牛顿方向当初值远离极小点时，迭代点不一定是最好的。因此，可以对牛顿法进行修正，提出阻尼牛顿法。阻尼牛顿法：算法步骤：牛顿法的进一步修正原始牛顿法和阻尼牛顿法虽然不同，但有共同缺点。1.可能出现Hesse矩阵奇异2.即使非奇异，也未必正定，因而牛顿方向不一定是下降方向。例：用阻尼牛顿法求解下列问题修正方法：共轭梯度法无约束最优化方法的核心问题是选择搜索方向。下面讨论基于共轭方向的一种算法—共轭梯度法。共轭：设A是nxn对称正定矩阵，若

3、中的两个方向和满足，则称这两个方向关于A共轭，或称它们关于A正交。若则称这组方向是A共轭的，或称它们为A的k个共轭方向。定理：设A是n阶对称正定矩阵，是k个A共轭的非零向量，则这个向量组线性无关。定理：对于二次凸函数，若沿一组共轭方向搜索，经有限步迭代必达到较小点。FR共轭梯度法思想（Fletcher-Reeves)使用公式（1）、（2）可以构造一组共轭方向针对二次凸函数的FR共轭梯度法例：解：用于一般函数的共轭梯度法拟牛顿法为什么要提出拟牛顿法1.牛顿法的优点：收敛快2.牛顿法的缺点：要计算Hesse矩阵的逆拟牛顿法的核心思想：构造近似矩阵取代牛顿法Hesse矩阵的逆构造近似矩阵（DFP算法

4、）DFP算法步骤