牛顿法和拟牛顿法

​牛顿法：牛顿法是二次收敛，因此收敛速度快。从几何上看是每次用一个二次曲面来拟合当前所处位置的局部曲面，而梯度下降法是用一个平面来拟合。

黑塞矩阵是由目标函数 f(x) 在点 X 处的二阶偏导数组成的 n*n 阶对称矩阵。

1. 牛顿法：将 f(x) 在 x(k) 附近进行二阶泰勒展开：

   

   其中，gk 是 f(x) 的梯度向量在 x(k) 的值，H(x(k)) 是 f(x) 的黑塞矩阵在点 x(k) 的值。牛顿法利用极小点的必要条件 f(x) 处的梯度为0，每次迭代中从点 x(k) 开始，假设

   

   ，对二阶泰勒展开求偏导有

   

   ，代入得到

   

   ，即

   

   ，以此为迭代公式就是牛顿法。                           
   

   ，令
   

   ，则有

   

   ，称为拟牛顿条件。根据选择 Gk 方法的不同有多种具体实现方法。                                         拟牛顿法：用一个 n 阶正定矩阵 Gk=G(x(k)) 来近似代替黑塞矩阵的逆矩阵就是拟牛顿法的基本思想。在牛顿法中黑塞矩阵满足的条件如下：

1. DFP 算法：假设每一步

   
   ，为使 Gk+1 满足拟牛顿条件，可使 Pk 和 Qk 满足
   
   ，
   
   ，例如取，
   
   ，
   
   ,就得到迭代公式
   

2. BFGS 算法：最流行的拟牛顿算法。考虑用 Bk 逼近黑塞矩阵，此时相应的拟牛顿条件是

   
   ，假设每一步
   
   ，则 Pk 和 Qk 满足
   
   ，
   
   ，类似得到迭代公式