第6章 无约束问题的优化方法.doc

第6章无约束问题的优化方法
§6.1最速下降法和牛顿法
6.1.1最速下降法的基本原理、计算步骤和特点
基本原理：
考虑无约束问题

从某一点出发，选择一个目标函数值下降最快的方向，可以尽快达到极小点．
1847年法国数学家Cauchy提出了最速下降法．后来，Curry等人作了进一步研究．
最速下降方向是目标函数的负梯度方向：

最速下降法的迭代公式：

取为在点处的最速下降方向：

为进行一维搜索的步长，满足：

计算步骤：
(l)给定初点，允许误差，置.
(2)计算搜索方向.
(3)若，则停止计算；否则，从出发，沿进行一维搜索，求，使

(4)令,置，转步骤（2）.
例1解问题

初点，.（最优解）
第1次迭代：目标函数在点处的梯度

令搜索方向

从出发，沿方向进行一维搜索，求步长，即

令(一般应采用不精确一维搜索求解)，解得

在直线上的极小点：
第2次迭代：

解得

第3次迭代：

解得

这时有

满足精度要求，得到近似解
最速下降算法的特点：
最速下降算法在一定条件下是收敛的．
最速下降法产生的序列是线性收敛的，而且收敛性质与极小点处Hesse矩阵的特征值有关．
定理1:设存在连续二阶偏导数，是局部极小点，Hesse矩阵的最小特征值，最大特征值为，算法产生的序列收敛于点，则目标函数值的序列以不大于的收敛比线性地收敛于.
最速下降法存在锯齿现象：

从局部看，最速下降方向确是函数值下降最快的方向．
从全局看，由于锯齿现象的影响，即使向着极小点移近不太大的距离，也要经历不小的弯路，使收敛速率大为减慢．
注1：最速下降法并不是收敛最快的方法，从全局看，它的收敛是比较慢的．
注2：最速下降法一般适用于计算过程的前期迭代或作为间插步骤．
当接近极小点时，使用最速下降法达到迭代终止，这样做并不有利．
6.1.2牛顿法的基本原理、计算步骤和特点
1.牛顿法
在点的二阶Taylor展开为

求的平稳点，令,即
(1)
设可逆，得到牛顿法的迭代公式

产生序列，在适当的条件下，这个序列收敛．
例2：解问题：(最优解)
目标函数的梯度和Hesse矩阵分别为

取初点.
第l次迭代:

第2次迭代:

继续迭代，得到
,,…
注3：当牛顿法收敛时，有下列关系：

c是某个常数．因此，牛顿法至少2级收敛，收敛速率是很快的．
注4：对二次凸函数，用牛顿法求解经1次迭代即达极小点．设有二次凸函数:

用极值条件求解：令
得到最优解

用牛顿法求解：任取初始点，根据牛顿法的迭代公式有

以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经有限次迭代必达到极小点．这种性质称为二次终止性．
注5:当初始点远离极小点时，牛顿法可能不收敛．
牛顿方向不一定是下降方向，经迭代，目标函数值可能上升.
即使目标函数值下降，得到的点也不一定是沿牛顿方向的最好点或极小点．
对牛顿法进行修正，提出了阻尼牛顿法．
2.阻尼牛顿法
阻尼牛顿法增加沿牛顿方向的一维搜索，迭代公式:

为牛顿方向.
由一维搜索得到:

由于阻尼牛顿法含有一维搜索，因此每次迭代目标函数值一般有所下降（绝不会上升）．可以证明，阻尼牛顿法在适当的条件下具有全局收敛性，且为2级收敛．
阻尼牛顿法的计算步骤：
(l)给定初点，允许误差，置.
(2)计算，.
(3)若，则停止计算；否则，令

（4）从出发，沿进行一维搜索，求，使

(5)令,置，转步骤（2）.
3.牛顿法的进一步修正
原始牛顿法和阻尼牛顿法有共同缺点：
（1）可能出现Hesse矩阵奇异的情形，因此不能确定后继点；
（2）即使非奇异，也未必正定，因而牛顿方向不一定是下降方向，就可能导致算法失效．

例3:用阻尼牛顿法求解：

取初始点.在点处，有
，
牛顿方向
从出发，沿作一维搜索．
令,则.
用阻尼牛顿法不能产生新点，而点并不是问题的极小点．原因在于Hesse矩阵非正定．
为使牛顿法从任一点开始均能产生收敛于解集合的序列，要做进一步修正,克服Hesse矩阵非正定．
考虑（1）式，记搜索方向，得到
(2)
阻尼牛顿法所用搜索方向是上述方程的解：

解决Hesse矩阵非正定问题的基本思想：
修正，构造一个对称正定矩阵.
在（2）中，用取代矩阵,得到方程
(3)
解此方程，得到在点处的下降方向

构造矩阵的方法之一:
令

是一个适当的正数．只要选择得合适，就是对称正定矩阵．
注6:当为鞍点时，有
及不定
此时（3）式不能使用．
这时可取为负曲率方向：

当不定时，这样的方向必定存在，而且沿此方向进行一维搜索必能使目标函数值下降．
§6.2共轭梯度法
6.2.1共轭方向的基本原理和定理
共轭梯度法是基于共轭方向的一种算法．
定义1：设是对称正定矩阵，若中的两个方向和满足

则称这两个方向关于共轭，或称它们