Matlab研究最速下降法求解无约束最优化问题的一类修正方法(2)
1. 最速下降法的介绍
最速下降法是求解无约束最优化问题的算法中最为古老但又相当根本的一种数值方法. 它的迭代过程十分简单，使用方便，并且又是理解一些其他的最优化方法的基础，最先是在1847年由法国数学家柯西(Cauchy)提出的[6].
1.1 最速下降法的基本思想
假设考虑的无约束最优化问题为 ，
其中 表示一阶连续可微函数的全体.
设在第 步得到一个 ，目标函数 在 附近连续可微，且∇ ≠ 将 在 处按照Taylor级数展开
= ,记 ,其中 >0, 是一个确定的方向向量.上式可以写为 .
易知，若向量 满足 ,则 是函数 在 处的下降方向，并且在所有满足 的方向 中，若 越小，则 下降的幅度就越大.
如果将上式写成
，可知 越大，则 下降的幅度就越大. 由 .
其中 是向量 与向量 之间的夹角.可知，当 固定时，取 ，也即取 =-∇ 时，-∇ 达到最大值 . 因而 在点 处下降的幅度最大. 故取搜索方向 =-∇ ，这种方法即为最速下降法，其迭代格式为
， 由线性搜索确定[8].
1.2 最速下降法的具体步骤
最速下降法的具体步骤如下：
(1)选定一个初始点 并给定精确要求 >0，令k=1.
(2)若 ，则停止， = ；否则，令 =-∇ .
(3)在 处沿方向 作一文线性搜索，得 ，k：=k+1，转步骤 (2).
若在第(3)步中采用精确线性搜索，即
，就有 =0.
此式表明 与 是正交的[9].
1.3 最速下降法的局限性
最速下降法在一定条件下是收敛的.我们有如下定理.
定理1[12] 设 是连续可微实函数，解集合 ={ | }，最速下降算法产生的序列{ }含于某个紧集，则序列{ }的每一个聚点 .
最速下降法产生的序列是线性收敛的，并且收敛性质与极小点处的Hesse矩阵 的特征值相关. 下面给出定理2.
定理2[12] 设 存在连续二阶偏导数， 是局部极小点，Hesse矩阵 的最小特征值 ，最大特征值为 ，算法产生的序列 收敛于 ，则目标函数值的序列 以不大于 的收敛比线性地收敛于 .
在上述定理中，若令 = ，则
，
是对称正定矩阵 的条件数.
这个定理表明，Hesse矩阵的条件数越小，目标函数值的序列 收敛越快；Hesse矩阵的条件数越大，序列收敛越慢.
容易证明，用最速下降算法来极小化目标函数时，相邻的搜索方向是正交的.
令 ， .
为求从 出发沿着方向 的极小点，令 ，由此得出方向 与 是正交的. 这表示迭代产生的序列 所沿路径是“之”字形的[14]. 当 靠近极小点 时，每次迭代移动的步长十分小，那么如此就显现出“锯齿现象”，是以影响了收敛速度[13].
当Hesse矩阵 的条件数比较大时，“锯齿现象”的影响极为严重. 对此可作以下剖析：
一般来说，在极小点附近，目标函数是可以用二次函数来近似替代的，其等值面近似于一个椭圆面，长轴和短轴分别在对应的最小特征值和最大特征值的特征向量的方向上，其大小与特征值的平方根成反比例[15]. 最小特征值与最大特征值相差越大，椭圆面就越扁，这样使得一文线性搜索是沿着斜长谷来进行的. 于是，当条件数较大时，为了使迭代点充分地靠近极小点，就需要走很大的弯路，那么，计算效率大大降低.
综上所述，最速下降方向反映了目标函数的一种局部性质. 从局部上来看，选取最速下降方向进行一文线性搜索是有利的，因为最速下降方向的确是函数值下降最快的方向. 但从全体上来看，因为“锯齿现象”的影响，纵使向着极小点移动不太大的距离，亦然要经历不小的弯路，是以收敛速率大大减慢. 这样来看，最速下降法并非收敛最快的方法，相反，从全体来看，它的收敛是比较迟缓的. 那么，最速下降法一般适用于计算过程的前期迭代或作为间插环节. 当靠近极小点时，再利用最速下降法，试图用这种方法达到迭代的终止，这样做并非有益的[10].
上一篇：隐函数在数学分析中的应用探讨
下一篇：第二型曲面积分的解法探讨