拟牛顿法
拟牛顿法(Quasi-Newton Methods)
是求解非线性优化问题最有效的方法之一。其在牛顿法的基础上，利用相邻两个点的位移和一阶导数信息构造与二阶导数阵相似的正定矩阵。从而以在不直接计算Hessian矩阵的情况下实现高维问题的超线性收敛。
牛顿法通过计算每一步的梯度 \(\nabla f\left(\mathbf{x}_{k}\right)\) 与Hessian矩阵 \(\mathbf{H}_{f}\left(\mathbf{x}_{k}\right)\) 迭代更逼近驻点的 \(\mathbf{x}_{k+1}\)
\[\mathbf{x}_{k+1}=\mathbf{x}_{k}-\mathbf{H}_{f}^{-1}\left(\mathbf{x}_{k}\right) \nabla f\left(\mathbf{x}_{k}\right).\]
其最大难度在于求解维度超大的Hessian矩阵与其逆矩阵 \(\mathbf{H}_{f}^{-1}\left(\mathbf{x}_{k}\right)\) ，而拟牛顿法则通过一维导数（梯度）的变化便可以得到近似的Hessian矩阵，而大大降低了求解难度与求逆的时间。
基本步骤
（以下高维向量、矩阵不再加粗表示）
记 \(B_k\) 表示第 \(k\) 次迭代的近似Hessian矩阵称为切线刚度矩阵，其初始为单位矩阵，即 \(B_0=I\). 根据
\[B_kp_k=-\nabla f\left(x_{k}\right)\]
计算 \(p_k\) ，作为每一次迭代的步。
\[x_{k+1}=x_k+\alpha p_k\]
其中 \(\alpha\) 一般计为 \(1.0\)，也可以从 \(1.0\) 折半查找，直到 \(f(x_{k+1})\) 更优。计算
\[s_k=\alpha p_k\ ,\ y_k=\nabla f\left(x_{k+1}\right)-\nabla f\left(x_{k}\right).\]
计算新的刚度矩阵
\[B_{k+1}=B_{k}-\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{T} B_{k} s_{k}}+\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}} （BFGS算法）.\]
若误差足够小，如等式约束两端误差小于 \(\epsilon\) 则得到解，否则继续迭代。
刚度矩阵算法
以上以BFGS法为例，介绍了基本的拟牛顿法步骤，其他方法也仅仅在计算刚度矩阵上进行的变化。
DFP法
\[B_{k+1}=B_{k}-\frac{B_{k} y_{k} y_{k}^{T} B_{k}}{y_{k}^{T} B_{k} y_{k}}+\frac{s_{k} s_{k}^{T}}{y_{k}^{T} s_{k}}\]
DFP方法是秩-2更新的一种，由它产生的矩阵 \(B_k\) 是正定的，而且满足这样的极小性：
\[\min _{B}\left|B-B_{k}\right| \text { s.t. } B=B^{T}, B s_{k}=y_{k}\]
BFGS法
\[B_{k+1}=B_{k}-\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{T} B_{k} s_{k}}+\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}} \]
该方法 \(B_k\) 同样正定，也同样满足上述的极小性。
且BFGS和DFP公式在形式上是对称的，但是BFGS比DFP更加有效。
对称秩1（SR1）法
\[B_{k+1}=B_{k}+\frac{\left(y_{k}-B_{k} s_{k}\right)\left(y_{k}-B_{k} s_{k}\right)^{T}}{\left(y_{k}-B_{k} s_{k}\right)^{T} s_{k}}\]
有别于DFP和BFG方法，SR1是一种秩-1更新。
SR1公式不要求矩阵 \(B_k\) 保持正定性，从而更逼近真实的Hesse矩阵，所以适用于信赖域方法(Trust Region Methods)。
Broyden族
\[B_{k+1}=\left(1-c_{k}\right) B_{k+1}^{B F G S}+c_{k} B_{k+1}^{D F P}\]
当 \(c_k=0\) 时，Broyden族公式就变成了BFGS公式；当 \(c_k=1\) 时，Broyden族公式就变成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一员。