1、牛牛顿顿法和拟法和拟牛顿法牛顿法无约束优化问题无约束优化问题 线搜索方法线搜索方法 dk ：搜索方向 （下降就可）： dk f(xk) 0 k ： 搜索步长： 1） 精确搜索： f(xd ) 达到最小 2） Wolfe 搜索： （两个条件） 精确搜索精确搜索 Wolfe 非精确搜索非精确搜索 Wolfe 非精确搜索非精确搜索 线搜索方法的下降线搜索方法的下降 方法收敛之关键：估计 搜索方向与最速下降方向的夹角 线搜索方法的收敛性线搜索方法的收敛性定理定理 如果 f(x) 下方有界，如果搜索方向与最速下降法的夹角不靠近/2,则由线搜索方法产生的点列 xk 满足： | gk | 0 搜索方向搜索方
2、向最速下降法：共轭梯度法：牛顿法： 牛顿方向牛顿方向牛顿方向是如下问题的解 牛顿法的优缺点牛顿法的优缺点收敛快收敛快 二次收敛二次收敛程序简单程序简单计算量大计算量大 需要二阶导数需要二阶导数要求高要求高 需要二阶导需要二阶导数数需要计算需要计算HesseHesse矩阵，而此矩阵可能非正定矩阵，而此矩阵可能非正定，可可能导致搜索方向不是下降方向。能导致搜索方向不是下降方向。 找替代牛顿法的方法找替代牛顿法的方法目标：目标： 收敛快收敛快 程序简单程序简单 同时同时 不需要二阶导数不需要二阶导数找：找： 像牛顿像牛顿 又不是牛顿又不是牛顿 的家伙！的家伙！ )()()(1)(2)(kkkxfxf
3、d )()()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 kHkkkHHHIH 11;TkkkkzzH)()( )(1)
4、(kkkqHp )()()()(kTkkkkqzzH )()()()()(kTkkkkkkqzqHpz )()()()()(2)()(kkkTkkTkkqHpqqz )()()()()()()()()(kkkTkTkkkkkkkqHpqqHpqHpH ?0 TkkkTkkkkvvuuH)()()()( )(1)(kkkqHp )()()()()()(kTkkkTkkkkqvvuuH )()()()()()()()(kkkkTkkkkTkkkqHpqvvquu )()()()()()()()(1;1kTkkkkkkTkkkkqvqHvqupu ；令令)()()()()()()()(kkTkkTk
5、kkkTkTkkkqHqHqqHqpppH 计计算算步步骤骤：0,)1( x )()(kxf否否是是)(kxx )()()1()()(0)()()(minarg)(kkkkkkkkkkdxxdxfxfHd nk 否否是是1:)()(1)()1()()()1()( kkHHHHxfxfqxxpkkkkkkkkkk)1()1( nxx1),(,)1()1(1 kxfdIHn1001,12242min13. 41)1(12221HxxxxDFP初始点方法求解：用例1294980118513617130538388630612H. 0DFP),.,1(0)(:)(kkHnkxf方法构造的则若定理)()
6、()(kkkxfHd 0)()()( kTkdxf 1 10 021)(min)()()1()(1)()(1)1(iiiii(i)(i)kjTiTTdxxpnkipApHnjiAppHxcxbAxxxfDFP其中则，令任取方法求解正定二次函数设用定理11 AHn)(1)(kkkqHp )(1)(kkkpBq )()()()()()()()(kkTkkTkkkkTkTkkkpBpBppBpqqqB )()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH 互换互换)()(,kkqp1111 kkkkkBHBBB)()()()()()()()()()()()()()
7、(11)()1 (11111kTkTkkkkTkkkTkkTkkTkkkTkkBFGSkuMvMuvMMuvMqppqHHqpqpppqpqHqHHTTT BFGSkDFPkkHHH111)1( TkkDFPkvvH)()(1 )()()()()()(21)()()()(kkTkkkkTkkkkTkkqHqqHqppqHqv其中其中0 为保持正定性，取为保持正定性，取 拟牛顿公式拟牛顿公式Davidon(1959), Fletcher-Powell(1963)Davidon(1959), Fletcher-Powell(1963)DFP DFP 方法方法 DFP公式的逆形式公式的逆形式如果如果
8、 H H 是是B B 的拟矩阵的拟矩阵 BFGS公式公式BFGS BFGS 方法：方法： ( (最常用的方法）最常用的方法） Broyden(1970), Fletcher(1970), Broyden(1970), Fletcher(1970), Goldfarb(1970), Shanno(1970)Goldfarb(1970), Shanno(1970) SR1公式公式对称秩一方法对称秩一方法 非对称秩一公式非对称秩一公式优点：克服对称秩一方法的分母为零的困难优点：克服对称秩一方法的分母为零的困难缺点：缺点： 不对称不对称 PSB公式公式Powell Powell 对称化技巧：对称化技巧： 交替利用交替利用 秩一方法秩一方法 和和 对称化对称化有限内存拟牛顿法有限内存拟牛顿法约束问题的拟牛顿法 SQP方法方法目标函数是目标函数是LAGRANGE LAGRANGE 函数的近似函数的近似SQP方法 良好的性质 广泛应用 与Lagrange-Newton 法的关系 总结简单的“拟”可以是革命性的进步!
