最优化理论与方法ppt课件.ppt

《最优化理论与方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、使用导数的无约束最优化方法策略表现形式方法线性近似最速下降法二次近似Newton法共轭梯度法用布鲁丹（Broyden）族或黄（Huang）族拟Newton法修正公式最速下降法（SteepestMethod）考虑无约束问题下降算法对于下降方向的要求：最速下降法的要求：最速下降法（SteepestMethod）最速下降法的计算步骤：（1）给出初始点和精度；（2）计算。如果，则令，停止；否则，转（3）；（3）令，求解得到；（4）令，转（2）。最速下降法（SteepestMethod）对于最速下降法的几点说

2、明：（1）锯齿现象：目标函数在负梯度方向下降得最快只是局部性质。（2）改进策略：在计算的开始阶段使用最速下降法，在迭代数次后，改用其他算法。最速下降法（SteepestMethod）二次函数情形下最速下降法的收敛速度定理考虑无约束最优化问题其中G是n阶对称正定矩阵。和分别是G的最大特征值和最小特征值。设是问题的解点，则最速下降法至少具有线性的收敛速度，并且满足下面的界：最速下降法（SteepestMethod）对于定理的说明：（1）在上面定理中，如果考虑的是如下一般二次目标函数，其中G是n阶对称正定

3、矩阵，则有类似的证明方法证明定理同样成立。（2）当目标函数是二阶连续可微的一致凸函数时，由上章的推导可知，采用精确线性搜索的最速下降法产生的迭代点列至少是线性收敛的。最速下降法（SteepestMethod）定理：设最速下降法产生的点列收敛到，在附近二阶连续可微，且，正定，则线性收敛到，即其中M和m满足，和分别是的最小特征值和最大特征值。Newton法及其改进Nowton法的主要内容：（1）牛顿法的基本思想（2）阻尼牛顿法（3）带保护措施的阻尼牛顿法（4）吉尔-默里稳定牛顿法（5）信赖域方法（一）N

4、ewton法及其改进（1）牛顿法的基本思想：在目标函数的极小点的近似点附近将二阶Tayler展开，用展开的二次函数去逼近，将这个二次函数的极小点作为的一个新的近似点依次下去，用一系列二次函数的极小点去逼近的极小点。Newton法及其改进设二次连续可微，则在处的二次近似为：令即Newton法及其改进若正定（对称），则存在。Newton迭代公式Newton方向：Newton法及其改进定理（Newton法收敛定理）设二阶连续可微，是的局部最优解，，正定，Hesse矩阵满足Lipschitz条件：即存在，使

5、得对所有的i，j，有其中是Hesse矩阵的元素。则当初始点充分靠近时，对于一切的k，牛顿迭代公式有定义，并且所得迭代点列收敛到，并且具有二阶收敛速度。Newton法及其改进牛顿法面临的主要困难：（1）很难检验初始点是否靠近最优解因而不能保证Hesse矩阵是否正定，得到的方向是下降方向，迭代点列的收敛性及收敛速度。（2）牛顿法对目标函数要求高（二阶连续可微），且需较多的存储单元，每次迭代均要进行矩阵求逆运算。（3）二次终止性：对于二次凸函数，用牛顿法求解，经1次迭代即达极小点。Newton法及其改进（

6、2）阻尼牛顿法：在标准牛顿法增加了沿牛顿方向的直线搜索。阻尼牛顿法在适当的条件下具有全局收敛性，且为2级收敛。Newton法及其改进阻尼牛顿法的缺点：阻尼牛顿法克服了牛顿法要求初始点充分靠近目标函数的极小点的缺点，但只有当目标函数的Hesse矩阵处处正定时，才具有全局收敛性。如果Hesse矩阵不是处处正定，当初始点远离局部极小点时，Hesse矩阵可能不正定，这时Hesse矩阵可能奇异也可能是非奇异。若Hesse矩阵奇异，求解方向的方程组可能无解，或者虽然有解，但求出的方向不能使迭代过程继续进行下去；

7、若Hesse矩阵非奇异，但不正定，则求得的方向可能不是下降方向。Newton法及其改进例：取，则，，显然，是可逆矩阵，但不正定。其逆矩阵为于是，沿此方向进行线性搜索，，其极小点为，因此迭代不能继续进行下去。Newton法及其改进（3）带保护措施的阻尼牛顿法（Goldstein和Price，1967）假设可逆，若正定，否则，Newton法及其改进（4）吉尔-默里稳定牛顿法（Gill和Murray，1974）定义：设在开集D上二次连续可微，（i）如果Hesse矩阵至少有一个负特征值，则叫做不定点。（ii

8、）如果X是一个不定点，若方向d满足则称d为在X处的负曲率方向。Newton法及其改进负曲率方向的性质：（1）若方向d为负曲率方向，则也是负曲率方向。（2）在鞍点处，负曲率方向必是下降方向；（3）在一般点处，若负曲率方向d满足：，则d与均是下降方向；，则d是下降方向；，则是下降方向。Newton法及其改进Gill-Murray稳定牛顿法的基本思想：当Hesse矩阵在迭代点处为不定矩阵时，对其进行强迫正定的分解；当趋于零时，采用负曲率方向使函数值下降。构造一个对称正定矩阵