第十八章 无约束最优化的梯度方法

高等工程数学

第十八章 无约束最优化的梯度方法

minf(z),f:Rn R1,目的是在Rn找一点z*使 z∈Rn均有f(Z*)≤f(z),z*

称为此无约束最优化问题的全局最优点。然而在实际中，大多数最优化方法只能求到局部最优点，即在Rn中可找到一点Z*使得在Z*的某个邻域中有f(z*)≤f(z)。但在实际中，可以根据问题的意义来判断求得的局部极小点是否为全局最优点，无约束最优化可以分为两大类:

一类是使用导数的方法，也就是根据目标函数的梯度（一阶导数）有时还要根据hesse矩阵（即二阶导数）所提供的信息而构造出来的方法，称为梯度方法。如：最速下降法，Newton法，共轭梯度法和变尺度法。

另一类是不使用导数的方法，统称为直接方法。前者收敛速度快，但计算复杂（一阶，二阶导数）后者不用导数，适应性强，但收敛速度慢。因此在可以求得目标函数导数信息时，尽可能用前一方法，而若求目标函数导数很困难，或者根本不存在导数时，就用后一种方法。

18.1 最速下降法

最速下降法是求多元函数极值的最古老的数值算法，它直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。其缺点是收敛速度较慢。

18.1.1 算法思路 为求解minf(z),(z Rn)

假定我们已经迭代到第 K次，即已有

z，从z出发进一步迭代。

(图18.1.1 )

显然应沿下降方向进行( f(zk)Tpk 0.则pk为下降方向），而下降最快的方向是pk f(zk)，为使目标函数沿此方向下降的最多，沿此pk方向进行直线搜索，从而得到第k+1次迭代点zk 1，即zk 1 zk tk f(zk)。其中步长因子tk满足f zk-tk f(zk) minf zk-t f zk 。

t R

按我们以前的记号，上面两式可记为：

zk 1 LS（zk,- f(zk)) （18.1.1）

当给定初始点（可任选），就可产生一个序列z0,z1,z2,......。在f(z)满足一定条件时，此序列{zk}必收敛于的f(z)极小点z*。

称以（18.1.1）为迭代公式的算法为最速下降法。