DFP 算法

Reference

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

  【概述】

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

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

$$D_{k+1}=D_k+\mathrm{△}{D}_k,k=0,1,2,...$$

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

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

【算法原理】

假设校正矩阵 $\mathrm{△}{D}_k$ 与拟牛顿条件 ${\mathit{\delta }}_{\mathit{k}}=D_{k+1}{\mathbf{y}}_{\mathbf{k}}$、近似矩阵 $D_k$ 有关

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

$$\mathrm{△}{D}_k=\alpha \mathit{\mu }{\mathit{\mu }}^T+\beta \mathit{\nu }{\mathit{\nu }}^T$$

从形式上看，这种待定公式保证了校正矩阵 $\mathrm{△}{D}_k$ 的对称性

结合拟牛顿条件 ${\mathit{\delta }}_{\mathit{k}}=D_{k+1}{\mathbf{y}}_{\mathbf{k}}$，将 $\mathrm{△}{D}_k$ 的待定式带入迭代式，有：

$$\begin{array}{rl}{\mathit{\delta }}_{\mathit{k}}& =D_{k+1}{\mathbf{y}}_{\mathbf{k}}\\ & =(D_k+\mathrm{△}{D}_k){\mathbf{y}}_{\mathbf{k}}\\ & =D_k{\mathbf{y}}_{\mathbf{k}}+\alpha \mathit{\mu }{\mathit{\mu }}^T{\mathbf{y}}_{\mathbf{k}}+\beta \mathit{\nu }{\mathit{\nu }}^T{\mathbf{y}}_{\mathbf{k}}\\ & =D_k{\mathbf{y}}_{\mathbf{k}}+\mathit{\mu }(\alpha {\mathit{\mu }}^T{\mathbf{y}}_{\mathbf{k}})+\mathit{\nu }(\beta {\mathit{\nu }}^T{\mathbf{y}}_{\mathbf{k}})\\ & =D_k{\mathbf{y}}_{\mathbf{k}}+(\alpha {\mathit{\mu }}^T{\mathbf{y}}_{\mathbf{k}})\mathit{\mu }+(\beta {\mathit{\nu }}^T{\mathbf{y}}_{\mathbf{k}})\mathit{\nu }\end{array}$$

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

$$\{\begin{array}{rll}\alpha {\mathit{\mu }}^T{\mathbf{y}}_{\mathbf{k}}& =& 1\\ \beta {\mathit{\nu }}^T{\mathbf{y}}_{\mathbf{k}}& =& -1\end{array}$$

带回 ${\mathit{\delta }}_{\mathit{k}}$ 中，有：

$${\delta }_{\mathbf{k}}-D_k{\mathbf{y}}_{\mathbf{k}}=\mathit{\mu }-\mathit{\nu }$$

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

$$\{\begin{array}{rll}\alpha & =& \frac{1}{{\mathit{\delta }}_{\mathit{k}}^T{\mathbf{y}}_{\mathbf{k}}}\\ \beta & =& -\frac{1}{{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k{\mathbf{y}}_{\mathbf{k}}}\end{array}$$

这时，校正矩阵 $\mathrm{△}{D}_k$ 已构造出来，即：

$$\mathrm{△}{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^T}{{{\mathbf{y}}_{\mathbf{k}}}^T{D}_k{\mathbf{y}}_{\mathbf{k}}}$$

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

$$D_k^T=D_k$$

因此，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,...$$

【算法流程】

DFP 算法的算法流程如下：

1. 给定初值 ${\mathbf{x}}_{\mathbf{0}}$ 和精度阈值 $\epsilon$，并令 $D_0=I$，$k=0$
2. 计算梯度向量 ${\mathbf{g}}_{\mathbf{k}}$，与搜索方向 ${\mathbf{d}}_{\mathbf{k}}=-D_k\cdot {\mathbf{g}}_{\mathbf{k}}$
3. 利用 ${\lambda }_k=\arg \underset{\lambda \in \mathbb{R}}{min}f({\mathbf{x}}_{\mathbf{k}}+\lambda {\mathbf{d}}_{\mathbf{k}})$ 得到步长 ${\lambda }_k$，并令 ${\mathit{\delta }}_{\mathit{k}}=\lambda {\mathbf{d}}_{\mathbf{k}}$，${\mathbf{x}}_{\mathbf{k}\mathbf{+}\mathbf{1}}={\mathbf{x}}_{\mathbf{k}}+{\mathit{\delta }}_{\mathit{k}}$
4. 若 ${\mathbf{x}}_{\mathbf{k}\mathbf{+}\mathbf{1}}$ 的梯度向量 ${\mathbf{g}}_{\mathbf{k}\mathbf{+}\mathbf{1}}$ 的 L1 范数 $||{\mathbf{g}}_{\mathbf{k}\mathbf{+}\mathbf{1}}||$ 满足 $||{\mathbf{g}}_{\mathbf{k}\mathbf{+}\mathbf{1}}||<\epsilon$，则停止迭代，得近似解 ${\mathbb{x}}^{\ast }={\mathbf{x}}_{\mathbf{k}\mathbf{+}\mathbf{1}}$，否则转至步骤 5
5. 计算两次迭代的梯度差 ${\mathbf{y}}_{\mathbf{k}}={\mathbf{g}}_{\mathbf{k}\mathbf{+}\mathbf{1}}-{\mathbf{g}}_{\mathbf{k}}$
6. 计算第 $k+1$ 次的近似矩阵 $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}}}$
7. 令 $k=k+1$，转至步骤 2