《牛顿法和拟牛顿法课件.pptx》由会员分享，可在线阅读，更多相关《牛顿法和拟牛顿法课件.pptx（37页珍藏版）》请在三一办公上搜索。
1、牛顿法和拟牛顿法,无约束优化问题,线搜索方法,dk：搜索方向（下降就可）：dk f(xk)0 k：搜索步长：1）精确搜索：f(xd)达到最小 2）Wolfe 搜索：（两个条件）,精确搜索,Wolfe 非精确搜索,Wolfe 非精确搜索,线搜索方法的下降,方法收敛之关键：估计 搜索方向与最速下降方向的夹角,线搜索方法的收敛性,定理 如果 f(x)下方有界，如果搜索方向与最速下降法的夹角不靠近/2,则由线搜索方法产生的点列 xk 满足：|gk|0,搜索方向,最速下降法：共轭梯度法：牛顿法：,牛顿方向,牛顿方向是如下问题的解,牛顿法的优缺点,收敛快 二次收敛程序简单计算量大 需要二阶导数要求高 需要
2、二阶导数需要计算Hesse矩阵，而此矩阵可能非正定，可能导致搜索方向不是下降方向。,找替代牛顿法的方法,目标：收敛快 程序简单 同时 不需要二阶导数找：像牛顿 又不是牛顿 的家伙！,基本思想：用不包含二阶导数的矩阵近似Hesse矩阵的逆。,拟牛顿条件,秩1校正DFP(Davidon-Fletcher-Powell)算法：秩2校正BFGS(Broyden-Fletcher-Goldfarb-Shanno)公式及Broyden族,秩1校正,秩为1,注释,在一定条件下，收敛且具有二次终止性。无法保证Hk的正定性；即使能，也有可能导致Hk无界。,DFP算法,秩为2,计算步骤：,重置,DFP法具有二次终
3、止性！,搜索方向为下降方向,共轭,DFP法具有二次终止性！,BFGS公式,BFGS修正公式,DFP公式,Sherman-Morrison公式,经验表明，比DFP公式好。,Broyden族,Broyden族的所有成员均满足拟牛顿条件。,特 点,不必计算Hesse矩阵。当Hk0时，算法产生的方向均为下降方向，具有二次终止性。存储量较大。,拟牛顿法是无约束最优化方法中最有效的一类算法。,拟牛顿公式,Davidon(1959),Fletcher-Powell(1963)DFP 方法,DFP公式的逆形式,如果 H 是B 的拟矩阵,BFGS公式,BFGS 方法：(最常用的方法）Broyden(1970),Fletcher(1970),Goldfarb(1970),Shanno(1970),SR1公式,对称秩一方法,非对称秩一公式,优点：克服对称秩一方法的分母为零的困难缺点：不对称,PSB公式,Powell 对称化技巧：交替利用 秩一方法 和 对称化,有限内存拟牛顿法,约束问题的拟牛顿法,SQP方法,目标函数是LAGRANGE 函数的近似,SQP方法,良好的性质广泛应用与Lagrange-Newton 法的关系,总结,简单的“拟”可以是革命性的进步!,
