Broyden 族

Reference

• 最优化方法复习笔记（四）拟牛顿法与SR1,DFP,BFGS三种拟牛顿算法的推导与代码实现
• Broyden类算法

【DFP 与 BFGS 的关系】

对于 DFP 算法来说，其迭代式为：

$$D_{k+1}=D_k+\frac{{\mathit{\delta }}_{\mathit{k}}{\mathit{\delta }}_{\mathit{k}}^T}{{\mathit{\delta }}_{\mathit{k}}^T{\mathbf{y}}_{\mathbf{k}}}-\frac{D_k{\mathbf{y}}_{\mathbf{k}}{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k}{{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k{\mathbf{y}}_{\mathbf{k}}},k=0,1,2,...$$

利用在 BFGS 算法 中提到的 Sherman-Morrison-Woodbury 公式，对其两边进行求逆（证明过程与 BFGS 中相似），可得：

$$D_{k+1}^{-1}=D_k^{-1}-(\frac{{{\mathbf{y}}_{\mathbf{k}}}^T{B}_k^{-1}{\mathbf{y}}_{\mathbf{k}}}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}+1)\frac{{\mathit{\delta }}_{\mathit{k}}{\mathit{\delta }}_{\mathit{k}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}-\frac{D_k^{-1}{\mathbf{y}}_{\mathbf{k}}{\mathit{\delta }}_{\mathit{k}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}-\frac{{\mathit{\delta }}_{\mathit{k}}{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k^{-1}}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}$$

对于 BFGS 算法来说，其迭代格式为：

$$B_{k+1}=B_k+\frac{{\mathbf{y}}_{\mathbf{k}}{{\mathbf{y}}_{\mathbf{k}}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}-\frac{B_k{\mathit{\delta }}_{\mathit{k}}{\mathit{\delta }}_{\mathit{k}}^T{B}_k}{{\mathit{\delta }}_{\mathit{k}}^T{B}_k{\mathit{\delta }}_{\mathit{k}}},k=0,1,2,...$$

在 BFGS 算法 中，详细证明了使用 Sherman-Morrison-Woodbury 公式后得到的蕴含 $B_{k+1}^{-1}$ 与 $B_k^{-1}$ 的关系式的 BFCS 算法的迭代式，即：

$$B_{k+1}^{-1}=B_k^{-1}-(\frac{{{\mathbf{y}}_{\mathbf{k}}}^T{B}_k^{-1}{\mathbf{y}}_{\mathbf{k}}}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}+1)\frac{{\mathit{\delta }}_{\mathit{k}}{\mathit{\delta }}_{\mathit{k}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}-\frac{B_k^{-1}{\mathbf{y}}_{\mathbf{k}}{\mathit{\delta }}_{\mathit{k}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}-\frac{{\mathit{\delta }}_{\mathit{k}}{{\mathbf{y}}_{\mathbf{k}}}^T{B}_k^{-1}}{{{\mathbf{y}}_{\mathbf{k}}}^T{\mathit{\delta }}_{\mathit{k}}}$$

在 拟牛顿迭代法 中，介绍了拟牛顿条件，其对牛顿法迭代过程中的海森矩阵 $H_{k+1}$ 进行约束，规定用 $B$ 表示对海森矩阵 $H$ 本身的近似，用 $D$ 表示对海森矩阵的逆 $H^{-1}$ 的近似，即：

$$B\approx H,D\approx H^{-1}$$

因此，有：

$$B^{-1}=D$$

此时再看 DFP 和 BFGS 迭代式与其求逆后的迭代式，可以发现，双方高度对称，只需令 ${\mathit{\delta }}_{\mathit{k}}\leftrightarrow {\mathbf{y}}_{\mathbf{k}}$，$B_k\leftrightarrow D_k$，即可在 DFP 和 BFGS 之间相互转换

因此，DFP 与 BFGS 互为对偶

【Broyden 族】

既然 DFP 与 BFGS 互为对偶，那么在具体应用中，选择哪一个会更好？

一个基本的思路是通过若干组实验来测试哪个算法在模型训练过程中更优，或对其进行收敛验证，但这无疑会耗费大量的时间

为此，Broyden 提出了一种较为简易的思路，即将 DFP 的迭代式与 BFGS 的迭代式进行正加权组合

将由 DFP 算法的迭代式得到的 $D_{k+1}$ 记作 $G_{k+1}^{DFP}$，即：

$$G_{k+1}^{DFP}=D_{k+1}=D_k+\frac{{\delta }_{\mathbf{k}}{{\delta }_{\mathbf{k}}}^T}{{{\delta }_{\mathbf{k}}}^T{\mathbf{y}}_{\mathbf{k}}}-\frac{D_k{\mathbf{y}}_{\mathbf{k}}{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k}{{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k{\mathbf{y}}_{\mathbf{k}}},k=0,1,2,...$$

再将使用 Sherman-Morrison 公式后的 BFGS 算法的迭代式得到的 $G_{k+1}$ 记作 $G_{k+1}^{BFGS}$，即：

$$G_{k+1}^{BFGS}=G_{k+1}=(I-\frac{{\delta }_{\mathbf{k}}{{\mathbf{y}}_{\mathbf{k}}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\delta }_{\mathbf{k}}})G_k(I-\frac{{\mathbf{y}}_{\mathbf{k}}{{\delta }_{\mathbf{k}}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\delta }_{\mathbf{k}}})+\frac{{\delta }_{\mathbf{k}}{{\delta }_{\mathbf{k}}}^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{\delta }_{\mathbf{k}}}$$

由于 $G_{k+1}^{DFP}$ 与 $G_{k+1}^{BFGS}$ 均满足拟牛顿条件，那么它们的线性组合也满足拟牛顿条件，且是正定的，故有：

$$G_{k+1}^{\varphi }={\varphi }_k{G}_{k+1}^{DFP}+(1-{\varphi }_k)G_{k+1}^{BFGS},0\le \varphi \le 1$$

当 ${\varphi }_k=0$ 时，$G_{k+1}^{\varphi }$ 为 BFGS 校正，${\varphi }_k=1$ 时，$G_{k+1}^{\varphi }$ 为 DFP 校正

随着 ${\varphi }_k$ 遍历 $[0,1]$ 的值，就可以得到一系列的 $G_{k+1}^{\varphi }$，这一系列的 $G_{k+1}^{\varphi }$ 的集合被称为 Broyden 族