变尺度法

? 一、变尺度法的基本思想

变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系。我们观察一下梯度法和阻尼牛顿法的迭代公式，即：

式——（1）

和——（2）

分析比较这两种方法可知:梯度法的搜索方向为，只需计算函数的一阶偏导

数，计算工作量小，当迭代点远离最优点时对突破函数的非二次性极为有利，函数值下降很快，但是当迭代点接近最优点时收敛速度很慢。牛顿法的搜索方向为

，

不仅需要计算一阶偏导数而且要计算二阶偏导数矩阵及其逆矩阵.计算工作璧很大，但牛顿法具有二次收敛性，当迭代点接近最优点时收敛速度很快。对这两种方法取其优，去其劣，迭代过程先用梯度法，后用牛顿法并避开牛顿法的赫森矩阵的逆矩阵的繁琐计算，这就是萌生建立“变尺度法”的基本构想。下面对变尺度法的基本思想进行阐述。 变尺度法所构成的迭代公式为：

——（3）

式中为最优步长因子，由一维搜索

而得;对照无约束优化迭代通式。变尺度法的搜索方向应为；

是根据需要人为构造的一个n×n阶对称矩阵，它在迭代过程中随迭代点的位置变化而变化。若在初始点

取

为单位矩阵取I,则式(3}就成为式(1)表示的梯度法迭代公式，搜索

，使它在整个迭代过程中

时。式(3)就

方向为负梯度方向。以后随着迭代过程不断地修正构造矩阵逐步地逼近目标函数在极小点处的赫森矩阵的逆矩阵。当

成为式(2)表示的阻尼牛顿法迭代公式。这样，当迭代点逼近最优点时，搜索方向就趋于牛顿方向。如能实现这种构想，那就综合了梯度法和牛顿法的优点，不直接计算而是用变化的构造矩阵

去逼近它，使算法更为有效。构造矩阵

，

在迭代过程中是变

化的，称为变尺度矩阵。由于变尺度法的迭代形式与牛倾法类似，不同的是在迭代公式中用

来逼近

，所以又称为“拟牛顿法”，变尺度法的搜索方向，最终要逼近牛顿方向

顿方向。

，故又称为拟牛

实现上述变尺度法的基本思想，关键在于如何产生这一合乎要求的变尺度矩阵下面对此进行重点讨论。

，

? 二、构造变尺度矩阵的基本要求

1.为了使拟牛顿搜索方向朝着目标函

数值下降的方向，必须为对称正定矩阵。证明如下：

若有目标函数f(X}由据梯度的性质，可知搜索方向的点积应大于零

点沿方向具有下降的性质，即，根

与负梯度方向之间的夹角应成锐角，即两者

将代入上式，则有

用矩阵表示为或

这表明变尺度矩阵数值下降方向。

必须是对称正定矩阵才能保证变尺度算法拟牛顿搜索方向是函

2.要求构造的变尺度矩阵式构造下一次迭代的变尺度矩阵

具有简单的迭代形式，能利用本次迭代信息以固定的格

，可以写成

——（4）

式中称为校正短阵。从上式可知，若确定了初始变尺度矩阵

，则可得

；确定

，又可得

(通常取为单位

矩阵I，若再确定度矩阵序列{

?，式（4）就是产生变尺

(k=0，1，2，?)}的基本迭代公式。

3.为使逐次构造的变尺度矩阵须满足拟牛顿条件。

最终能遇近赫森矩阵的逆矩阵，必

所谓拟牛顿条件，可由下面导出。

设f (X)为具有连续的一、二阶偏导数的一般形式的目标函数，为使构造的变尺度矩阵仅使用梯度和其他一些易于获得的信息而最终逼近计算繁琐的赫森矩阵之逆矩阵，可先分析一下赫森矩阵H(X)与函数梯度g=▽f (X)之间的关系。f (X)展开成泰勒级数并仅取到二次项时

该近似二次函数的梯度是

如果取为极值点附近第k+1次迭代点，则有

即

若矩阵为可逆矩阵，则用左乘上式两边，得

——（5）

上式表明与前后两个迭代点的向量差

之间的基本关系。

以及梯度向量差

设迭代过程早己进行到第k+1步，、和、均已在此之前求得，根

据期望能借助前一次迭代的某些结果来构造下一次的变尺度矩阵以及最终逼近赫森矩阵的逆矩阵，则应迫使第k+1次变尺度矩阵

代替式(4)中

，即满足

——（6）

式（6）是构造变尺度矩阵应满足的一个重要条件，通常称为拟牛顿条件或拟牛顿方程。

为简便起见，记，，则拟牛顿条件可写成

——（7）

?

三、DFP法变尺度矩阵递推公式

前已述及，产生变尺度矩阵序列{ (k=0，1，2，?)}采用式（4）的形式，即

可见，在前一次变尺度矩阵阵

给定后，若能确定校正矩阵

的计算公式时又必须使

，则下一个变尺度矩

满足式（7）的拟

就可以确定，而建立校正矩阵

牛顿条件

联立式（4）和式(7)，则有

亦即——（8）

在上式中要直接求解还有困难，因满足上式的矛有无穷多个，实际上建立

的计算公式构成一族算法，校正矩阵取不同的计算公式，就形成各自的变尺度

法。这里介绍W. C. Davidon提出并经过R. Fletcher和M. J. D. Powell修改的求校正矩阵

的公式，即所谓DFP公式。由于

和

都是n×n阶对称矩阵，所以

为如下形式：

也一定是n×n阶对称矩阵。DFP算法取

——（9）

式中，，为待定常数；，为n维待定向量，将上式代入式（8），则有

即——（10）

满足上式的待定向量，有多种取法，现令

——（11）

——（12）

注意到和都是数量，故可取

由式（11）及（12）可以定出

——（13）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库变尺度法在线全文阅读。