DFP算法介绍及其稳定性分析

在变尺度法中，校正矩阵E^（k）取不同的形式，就形成不同的变尺度法。DFP算法中的校正矩阵E^（k）取下列形式：

E^（k）=α^（k）u^（k）（u^（k））^T+β^（k）v^（k）（v^（k））^T （4-21）

其中u^（k）、v^（k）是n维待定向量；α^（k）、β^（k）是待定常数，u^（k）（u^（k））^T、v^（k）（v^（k））^T是对称秩一的矩阵，它们可以说是一种最简单的矩阵。

根据校正矩阵E（k）要满足拟牛顿条件

E^（k）y^（k）=z^（k）-M^（k）y^（k）则有（α^（k）u^（k）（u^（k））T+β^（k）v^（k）（v^（k））^T）y^（k）=z^（k）-M^（k）y^（k）即α^（k）u^（k）（u^（k））^Ty^（k）+β^（k）v^（k）（v^（k））^Ty^（k）=z^（k）-M^（k）y^（k）

满足上面方程的待定向量u^（k）和v^（k）有多种取法，我们取

α^（k）u^（k）（u^（k））^Ty^（k）=z^（k）

β^（k）v^（k）（v^（k））^Ty^（k）=M^（k）y^（k）

注意到（u^（k））^Ty^（k）、（v^（k））^Ty^（k）都是数量，不妨取

u^（k）=z^（k）

v^（k）=M^（k）y^（k）

这样就可以定出

从而可得DFP算法的校正公式为(www.xing528.com)

DFP算法的计算步骤和变尺度法的一般步骤相同，只是具体计算校正矩阵时应按上面公式迸行。

当初始矩阵M^（0）选为对称正定矩阵时，DFP算法将保证以后的迭代矩阵M^（k）都是对称正定的，即使将DFP算法施用于非二次函数也是如此，从而保证算法总是下降的。这种算法用于多维问题（如20个变量以上），收敛速度快，效果好。DFP算法是无约束优化方法中最有效的方法之一，因为它不单纯是利用向量传递信息，还采用了矩阵来传递信息。DFP算法是戴维登（DaVidon）于1959年提出的，后来由弗来彻（Fletcher）和鲍威尔（Powell）于1963年做了改迸，故用三人名宇的第一个宇母命名。

DFP算法由于舍入误差和一维搜索不精确，有可能导致M^（k）奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法公式，称作BFGS（Broyden-Fletcher-Goldfarb-Shanno）算法，其校正公式为

因为变尺度法的有效性促使其不断发展，所以出现过许多变尺度的算法。1970年黄（Huang）从共轭条件出发对变尺度法做了统一处理，写出了统一公式

并取

E^（k）=z^（k）（u^（k））^T+M^（k）y^（k）（v^（k））^T

可以看出，当取α₁₂（^k）=α₂₁（^k）=0，α₁₁（^k）=α₂₂（k），α₂₂（k）=β^（k）时就是DFP算法的公式。

取α₁₂^（k）=α₂₁^（k），α₂₂^（k）=0就得到BFGS算法的公式。

还可以取

u^（k）=-v^（k）及α₁₁^（k）=0或α₁₂^（k）=0，α₁₁^（k）=α^（k）=-α₁₂^（k）=-α₂₁^（k）。

就是说，对α_ij^（k）赋值不同即可得到不同变尺度算法。如取α₁₁^（k）=α₂₂^（k）=0时得麦考密克（McCormick）算法；α^k₁₁=α^k₂₁=0即得皮尔逊（Pearson）算法等。