拟牛顿算法，SR1，DFP，BFGS步骤

在牛顿算法中我们要面对逆向的Hessian以及二阶的偏导。导致我们的计算量很大，为了提高效率，如果无法使用Hessian矩阵H（x），或者如果计算逆矩阵的计算量太大（复杂度为O（N ^ 3），则拟牛顿法可以 仅可用于基于一阶导数，f（ x）（具有复杂度 O（N ^ 2））的梯度g来建立一个近似Hessian的矩阵或其逆的近似矩阵 ，类似于先前考虑的Broyden方法。我们可以使用拟牛顿算法。

下面我们考虑最小化函数f(x)。 围绕点X_n+1进行泰勒展开得到如下方程： 下面对X求导我们可以得到： Evaluating at x=x_n,并且设g(x_n) = g_n那么上面的式子就可以变为： 其中矩阵B _n 是Hessian矩阵H_n 的正割近似，最后的等式称为割线方程。 为了方便起见，我们进一步定义： 那么上面的公式可以变为： 那么我们有了Hessian的近似矩阵，这样我们就可以达成了拟牛顿算法 的条件。 拟牛顿步骤：

在我们的这个求解局部最小值中， B_n也就是我们的近似矩阵，要是一个正定举证。（正定矩阵的定义看我的另一篇文章）

SR1 是拟牛顿算法中的一种，这里B_n的更新需要添加一个附加项。 在这里u是一个向量。uut 是第一级的矩阵。以及加上我们的割线条件，就可以得到： 该方程式表示u与w=y_n - B_n s_n的方向相同，因此可以写成 u = cw 。 换回来我们得到: 然后我们求的c等于： 那么Bn就会变成： 接下来反转B_n+1我们可以得到： 要想得到上面的结果，我们还可以使用对偶分割条件的方法：

但是SR1 算法有个问题就是需要Bn的逆向保持正定。

在整个迭代过程中可能很难维持这一要求。 在以下DFP和BFGS方法中可以避免此问题。

在这个算法中需要添加两个额外附加项： 更具割线定理，我们可以得到： 然后将简化拓展：

像BFGS和DFP一样，它可能会出现舍入错误和行搜索不准确的情况。 BFGS和SR1更新之间的显着区别是，如果Bk为正定且skyk> 0，则BFGS保证产生正定Bk + 1，而SR1不具有此属性。SR1公式在许多情况下都可以生成更准确的Hessian近似值。 BFGS优于DFP的原因在于，BFGS有自校正的性质(self-correcting property)。通俗来说，如果某一步BFGS对Hessian阵的估计偏了，导致优化变慢，那么BFGS会在较少的数轮迭代内（取决于线搜索的质量），校正估计的Hessian阵。