《无约束极值问题》PPT课件

《《无约束极值问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一类是使用导数的方法，也就是根据目标函数的梯度（一阶导数）有时还要根据Hesse矩阵（即二阶导数）所提供的信息而构造出来的方法，就称为梯度方法。如：最速下降法，Newton法，共扼梯度法和变尺度法。另一类是不使用导数的方法，统称为直接方法。前者收敛速度快，但计算复杂（一阶，二阶导数）后者不用导数，适应性强，但收敛速度慢。因此再可以求得目标函数导数信息时，尽可能用另一方法，而若求目标函数导数很困难，或者根本不存在导数时，就用后一种方法.无约束最优化可以分为两大类：无约束极值问题一最速下降法最速下降法是求多元函数极值的最古老的数值算法

2、，它直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。其缺点是收敛速度较慢。（一）算法思想：假定我们已经迭代到第K次，已有从出发进一步迭代。§3最速下降法和共轭梯度法显然应沿下降方向进行，而下降最快的方向是为了使目标函数沿此方向下降的最多，　　沿此方向进行直线搜索，从而得到第k+1次迭代点　　即其中步长因子　　满足1选定初始点，并给定精度，令（二）算法步骤2若，则停止，否则令3由求出最佳步长。4令返回第2步则得新的迭代点这说明其前后两个搜索方向总是垂直的，这就造成了最优步长的最速下降法逼近

3、极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路。因此反而是不好的。（三)锯齿现象：最速下降法在两个相邻点之间的搜索方向对于正定二次函数是正交的，因而最速下降法向最小点逼近是曲折前进的。这种现象称为锯齿现象。除最特殊的目标函数和极特殊的初始点外，这种现象都会发生。这是因为最速下降法的搜索方向正是从而知：=0为了清除最优步长最速下降法中两

4、个搜索方向正交的不良后果，人们发明了不少方法，如：（1）选择不同初始点。例如：对问题：取初点则=令得然后再从开始新的迭代，经过10次迭代，得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点时，步长很小，目标函数值下降很慢。如果不取初点为而取虽然后一初点较前一初点离最优点远，但迭代中不含上面出现的锯齿现象。这时：可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长λ的方法，称为固定步长最速下降法。只要λ充分

5、小，总有：但λ到底取多大，没有统一的标准，λ取小了，收敛太慢，而λ取大了，又会漏掉极小点。一步就得到了极小点。（2）采用精确的一维搜索：即用一维搜索求出的步长为时，我们不取，而用的一个近似值作为,如取=0.9这样可使相邻两个迭代点处的梯度不正交，从而改变收敛性。首先考虑二次函数的无约束极小问题二共轭梯度法令将(1)化为显然，（3）式经n次一维搜索可得最优解为对角阵1定义：设为n阶正定阵，若n维方向满足（一）共轭方向则称是共轭的。2性质：设为n阶正定阵，若是共轭的，则必线性无关1共轭梯度法思想：将共轭性与最速下降方法结合，利用已知点

6、处的梯度构造一组共轭方向，并沿此组方向进行搜索，求出极小点。适用范围：凸函数（二）共轭梯度法2FR共轭梯度法考虑问题：其中：为对称正定阵（1）算法步骤：1任选初始点令2若，则停止；否则令其中：3k=k+1返回2用FR共轭梯度法求解（2）算法举例：解：第一次迭代第二次迭代共轭搜索方向：非二次型的共轭梯度法设为某一严格凸函数，具有二阶连续偏导用二阶泰勒展开近似表示迭代公式：(一）算法的基本思路：考虑到到的确迭代过程，在点处对Tayloy展开：如果目标函数在上具有二阶导数，共Hesse矩阵正定，并且表达式为量式时，就可使用下述Newto

7、n法。这种方法收敛速度很快。其缺点是计算量大，二是很赖于初始点的选择。§4Newton法和拟牛顿法一、Newton法若Hesse矩阵正定则存在，的极小点为当时为的近似极小点，记当时为的精确极小点。1选定初始点，并给定精度，令算法步骤2若，则停止，否则转33求出牛顿方向5令返回第2步4求新的迭代点例：用Newton法求的极小点。初点解：代入Newton迭代公式得：即为问题的最优点1。选定初始点计算2。计算3。由方程（二）算法过程：以知目标函数,梯度，Hesse阵，给定终止准则H及控制误差限4。令5。判别终止准则H是否满足。若满足，则

8、打印最优解：否则，转2。在此算法中，没有直接用Newton迭代公式：而是通过3。解的线性方程进行。因为这样可以减少计算工作量，而且解线性方程组以有标准程序。上面我们看到Newton法用于具有对称正定矩阵的二次函数时，一次迭代即可得到极小点。而对于一