无约束极值问题.ppt

《无约束极值问题.ppt》由会员分享，可在线阅读，更多相关《无约束极值问题.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、：凸函数（二）共轭梯度法2 FR共轭梯度法考虑问题：其中：为对称正定阵（1）算法步骤：1 任选初始点 令2 若 ，则停止；否则令其中：3 k=k+1 返回2用FR共轭梯度法求解（2）算法举例：解：第一次迭代第二次迭代共轭搜索方向：非二次型的共轭梯度法设为某一严格凸函数，具有二阶连续偏导用二阶泰勒展开近似表示迭代公式：(一）算法的基本思路：考虑到 到 的确迭代过程，在 点处对 Tayloy展开：如果目标函数在上具有二阶导数，共Hesse矩阵正定，并且表达式为量式时，就可使用下述Newton法。这种方法收敛速度很快。其缺点是计算量大，二是很赖于初始点的选择。4 Newton法和拟牛顿法一、一、Ne

6、wton法法若Hesse矩阵正定则存在，的极小点为当时为的近似极小点，记当时为的精确极小点。1 选定初始点 ，并给定精度 ，令算法步骤算法步骤2 若 ，则停止，否则转33 求出牛顿方向 5令 返回第2步4 求新的迭代点例：用Newton法求的极小点。初点解：代入Newton迭代公式得：即为问题的最优点1。选定初始点 计算2。计算3。由方程（二）算法过程：以知目标 函数 ,梯度 ，Hesse阵 ，给定终止准则H及控制误差限4。令5。判别终止准则H是否满足。若满足，则打印最优解：否则，转2。在此算法中，没有直接用Newton迭代公式：而是通过3。解的线性方程进行。因为这样可以减少计算工作量，而且解

7、线性方程组以有标准程序。上面我们看到Newton法用于具有对称正定矩阵的二次函数时，一次迭代即可得到极小点。而对于一般的具有对称正定Hesse矩阵的函数，在极小点附近近似地呈现为二次函数，所以可以想象Newton法在解点附近具有较高的收敛速度。（三）Newton法的缺点1 要计算 2 即要非奇异为正定时，该方法才为下降算法为正定时，3的计算量也很大 因为则此逆矩阵为，而例例:解：解：它的极小在t=0达到,此时Newton法不能产生新点,而 不是极小点,起原因在于 不正定,即 不恒为正,为了使Newton法适应于 不是正定的,甚至奇异的情形,必须对Newton法作进一不修正.Newton法和阻尼

8、Newton法有共同缺点：一、可能出现Hesse矩阵奇异的情形，因此不能确定后继点；二、即使Hesse矩阵非奇异，也未必正定，因而New他on方向不一定是下降向，这就可能导致算法失效 由于阻尼Newton法含有较搜索，因此，每次迭代目标函数值一般有所下降(决不会上升)可以证明，阻尼Newton法在适当条件下具有全局收敛件，且为二阶收敛例解：二、拟牛顿法为了克服牛顿法的缺点，提出了用不包含二阶导数的矩阵替代 DPF法构造Hesse逆矩阵的最早的，最巧妙的一种格式，由Davidon提出的，后来由Fletcher和Powell作了改进，称为DPF法，又称变尺度法公式：迭代步骤：1 给定2 令4若则停

9、止为近似最优解。否则3计算5转66若则令返回2，否则转77 由公式计算返回3例：用DPF法求解问题解：同理求出最佳步长为极小值点5模式搜索法（步长加速法）z模式搜索法是由Hooke和Jeeves 1961年提出的，因此又称为HookeJeeves方法其基本思想，从几何上讲，是寻找具有较小函数值的“山谷”，力图使迭代产生的序列沿“山谷”逼近极小点算法从初始基点开始，包括两种类型的移动，这就是探测移动（exploratogy move)和模式移动(panern move)探测移动依次沿n个坐标轴进行，用以确定新的基点和有利于函数值F降的方向模式移动沿相邻两个基点连线方向进行，试图顺着“山谷”使函数值更快减少两种移动交替进行第一轮探测移动结束再沿以为基点，沿进行第一轮模式移动记