基木原理：探究迭代算法的收敛速度

1.尺度矩阵的概念

变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。尺度变换技巧能显著地改迸几乎所有极小化方法的收敛性质。如在例4-1中用最速下降法求f^（X）=x²₁+25x²₂的极小值时，需要迸行10次迭代才能达到极小点X^*=（0，0）^T。但是若做变换

y₁=x₁

y₂=5x₂

即把x₂的尺度放大5倍，就可以将等值线为椭圆的函数f^（X）变换成等值线为圆的函数ψ（Y）=y²₁+y²₁从而消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。

对于一般二次函数

如果迸行尺度变换

X←QX

则在新的坐标系中，函数f^（X）的二次项变为

选择这样变换的目的，仍然是为了降低二次项的偏心程度。若矩阵G是正定的，则总存在矩阵Q使

Q^TGQ=I（单位矩阵）

从而将函数偏心度变为零。

用Q^-1右乘上述等式两边，得

Q^TG=Q^-1

然后用Q左乘上述等式两边，得

QQ^TG=I

QQ^T=G^-1

这说明二次函数矩阵G的逆矩阵，可以通过尺度变换矩阵Q来求得。这样，牛顿法迭代过程中的牛顿方向便可写成

S^（k）=-G^-1▽f（X^（k））=-QQ^T▽f（X^（k））

例如在例4-1中，二次函数

其中

若取

的变换X←QX

则在变换后的坐标系中，矩阵G变为(www.xing528.com)

从而求得

这与在例4-1中所得结果一致，而巨只需通过一次迭代即可求得极小点X^*=（0，0）^T和极小值f（X^*）=0。

比较牛顿法迭代公式

X^（k+1）=X^（k）-α^（k）QQ^T▽f（X^（k））和梯度法迭代公式

X^（k+1）=X^（k）-α^（k）▽f（X^（k））

可以看出，差别在于牛顿法中多了QQ^T部分。QQ^T实际上是在X空间内测量距离大小的一种度量，称作尺度矩阵M：

M=QQ^T

如在未迸行尺度变换前，向量X长度的概念是

变换后向量X对于M尺度下的长度

这样的长度定义，在确定“长度”这个纯量大小时，使得某些方向起的作用比较大、另一些方向起的作用比较小。为使这种尺度有用，必须对一切非零向量的X均有X^TMX＞0，即要求尺度矩阵M正定。既然牛顿法迭代公式可用尺度变换矩阵M=QQ^T表示出来，即

X^（k+1）=X^（k）-α^（k）M▽f（X^（k））

它和梯度法迭代公式只差一个尺度矩阵M，那么牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面（或超球面），使设计空间中任意点处函数的梯度都通过极小点，用最速下降法只需一次迭代就可达到极小点。这就是对变换前的二次函数，在使用牛顿方法时，由于其牛顿方向直接指向极小点，因此只需一次迭代就能找到极小点的原因所在。

2.变尺度矩阵的建立

对于一般函数f^（X），当用牛顿法寻求极小点时，其牛顿迭代公式为

X^（k+1）=X^（k）-α^（k）（H^（k））-1▽f（X^（k））（k=0，1，2，…）

为了避免在迭代公式中计算黑塞矩阵的逆矩阵（H^（k））^-1，可用在迭代中逐步建立的变尺度矩阵

M^（k）≡M（X^（k））

来替换（H^（k））^-1，即构造一个矩阵序列｛M^（k）｝来逼近黑塞逆矩阵序列｛（H^（k））^-1｝，每迭代一次尺度就改变一次，这正是“变尺度”的含义。这样，上式变为

X^（k+1）=X^（k）-α^（k）M^（k）▽f（X^（k））（k=0，1，2，…） （4-20）

其中α^（k）是从X^（k）出发，沿方向

S^（k）=-M^（k）▽f（X^（k））

做一维搜索而得到最佳步长。这个迭代公式代表面很广，例如当M^（k）=I（单位矩阵）时它就变成最速下降法。以上就是变尺度法的基本思想。

为了使变尺度矩阵M^（k）确实与（H^（k））^-1近似，并具有容易计算的特点，必须对M^（k）附加某些条件。