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

《第6章 无约束问题的优化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章无约束问题的优化方法§6.1最速下降法和牛顿法6.1.1最速下降法的基本原理、计算步骤和特点基本原理：考虑无约束问题从某一点出发，选择一个目标函数值下降最快的方向，可以尽快达到极小点．1847年法国数学家Cauchy提出了最速下降法．后来，Curry等人作了进一步研究．最速下降方向是目标函数的负梯度方向：最速下降法的迭代公式：取为在点处的最速下降方向：为进行一维搜索的步长，满足：计算步骤：(l)给定初点，允许误差，置.(2)计算搜索方向.(3)若，则停止计算；否则，从出发，沿进行一维搜索，求，使(4

2、)令,置，转步骤（2）.例1解问题初点，.（最优解）第1次迭代：目标函数在点处的梯度令搜索方向89从出发，沿方向进行一维搜索，求步长，即令(一般应采用不精确一维搜索求解)，解得在直线上的极小点：第2次迭代：解得第3次迭代：解得这时有满足精度要求，得到近似解最速下降算法的特点：最速下降算法在一定条件下是收敛的．最速下降法产生的序列是线性收敛的，而且收敛性质与极小点处Hesse矩阵的特征值有关．89定理1:设存在连续二阶偏导数，是局部极小点，Hesse矩阵的最小特征值，最大特征值为，算法产生的序列收敛于点，则

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

4、)设可逆，得到牛顿法的迭代公式产生序列，在适当的条件下，这个序列收敛．例2：解问题：(最优解)目标函数的梯度和Hesse矩阵分别为89取初点.第l次迭代:第2次迭代:继续迭代，得到,,…注3：当牛顿法收敛时，有下列关系：c是某个常数．因此，牛顿法至少2级收敛，收敛速率是很快的．注4：对二次凸函数，用牛顿法求解经1次迭代即达极小点．设有二次凸函数:用极值条件求解：令得到最优解用牛顿法求解：任取初始点，根据牛顿法的迭代公式有以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经有限次迭代必达到极小点．

5、这种性质称为二次终止性．注5:当初始点远离极小点时，牛顿法可能不收敛．牛顿方向不一定是下降方向，经迭代，目标函数值可能上升.即使目标函数值下降，得到的点也不一定是沿牛顿方向的最好点或极小点．对牛顿法进行修正，提出了阻尼牛顿法．2.阻尼牛顿法阻尼牛顿法增加沿牛顿方向的一维搜索，迭代公式:89为牛顿方向.由一维搜索得到:由于阻尼牛顿法含有一维搜索，因此每次迭代目标函数值一般有所下降（绝不会上升）．可以证明，阻尼牛顿法在适当的条件下具有全局收敛性，且为2级收敛．阻尼牛顿法的计算步骤：(l)给定初点，允许误差，置

6、.(2)计算，.(3)若，则停止计算；否则，令（4）从出发，沿进行一维搜索，求，使(5)令,置，转步骤（2）.3.牛顿法的进一步修正原始牛顿法和阻尼牛顿法有共同缺点：（1）可能出现Hesse矩阵奇异的情形，因此不能确定后继点；（2）即使非奇异，也未必正定，因而牛顿方向不一定是下降方向，就可能导致算法失效．例3:用阻尼牛顿法求解：取初始点.在点处，有，牛顿方向从出发，沿作一维搜索．令,则.用阻尼牛顿法不能产生新点，而点并不是问题的极小点．原因在于Hesse矩阵非正定．为使牛顿法从任一点开始均能产生收敛于解集

7、合的序列，要做进一步修正,克服Hesse矩阵非正定．考虑（1）式，记搜索方向，得到89(2)阻尼牛顿法所用搜索方向是上述方程的解：解决Hesse矩阵非正定问题的基本思想：修正，构造一个对称正定矩阵.在（2）中，用取代矩阵,得到方程(3)解此方程，得到在点处的下降方向构造矩阵的方法之一:令是一个适当的正数．只要选择得合适，就是对称正定矩阵．注6:当为鞍点时，有及不定此时（3）式不能使用．这时可取为负曲率方向：当不定时，这样的方向必定存在，而且沿此方向进行一维搜索必能使目标函数值下降．§6.2共轭梯度法6.2

8、.1共轭方向的基本原理和定理共轭梯度法是基于共轭方向的一种算法．定义1：设是对称正定矩阵，若中的两个方向和满足则称这两个方向关于共轭，或称它们关于正交．若，，…，是中个方向，它们两两关于共轭，即满足则称这组方向是共轭的，或称它们为的个共轭方向．注1：如果为单位矩阵，则两个方向关于共轭等价于两个方向正交．共轭是正交概念的推广．89注2：如果是一般的对称正定矩阵，和关于共轭，也就是方向与方向正交．共轭的几何意义（以正定二次函数为例