基木原理及最速下降法在优化中的应用

优化设计是追求目标函数值f（X）最小，因此一个很自然的想法是从某点X出发，其搜索方向S取该点的负梯度方向-▽f（X）（最速下降方向），使函数值在该点附近的范围内下降最快。按此规律不断走步，形成以下迭代的算法：

由于最速下降法是以负梯度方向作为搜索方向，所以最速下降法又称为梯度法。

为了使目标函数值沿搜索方向-▽f（X）能获得最大的下降值，其步长因子应取一维搜索的最佳步长α^（k）。即有

根据一元函数极值的必要条件和多元复合函数求导公式，即有

φ′（α）=-|▽f（X^（k）-α^（k）▽f（X^（k）））|^T▽f（X^（k））=0

即 ［▽f（X^（k+1））^]T▽f（X^（k））=0

或写成 （S^（k+1））^TS^（k）=0

由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在最速下降法中，迭代点向函数极小点靠近的过程，走的是曲折的路线。这一次搜索方向与前一次的搜索方向互相垂直，形成“之”宇形的锯齿现象，见图4-1。从直观上可以看到，在远离极小点的位置，每次迭代可使函数值有较多的下降。可是在接近极小点的位置，由于锯齿现象使每次迭代行迸的距离缩短，因而收敛速度减慢。这种情况似乎与“最速下降”的名称相矛盾，其实不然，这是因为梯度是函数的局部性质。从局部上看，在一点附近函数的下降是快的，但从整体上看则走了许多弯路，因此函数的下降并不算快。

图4-1 最速下降法的搜索路径

若将4.10节例4-1中的目标函数f（X）=x²₁+25x²₂引入变换

y₁=x₁

y₂=5x₂

则函数f（X）变为

ψ（Y）=y²₁+y²₂

其等值线就由一族椭圆（图4-2）变成一族同心圆（图4-3），仍从X^（0）=（2，2）^T即Y^（0）=（2，10）^T出发迸行最速下降法寻优。此时有

图4-2 等值线为椭圆的迭代过程

图4-3 等值线为圆的迭代过程

沿负梯度-▽ψ（Y^（0））方向迸行一维搜索，有

(www.xing528.com)

α^（0）为一维搜索最佳步长，可由极值条件算出

从而算得第一次走步后设计点的位置及其相应的目标函数值为

可见经过坐标变换后，只需经过一次迭代，就可找到最优解

X^*=（0，0）^T

f（X^*）=0

比较以上两种函数形式

可以看出它们中间的对角形矩阵不同，同时f（X）的等值线为一族椭圆，而ψ（Y）的等值线为一族同心圆。这是由于经过尺度变换

y₁=x₁

y₂=5x₂

即x₁轴的度量不变，而把x₂轴的度量放大5倍，从而把等值线由椭圆变成圆了，这说明上面两个二次型函数的对角形矩阵刻画了椭圆的长、短轴，它们是表示度量的矩阵或者是表示尺度的矩阵。最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估计式上看出来。在适当条件下，有

式中，M为f（X）的黑塞矩阵最大特征值上界；m为其最小特征值下界。

对于等值线为椭圆的二次型函数f（X）=x²₁+25x²₂，其黑塞矩阵，

两个特征值分别为λ₁=2，λ₂=50。因此m=2，M=50，从而有

可见等值线为椭圆的长、短轴相差越大，收敛就越慢。而对等值线为圆的二次函数ψ（Y）=y²₁+y²₂，其黑塞矩阵，两个特征值相等，即λ₁=λ₂=2，因此m=M=2，将其代入式（4-4），有

得 Y^（k+1）=Y^*

即经过一次迭代便可达到极值点。

当相邻两个迭代点之间满足关系式（4-4）时（右边的系数为小于等于1的正常数），我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速度的迭代法。

最速下降法是一个求解极值问题的古老算法，早在1847年就已由柯西（Cauchy）提出。此法直观、简单。由于它采用了函数的负梯度方向作为下一步的搜索方向，所以收敛速度较慢，越是接近极值点收敛越慢，这是它的主要缺点。应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其他无约束优化方法配合使用。特别是一些更有效的方法都是在对它改迸后，或在它的启发下获得的，因此最速下降法仍是许多有约束和无约束优化方法的基础。