DFP变尺度法优化策略

DFP变尺度法的迭代公式为

式中A^（k）是n×n阶对称矩阵。因为它是用来取代[H（X^（k））]^-1的，且在每次迭代计算中有变化，故称为变尺度矩阵。其递推形式为

A^（k+1）=A^（k）+E^（k） （4-11）

式中E^（k）为修正矩阵，可由下式确定：

式中

式（4-12）是Davidon于1959年提出，后经Fletcher和Powell修改和证明，故变尺度法又称为DFP法，式（4-12）称为DFP公式。

DFP变尺度法的迭代步骤如下：

1）给定初始点X^（0）∈Eⁿ，允许误差ε＞0。

2）检验是否满足收敛条件，若满足，则停止迭代，X^*=X^（0）；否则进行3）。

3）给定初始矩阵A^（0）=I，置Δf（X^（0））⇒G^（0），0⇒k。

4）置A^（k）G^（k）⇒S^（k）。

5）求h^（k），可用下列两式计算：

或

6）令X^（k+1）=X^（k）+h^（k）S^（k）。

7）检验是否满足条件满足，若满足，则停止迭代，X^*=X^（k+1）；否则，当k=n时，置X^（k+1）⇒X^（0），返回进行3）；当k＜n时，令G^（k+1）=Δf（X^（k+1）），计算：

8）置k+1⇒k，返回进行4）。

DFP变尺度法的迭代过程如图4-5所示。

图4-5 DFP变尺度法程序框图

【例4-4】 试用DFP变尺度法求目标函数f（X）=2x²₁+x²₂+x₁x₂的极小点及极小值。(https://www.daowen.com)

解 给定初始点为X^（0）=[0.371，0.116]^T，和允许误差ε=0.001。

因为

故进行第一次迭代计算。

第一次迭代计算：

给定初始矩阵

令

则

求h（0）：

于是

而

第二次迭代计算：

求h^（1）：

于是

因为

故需继续进行迭代计算，最后得到：

f（X^*）=0.000245973206

上述迭代过程表明，DFP变尺度法在目标函数f（X）的梯度向量易求的情况下，是比较有效的一种最优化方法。理论上可证明其搜索方向是相互共轭的，对于n维正定二次函数来说，只需n次迭代即可收敛，因此它也具有二次收敛速度。对于非二次函数，其收敛速度介于牛顿法和梯度法之间。DFP变尺度法的主要缺点是存储量较大，以及因DFP公式中含有近似矩阵A^（k），计算中容易引起数值不稳定。