Reference
【概述】
在 牛顿迭代法 中，介绍了海森矩阵（Hessian Matrix），以及原始牛顿迭代法、阻尼牛顿迭代法
牛顿迭代法虽然收敛速度快，但在计算过程中需要计算目标函数 $f(\mathbf{x})$ 的梯度 $\triangledown f$ 和二阶偏导数 $\triangledown^2f $，以及海森矩阵的逆矩阵 $H^{-1}$，计算量大，且有时海森矩阵无法保持正定，使得牛顿迭代法失效
为克服上述的这两个问题，于是提出了拟牛顿法（Quasi Newton Method）
拟牛顿法又称拟牛顿迭代法，其基本思想是：不用二阶偏导数而构造出近似海森矩阵的正定对称矩阵，在拟牛顿的条件下优化目标函数，从而简化计算过程
使用不同的构造构造方法，就产生了不同拟牛顿法，常见的有：DFP 算法、BFGS 算法、L-BFGS 算法等
【拟牛顿条件】
拟牛顿条件（Quasi Newton Condition）为拟牛顿法提供理论指导，指出了用来近似海森矩阵 $H$ 的矩阵应满足的条件
对于无约束极小化问题：
其中，$\mathbf{x}=(x^{(1)},x^{(2)},…,x^{(n)})^T\in \mathbb{R}^n$，$x^{(i)}$ 为向量 $\mathbf{x}$ 的第 $i$ 个分量
设经过了 $k+1$ 次迭代后，得到 $\mathbf{x_{k+1}}$，此时将目标函数 $f(\mathbf{x})$ 在 $\mathbf{x_{k+1}}$ 附近利用多元函数的泰勒展开式作二阶展开，有：
在两边同时作用一个梯度算子 $\triangledown$，有：
其中，$\mathbf{g_{k+1}}$ 为梯度向量，$H_{k+1}$ 为海森矩阵
取 $\mathbf{x}=\mathbf{x_k}$，则 $\triangledown f(\mathbf{x})=\mathbf{g_k}$，故有：
移项得：
记第 $k$ 次迭代与第 $k+1$ 次迭代的梯度差为 $\mathbf{y_k}=\mathbf{g_{k+1}}-\mathbf{g_k}$，$\mathbf{x}$ 的增量为$\boldsymbol{\delta_k}=\mathbf{x_{k+1}}-\mathbf{x_k}$，则有：
或：
这就是拟牛顿条件，其对牛顿法迭代过程中的海森矩阵 $H_{k+1}$ 进行约束
令 $B$ 表示对海森矩阵 $H$ 本身的近似，用 $D$ 表示对海森矩阵的逆 $H^{-1}$ 的近似，即：
此时，对 $H_{k+1}$ 做近似有 $B_{k+1}$，对 $H_{k+1}^{-1}$ 做近似有 $D_{k+1}$，故拟牛顿条件可写为：
或
【拟牛顿法】
在拟牛顿法中，通常选择 $D_{k}$ 作为 $H_{k}^{-1}$ 的近似（DFP 算法），或选择 $B_{k}$ 作为 $H_{k}$ 的近似（BFGS 算法），使其满足拟牛顿条件
从而令搜索方向由 $\mathbf{d_k}=-H_k^{-1}\cdot \mathbf{g_k}$ 近似为 $\mathbf{d_k}=-D_k\cdot \mathbf{g_k}$ 或 $\mathbf{d_k}=-B_k^{-1}\cdot \mathbf{g_k}$
拟牛顿法具体的算法如下表
| 方法 | 迭代式 | 具体介绍 |
|---|---|---|
| DFP 算法 | $D_{k+1}=D_k+\frac{\boldsymbol{\delta_k}\boldsymbol{\delta_k}^T}{\boldsymbol{\delta_k}^T\mathbf{y_k}}-\frac{D_k\mathbf{y_k}\mathbf{y_k}^TD_k}{\mathbf{y_k}^TD_k\mathbf{y_k}}$ | DFP 算法 |
| BFGS 算法 | $G_{k+1} =(I-\frac{\boldsymbol{\delta_k}\mathbf{y_k}^T}{\mathbf{y_k}^T\boldsymbol{\delta_k}})G_k(I-\frac{\mathbf{y_k}\boldsymbol{\delta_k}^T}{\mathbf{y_k}^T\boldsymbol{\delta_k}})+\frac{\boldsymbol{\delta_k}\boldsymbol{\delta_k}^T}{\mathbf{y_k}^T\boldsymbol{\delta_k}}$ | BFGS 算法 |
| Broyden 族 | $G^{\phi}_{k+1}=\phi_{k} G^{DFP}_{k+1}+(1-\phi_k)G^{BFGS}_{k+1},\quad 0\leq\phi\leq 1$ | Broyden 族 |
| L-BFGS 算法 | $-$ | L-BFGS 算法 |
