牛顿法二阶梯度法

1、l一原始牛顿法l 基本思想：是利用二次函数（二次曲线） l来逐点去近似或逼近原目标函数 ，然后求出这个二次函数的极小点 作为对原目标函数求优的下一个迭代点 通过若干次的l重复迭代，使迭代点逐步逼近原目标函数极小点 。 x xfxk1x*0 x*l设已知一维目标函数 的初始点l过a点作一与原目标函数 相切的二次曲线抛物线 ，求此抛物线的极小点的坐标 ，将 代入原目标函数 求得 值或b点，过b再作与 相切的二次曲线求c直到求出 。 xf xxkkfa, xf xxk1xk1 xfxkf1 xfx*l设 只有连续一，二阶偏导数，在l点邻域取 的泰勒二次多项式l求此函数的极小点 可由 l求得l这是一维

2、问题，同理对于n维问题有 xfxk xf xxxxxxxkfxffkkkkk 221xk 0 xkl上式中 xxxxxxfxxkktktkkxfkxkf221 xxkkhf2nxfhxxxjik1,2,.ji, 2l因此上式有：当 时，可求 的极值点，当矩阵为正定时，有极小值。由（1）得 0 x x xh (2) xxxkkkxhfx (1) )(21xfxhkxkfxxxxxxfxxkktktkkl因为（1）式可写为l其中： xxxhxgfxttxx21 xxgxfkkxkxxxffl因为 是二次函数，故 是线性函数。l令 由（2）式则有l若 为可逆矩阵，上式两边左乘l 则有下式： x x

3、0x 0 xxxkkkxhf xkh xhk1l得：l当 为二次函数时，x就是 01xixxhknkxfk xxhxkkfkx1 xfx*l 是一个常数矩阵l则牛顿法的一般迭代公式是：l迭代方向 xkh xxhxxkkkfk11 xxhskkfk1l该方向为牛顿方向l在迭代公式中没有步长因子，或看作是步长恒等于1。l通过这种迭代，逐次向极小点逼近。l试用牛顿法 1 .0,0060410021212221xxxxxxxxf给定初始点的无约束最优解，例：求目标函数l在上面的牛顿法中，存在一个问题，由于迭代式中没有步长因子，或者说步长l =1，所以有时函数值反而有所增大，即 因而可能造成点列的发l散

4、，而使计算失败。从而要对古典（原始）牛顿法做修正，提出修正牛顿法。 k xxkkff1l方法：步长改用最优步长因子 ，将迭代式改写为：l 应为 k xxhxxkkkkfk11sk xxhskkfk1 sxxkkkk1l 为l 0l此时初始点无论如何选择，则可得到最优结果。)()(min)()()()()()(kkkkkksxfsxf k kl步骤如下：l（1）任选初始点 ，给定精度l 置k=0l（2）计算 点的梯度和海赛矩阵的逆l 矩阵l（3）检验是否满足精度要求，l若满足停止迭代，否则进行（4）步xkfrxn)0(0 xkl（4）令l（5）从 出发沿牛顿方向 进行一l 维搜索l求出最优步长l

5、（6）令l k=k+1 转步骤（2） xxhskkfk1 xk sk)()(min)()()()()()(kkkkkksxfsxf k sxxkkkk1l使用牛顿法的条件：n（变量较多时）因次较高，海赛矩阵是奇异矩阵，逆矩阵不存在，不能使用牛顿法。l例：用牛顿法求函数l的最优解，初始点 102214212211xxxxxf 100 0-50 txl由于梯度法和牛顿法具有以上的缺点，能不能找到一种方法能拟补上两种方法的缺点，从而综合上两种方法的各自优点，提出了如下变尺度法的基本思路。l基本思想：在牛顿法中探索方向l设法构造出一个对称正定矩阵 来代替 xxhskkfk1ak)(l 在迭代中逐渐逼近

6、l 简化牛顿法的计算，l 且收敛快。l变尺度法是用 来逼近l所以称拟牛顿法，迭代公式为：xhk1xhk1ak)(xhk1 sxxaxxkkkkkkkkf1l -步长由l求出l探索方向l （1）)(min)()()()()()()(kkkkkksxfsxf k xaskkfkl -n*n阶对称正定矩阵，是变化的，递推形式为 （2）l -校正矩阵，它与 ，l 向量有关。l综上可知：当 是梯度迭代公式l当 是牛顿迭代公式l以上两种方法是变尺度法的特例 eaakkk1 ek xxkk,1 xxkkff和1 iak xhakk1l怎样找出 ，先分析 的关系，设 为一般形式的目标函数，并且有连续的一、二阶

7、偏导数，在点 的泰勒近似展开为l梯度为 ak xfxh和 xf xk xxxxxxfxkktktkxhkxkfxf21)()()( xxgxxxkkkkkkxhxhfxfg l令 则有l两边左乘 xxkk1 111xxxgxgkkkkkkhf gggkkk1 xxxkkk1 xxhgkkk)( xhk1l这样找到了 与 及 l之间的关系，用 来代替l既有l迭代开始，可选择l如果构造出 后，再如果 可表示为（2）式 gxhxkkk1 xhk1 xk gk ak xhk1 gaxkkk iaak0 akak 1 eaakkk1l -校正矩阵，可用统一的公式表示。l经过三个人的修改的校正矩阵 的公式

8、即所谓dfp公式为： ek ekgagaggagxxxekktttkkkttkkkkkkk)()()()()()()()()()()()(l因为 为n*n阶对称正定矩阵，固有l式中l有 后就可按（2）式求出 akgagaggagxxxekkttkkkttkkkkkkk)()()()()()()()()()()()( gggkkk1 xxxkkk1 ekak 1l有 后就可按（1）求出 新方向探索l最后得出dfp变尺度法的迭代公式归结为ak 1sk 1xaskkkf111 eaaxassxsxsxxaxxkkkkkkkkkkkkkkkkkkkkffff111minl适用条件：容易求出f(x)的梯度n100时此方法最好。l所以又发展了bfgs比dfp更为成功，方法：只是 公式不同，其余完全相同。 ek)()()()()()()()()(1)()()()()()()()()(agxxgagxgagxxxxgxektktkkktkttkktkkkkkkktkkkl两种变尺度法的计算步骤一样为：l（1）任选初始点 ，给定精度l 维数nl（2）置k=0 ， （单位矩阵）l探索方向为， l（3）进行一维搜索求 ，rxn)0(0 ikaa0 gaxaskkkkkf)()()() 1(kkkksxx)( k)(min)()()()()()()(kkkkkksxfsxfl（4）计算 ，如果 小于给