DFP 算法

Reference

• 牛顿法与拟牛顿法学习笔记（三）DFP 算法
• 优化算法——拟牛顿法之DFP算法
• Davidon–Fletcher–Powell formula

  【概述】

DFP 算法是建立在阻尼牛顿法之上的，由 Davidon 提出，后经 Fletcher 和 Powell 加以发展和完善，因此以三人的姓名的首字母命名，是最早的拟牛顿法

对于阻尼牛顿法的搜索方向 $\mathbf{d_k}=-H_k^{-1}\cdot \mathbf{g_k}$，根据拟牛顿条件，DFP 选用 $D_k$ 作为 $H_k^{-1}$ 的近似，其迭代格式为：

$$D_{k+1}=D_k+\triangle D_k,\quad k=0,1,2,...$$

其中，$D_0$ 取单位矩阵 $I$，因此，算法的关键就是每一次迭代的校正矩阵 $\triangle D_k$ 如何构造

关于拟牛顿条件详见：拟牛顿迭代法

【算法原理】

假设校正矩阵 $\triangle D_k$ 与拟牛顿条件 $\boldsymbol{\delta_k}=D_{k+1}\mathbf{y_k}$、近似矩阵 $D_k$ 有关

采用待定系数法，设 $\alpha$、$\beta$ 为待定系数，向量 $\boldsymbol{\mu},\boldsymbol{\nu} \in \mathbb{R}^n$ 为待定列向量，则校正矩阵 $\triangle D_k$ 可待定为：

$$\triangle D_k=\alpha\boldsymbol{\mu}\boldsymbol{\mu}^T+\beta\boldsymbol{\nu}\boldsymbol{\nu}^T$$

从形式上看，这种待定公式保证了校正矩阵 $\triangle D_k$ 的对称性

结合拟牛顿条件 $\boldsymbol{\delta_k}=D_{k+1}\mathbf{y_k}$，将 $\triangle D_k$ 的待定式带入迭代式，有：

$$\begin{align} \boldsymbol{\delta_k} &= D_{k+1}\mathbf{y_k} \notag \\ &= (D_k+\triangle D_k)\mathbf{y_k} \notag \\ &= D_k\mathbf{y_k}+\alpha\boldsymbol{\mu}\boldsymbol{\mu}^T\mathbf{y_k}+\beta\boldsymbol{\nu}\boldsymbol{\nu}^T\mathbf{y_k} \notag \\ &= D_k\mathbf{y_k}+\boldsymbol{\mu}(\alpha\boldsymbol{\mu}^T\mathbf{y_k})+\boldsymbol{\nu}(\beta\boldsymbol{\nu}^T\mathbf{y_k}) \notag \\ &=D_k\mathbf{y_k}+(\alpha\boldsymbol{\mu}^T\mathbf{y_k})\boldsymbol{\mu}+(\beta\boldsymbol{\nu}^T\mathbf{y_k})\boldsymbol{\nu} \notag \end{align}$$

可以发现，括号中的 $\alpha\boldsymbol{\mu}^T\mathbf{y_k}$ 与 $\beta\boldsymbol{\nu}^T\mathbf{y_k}$ 是两个数，取最简单的情况，进行如下赋值：

$$\left\{\begin{array}{rl} \alpha\boldsymbol{\mu}^T\mathbf{y_k} &=& 1 \\ \beta\boldsymbol{\nu}^T\mathbf{y_k} &=& -1 \end{array} \right.$$

带回 $\boldsymbol{\delta_k}$ 中，有：

$$\mathbf{\delta_k}-D_k\mathbf{y_k}=\boldsymbol{\mu}-\boldsymbol{\nu}$$

为使上式成立，直接取最简单情况 $\boldsymbol{\mu}=\boldsymbol{\delta_k}$，$\boldsymbol{\nu}=D_k\mathbf{y_k}$，此时，对于待定系数 $\alpha$、$\beta$，有：

$$\left\{\begin{array}{rl} \alpha &=& \frac{1}{\boldsymbol{\delta_k}^T\mathbf{y_k}} \\ \beta &=& -\frac{1}{\mathbf{y_k}^TD_k\mathbf{y_k}} \end{array} \right.$$

这时，校正矩阵 $\triangle D_k$ 已构造出来，即：

$$\triangle 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^T}{\mathbf{y_k}^TD_k\mathbf{y_k}}$$

由于近似矩阵 $D_k$ 为近似成海森矩阵逆矩阵 $H_k^{-1}$ 的正定矩阵，故有：

$$D_k^T=D_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}},\quad k=0,1,2,...$$

【算法流程】

DFP 算法的算法流程如下：

1. 给定初值 $\mathbf{x_0}$ 和精度阈值 $\varepsilon$，并令 $D_0=I$，$k=0$
2. 计算梯度向量 $\mathbf{g_k}$，与搜索方向 $\mathbf{d_k}=-D_k\cdot \mathbf{g_k}$
3. 利用 $\lambda_k=\arg \min\limits_{\lambda\in \mathbb{R}} f(\mathbf{x_k}+\lambda \mathbf{d_k})$ 得到步长 $\lambda_k$，并令 $\boldsymbol{\delta_k}=\lambda\mathbf{d_k}$，$\mathbf{x_{k+1}}=\mathbf{x_k} + \boldsymbol{\delta_k}$
4. 若 $\mathbf{x_{k+1}}$ 的梯度向量 $\mathbf{g_{k+1}}$ 的 L1 范数 $||\mathbf{g_{k+1}}||$ 满足 $||\mathbf{g_{k+1}}||<\varepsilon$，则停止迭代，得近似解 $\mathbb{x}^*=\mathbf{x_{k+1}}$，否则转至步骤 5
5. 计算两次迭代的梯度差 $\mathbf{y_k}=\mathbf{g_{k+1}}-\mathbf{g_k}$
6. 计算第 $k+1$ 次的近似矩阵 $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}}$
7. 令 $k=k+1$，转至步骤 2