牛顿法和拟牛顿法

牛顿法和拟牛顿法无约束优化问题线搜索方法•dk：搜索方向（下降就可）：dk▽f(xk)0•αk：搜索步长：1）精确搜索：f(x＋αd)达到最小2）Wolfe搜索：（两个条件）精确搜索Wolfe非精确搜索Wolfe非精确搜索线搜索方法的下降•方法收敛之关键：估计搜索方向与最速下降方向的夹角线搜索方法的收敛性定理如果f(x)下方有界，如果搜索方向与最速下降法的夹角不靠近π/2,则由线搜索方法产生的点列xk满足：||gk||→0搜索方向最速下降法：共轭梯度法：牛顿法：牛顿方向牛顿方向是如下问题的解牛顿法的优缺点收敛快－－－二次收敛程序简单计算量大－－－需要二阶导数要求高－－－需要二阶导数需要计算Hesse矩阵，而此矩阵可能非正定，可能导致搜索方向不是下降方向。找替代牛顿法的方法目标：收敛快程序简单同时不需要二阶导数找：像牛顿又不是牛顿的家伙！！！基本思想：用不包含二阶导数的矩阵近似Hesse矩阵的逆。拟牛顿条件)()()(1)(2)(kkkxfxfd)()()1(kkkkdxx与一阶导数的关系：首先分析1)(2)(kxf))(()(21))(()()()1()1(2)1()1()1()1()1(kkTkkkkkxxxfxxxxxfxfxfTaylorx展开：处进行二阶在点))(()()()1()1(2)1(kkkxxxfxfxf))(()()()1()()1(2)1()(kkkkkxxxfxfxf)(1)1(2)()()1(2)()()1()()()1()()()()()(::kkkkkkkkkkkkqxfppxfqxfxfqxxp)(1)(kkkqHpkH1.秩1校正2.DFP(Davidon-Fletcher-Powell)算法：秩2校正3.BFGS(Broyden-Fletcher-Goldfarb-Shanno)公式及Broyden族kkkHHHIH11;校正矩阵秩1校正TkkkkzzH)()(秩为1)(1)(kkkqHp)()()()(kTkkkkqzzH)()()()()(kTkkkkkkqzqHpz)()()()()(2)()(kkkTkkTkkqHpqqz)())(()()()()()()()(kkkTkTkkkkkkkqHpqqHpqHpH?0注释•在一定条件下，收敛且具有二次终止性。•无法保证Hk的正定性；即使能，也有可能导致△Hk无界。DFP算法TkkkTkkkkvvuuH)()()()(秩为2)(1)(kkkqHp)()()()()()(kTkkkTkkkkqvvuuH)()()()()()()()(kkkkTkkkkTkkkqHpqvvquu)()()()()()()()(1;1kTkkkkkkTkkkkqvqHvqupu；；令)()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH计算步骤：0,)1(x)()(kxf否是)(kxx)()()1()()(0)()()(minarg)(kkkkkkkkkkdxxdxfxfHdnk否是1:)()(1)()1()()()1()(kkHHHHxfxfqxxpkkkkkkkkkk)1()1(nxx1),(,)1()1(1kxfdIHn重置1001,12242min13.41)1(12221HxxxxDFP初始点方法求解：用例DFP法具有二次终止性！1294980118513617130538388630612H.0DFP),,...,1(0)(:)(kkHnkxf方法构造的则若定理)()()(kkkxfHd0)()()(kTkdxf搜索方向为下降方向110021)(min)()()1()(1)()(1)1(iiiii(i)(i)kjTiTTdxxpnkipApHnjiAppHxcxbAxxxfDFP其中则，令任取方法求解正定二次函数设用定理共轭11AHnDFP法具有二次终止性！BFGS公式)(1)(kkkqHp)(1)(kkkpBq)()()()()()()()(kkTkkTkkkkTkTkkkpBpBppBpqqqB)()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH互换)()(,kkqpBFGS修正公式DFP公式1111kkkkkBHBBB)()()()()()()()()()()()()()(11)()1(11111kTkTkkkkTkkkTkkTkkTkkkTkkBFGSkuMvMuvMMuvMqppqHHqpqpppqpqHqHHTTTSherman-Morrison公式经验表明，比DFP公式好。Broyden族BFGSkDFPkkHHH111)1(TkkDFPkvvH)()(1)()()()()()(21)()()()(kkTkkkkTkkkkTkkqHqqHqppqHqv其中Broyden族的所有成员均满足拟牛顿条件。0为保持正定性，取特点•不必计算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法的关系总结简单的“拟”可以是革命性的进步!