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

一类是使用导数的方法，也就是根据目标函数的梯度（一阶导数）有时还要根据Hesse矩阵（即二阶导数）所提供的信息而构造出来的方法，就称为梯度方法。如：最速下降法，Newton法，共扼梯度法和变尺度法。另一类是不使用导数的方法，统称为直接方法。 前者收敛速度快，但计算复杂（一阶，二阶导数）后者不用导数，适应性强，但收敛速度慢。因此再可以求得目标函数导数信息时，尽可能用另一方法，而若求目标函数导数很困难，或者根本不存在导数时，就用后一种方法.,无约束最优化可以分为两大类：,无约束极值问题,一 最速下降法 最速下降法是求多元函数极值的最古老的数值算法，它直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。其缺点是收敛速度较慢。 （一）算法思想： 假定我们已经迭代到第 K次，已有 从 出发进一步迭代。,3 最速下降法和共轭梯度法,显然应沿下降方向进 行 ，而下降最快的方向是,为了使目标函数沿此方向下降的最多， 沿此方向进行直线搜索，从而得到第k+1次迭代点 即 其中步长因子 满足,1 选定初始点 ，并给定精度 ，令,（二） 算法步骤,2 若 ，则停止， 否则令,3 由 求出最佳步长 。,4 令 返回第2步,则得新的迭代点,这说明其前后两个搜索方向总是垂直的，这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。 这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路。因此反而是不好的。,（三)锯齿现象： 最速下降法在两个相邻点之间的搜索方向对于正定二次函数是正交的，因而最速下降法向最小点逼近是曲折前进的。,这种现象称为锯齿现象。,除最特殊的目标函数和极特殊的初始点外，这种现象都会发生。这是因为最速下降法的搜索方向正是 从而知： =0,为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发明了不少方法，如：,（1）选择不同初始点。,例如：对问题： 取初点,则,=,令,得,然后再从 开始新的迭代，经过10次迭代，得最优解 计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点时，步长很小，目标函数值下降很慢。 如果不取初点为 而取 虽然后一初点较前一初点离最优点 远，但迭代中不含上面出现的锯齿现象。这时：,可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事,对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长的方法，称为固定步长最速下降法。 只要充分小，总有： 但到底取多大，没有统一的标准， 取小了，收敛太慢，而取大了，又会漏掉极小点。,一步就得到了极小点。,（2）采用精确的一维搜索：即用一维搜索求出的步长为 时，我 们不取 ，而用 的一个近似值作为 ,如取 =0.9 这样可使相邻两个迭代点处的梯度不正交，从而改变收敛性。,首先考虑二次函数的无约束极小问题,二 共轭梯度法,令,将(1)化为,显然，（3）式经n次一维搜索可得最优解,为对角阵,1 定义：设 为n阶正定阵，若n维方向 满足,（一）共轭方向,则称 是 共轭的。,2 性质：设 为n阶正定阵，若 是 共轭的，则必线性无关,1共轭梯度法思想： 将共轭性与最速下降方法结合，利用已知点处的梯度构造一组共轭方向，并沿此组方向进行搜索，求出极小点。 适用范围：凸函数,（二）共轭梯度法,2 FR共轭梯度法,考虑问题：,其中： 为对称正定阵,（1）算法步骤：,1 任选初始点 令,2 若 ，则停止；否则,令,其中：,3 k=k+1 返回2,用FR共轭梯度法求解,（2）算法举例：,解：,第一次迭代,第二次迭代,共轭搜索方向：,非二次型的共轭梯度法,设,为某一严格凸函数，具有二阶连续偏导,用二阶泰勒展开近似表示,迭代公式：,(一）算法的基本思路： 考虑到 到 的确迭代过程，在 点处对 Tayloy展开：,如果目标函数在上具有二阶导数，共Hesse矩阵正定，并 且表达式为量式时，就可使用下述Newton法。这种方法 收敛速度很快。其缺点是计算量大，二是很赖于初始点的 选择。,4 Newton法和拟牛顿法,一、Newton法,若Hesse矩阵,正定,则,存在，,的极小点,为,当,时,为,的近似极小点，记,当,时,为,的精确极小点。,1 选定初始点 ，并给定精度 ，令,算法步骤,2 若 ，则停止， 否则转3,3 求出牛顿方向,5令 返回第2步,4 求新的迭代点,例：用Newton法求,的极小点。,初点,解：,代入Newton迭代公式得：,即为问题的最优点,1。选定初始点 计算 2。计算 3。由方程,（二）算法过程： 以知目标 函数 , 梯度 ，Hesse阵 ，给定终止准则H 及控制误差限,4。令 5。判别终止准则H是否满足。若满足，则打印最优解：,否则，,转2。,在此算法中，没有直接用Newton迭代公式： 而是通过3。解的线性方程进行。因为这样可以减少计算工作量，而且解线性方程组以有标准程序。 上面我们看到Newton法用于具有对称正定矩阵的二次函数时，一次迭代即可得到极小点。而对于一般的具有对称正定Hesse矩阵的函数，在极小点附近近似地呈现为二次函数，所以可以想象Newton法在解点附近具有较高的收敛速度。,（三）Newton法的缺点,1 要计算,2,即,要非奇异,为正定时，该方法才为下降算法,为正定时，,3,的计算量也很大,因为,则,此逆矩阵为,，而,例:,解：,它的极小在t=0达到,此时Newton法不能产生新点,而 不是极小点,起原因在于 不正定,即 不恒为正,为了使Newton法适应于 不是正定的,甚至奇异的情形,必须对Newton法作进一不修正.,Newton法和阻尼Newton法有共同缺点：,一、可能出现Hesse矩阵奇异的情形，因此不能确定后继点； 二、即使Hesse矩阵非奇异，也未必正定，因而New他on方向不一定是下降向，这就可能导致算法失效,由于阻尼Newton法含有较搜索，因此，每次迭代目标函数值一般有所下降(决不会上升)可以证明，阻尼Newton法在适当条件下具有全局收敛件，且为二阶收敛,例,解：,二、拟牛顿法,为了克服牛顿法的缺点，提出了用不包含二阶导数的,矩阵,替代,DPF法,构造Hesse逆矩阵的最早的，最巧妙的一种格式，由,Davidon提出的，后来由Fletcher和Powell作了改进，称为DPF法，又称变尺度法,公式：,迭代步骤：,1 给定,2 令,4,若,则停止,为近似最优解。否则,3,计算,5,转6,6,若,则令,返回2，否则转7,7,由公式计算,返回3,例：用DPF法求解问题,解：,同理求出最佳步长,为极小值点,5模式搜索法（步长加速法）,模式搜索法是由Hooke和Jeeves 1961年提出的，因此又称为HookeJeeves方法其基本思想，从几何上讲，是寻找具有较小函数值的“山谷”，力图使迭代产生的序列沿“山谷”逼近极小点算法从初始基点开始，包括两种类型的移