拟牛顿法 Quasi Newton Method
拟牛顿法是以牛顿法为基础的优化方法，主要用于求解非线性方程组或连续函数的零点、极大、极小值问题。
当牛顿法中的雅可比矩阵或 Hessian 矩阵难以甚至无法计算时，拟牛顿法就起作用了，这是求解非线性优化问题最有效的方法之一，拟牛顿法由美国 Argonne 国家实验室的物理学家 W.C.Davidon 于 20 世纪 50 年代提出。
拟牛顿法的思想
牛顿法每次求解 Hessian 矩阵时需要先计算逆矩阵，这样会导致效率下降，但拟牛顿法使用正定矩阵来近似 Hessian 矩阵的逆矩阵，从而降低了算法复杂度并提升了效率。
常见的拟牛顿算法
- DFP (Davidon-Fletcher-Powell）算法
DFP 算法中选择 作为 的近似，假设每一步迭代中矩阵 是由 加上两个附加项构成，即
其中，
与
是待定矩阵。则
为使
满足拟牛顿条件，可使与满足
可取
可得矩阵的迭代公式
可以证明，如果初始矩阵
是正定的，则迭代过程中的每个矩阵
都是正定的。
- BFGS (Broyden-Fletcher-Goldfard-Shano) 算法
DFP 是用逼近海赛矩阵的逆矩阵
，而 BFGS 算法中选择
逼近海赛矩阵
，相应的拟牛顿条件
假设每一步迭代中矩阵
是由加上两个附加项构成，即
其中，与是待定矩阵。则
为使满足拟牛顿条件，可使与满足
可取
可得矩阵的迭代公式
可以证明，如果初始矩阵
是正定的，则迭代过程中的每个矩阵都是正定的。
- Broyden (Broyden’s algorithm) 类算法
我们可以从 BFGS 算法矩阵的迭代公式得到 BFGS 算法关于的迭代公式。
记
两次应用 Sherman-Morrison 公式，得
称为 BFGS 算法关于的迭代公式。
其中 Sherman-Morrison 公式：假设
是 n 阶可逆矩阵，
是 n 维向量，且
也是可逆矩阵，则：
令由 DFP 算法 的迭代公式得到的记作
，由 BFGS 算法的迭代公式得到的记作，由于 和 均满足拟牛顿条件，则两者的线性组合
也满足拟牛顿条件，而且是正定的。其中，
。该类算法称为 Broyden 类算法。