《第十八章 无约束最优化的梯度方法.doc》由会员分享，可在线阅读，更多相关《第十八章 无约束最优化的梯度方法.doc（36页珍藏版）》请在金锄头文库上搜索。
1、第十八章 无约束最优化的梯度方法,目的是在找一点称为此无约束最优化问题的全局最优点。然而在实际中，大多数最优化方法只能求到局部最优点，即在中可找到一点使得在的某个邻域中有。但在实际中，可以根据问题的意义来判断求得的局部极小点是否为全局最优点，无约束最优化可以分为两大类:一类是使用导数的方法，也就是根据目标函数的梯度（一阶导数）有时还要根据hesse矩阵（即二阶导数）所提供的信息而构造出来的方法，称为梯度方法。如：最速下降法，Newton法，共轭梯度法和变尺度法。另一类是不使用导数的方法，统称为直接方法。前者收敛速度快，但计算复杂（一阶，二阶导数）后者不用导数，适应性强，但收敛速度慢。因此在可以
2、求得目标函数导数信息时，尽可能用前一方法，而若求目标函数导数很困难，或者根本不存在导数时，就用后一种方法。18.1 最速下降法最速下降法是求多元函数极值的最古老的数值算法，它直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。其缺点是收敛速度较慢。18.1.1 算法思路 假定我们已经迭代到第 K次，即已有，从出发进一步迭代。 (图18.1.1 )显然应沿下降方向进行，而下降最快的方向是，为使目标函数沿此方向下降的最多，沿此方向进行直线搜索，从而得到第k+1次迭代点，即。其中步长因子满足。按我们以前的记号，上面两式可记为： （18.1.1）当给定初始点（可
3、任选），就可产生一个序列。在满足一定条件时，此序列必收敛于的极小点。称以（18.1.1）为迭代公式的算法为最速下降法。以后为方便，记：18.1.2 算法过程已知目标函数及其梯度，给定终止准则H及终止限 1）选定初始点，计算2）做直线搜索3）判定终止准则H是否满足，若满足则打印最优解，终止。否则转2）。将最速下降法用于具有对称正定矩阵Q的二次函数：而此处即为：，其中即：,从而：因此：18.1.3 锯齿现象最速下降法在两个相邻点之间的搜索方向对于正定二次函数是正交的，因而最速下降法向最小点逼近是曲折前进的。这种现象称为锯齿现象。除最特殊的目标函数和极特殊的初始点外，这种现象都会发生。这是因为最速下
4、降法的下一步搜索方向是 ，从而知： 。图18.1.2 这说明其前后两个搜索方向总是垂直的，这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路。因此反而是不好的。为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发明了不少方法，如：（1）选择不同初始点。例如：对问题：取初点，为求，沿方向从出发求的极点，即在线搜索 代入函数式，则解得 ，然后再从开始迭代，经过1
5、0次迭代，近似得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接近最优点时，步长很小，目标函数值下降很慢。如果不取初点为而取虽然后一初点较前一初点离最优点远，但迭代中不含上面出现的锯齿现象。这时：一步就得到了极小点。可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。（2）采用不精确的一维搜索。用一维搜索求出的步长为时，我们不取，而用的一个近似值作为 如取=0.9。这样可使相邻两个迭代点处的梯度不正交，从而改变收敛性。对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长的方法，称为固定步长最速下降法。只要充分小，总有：但到底
6、取多大，没有统一的标准， 取小了，收敛太慢，而取大了，又会漏掉极小点。18.1.4 用于二次函数时的收敛速度定理18.1.1 对于二次函数Q为对称正定，分别为其最小最大特征值，从任意初点出发，对此二次函数，用最速下降法产生的序列，对于有：并且由于而的极小点恰好是。故最速下降法对于二次函数关于任意初点均收敛，而且是线性收敛的。 下面说明最速下降法收敛 性的几何意义。考虑具有对称正定矩阵，其中这个函数的等值线为, c0改写为：这是以和为半轴的橢圆。 图18.1.3 图18.1.4 从下面的分析可见，两个特征值的相对大小决定最速下降法的收敛性。（1） 当时，等值线变为圆。此时因而由上述定理知：既只需
7、迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标函数时，只需迭代一步就到了极小点。（2）, 等值线为椭圆。此时对于一般的初始点将产生锯齿现现象。（3）当等值线是很扁的椭圆。此时， 对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。图18.1.5 18.1.5 加速最速下降法的收敛性 上面我们已经证明最速下降法具有收敛性，收敛速度较慢，为了加速其收敛性，Shah等人于己于人1964年提出了一种“平行切线法”（简记为PARTAN法）。其算法过程如下：选择初始点及控制误差 1）求2）求 3）求为下一个一维搜索所确定的 再求 4） 若这个算法的思路就是：与最速下降法一样计算，但从求就不同。
8、就是先从Zk出发沿负梯度进行一维搜索，把求得的极小点记为，然后从出发沿着指向的方向用一维极小的方法求出。显然，在一般情况下要比好 一些 ，所以平行切线法的每次迭代至少不会比最速下降法的一次迭代差，因此收敛速度加快了。仍用前面的例子加以说明 用平行切线法求解时，仍和最速下降法一致。而表中的在平行切线时作为，然后从出发沿方向，作一维搜索，则一步就得到极小点。当然由于计算中的舍入误差，上述方向指向极小点方向的右偏移，因而一步求出的是的近似值。18.2 Newton法 如果目标函数在Rn上具有二阶导数，且Hesse矩阵正定，并且表达式为显式时，就可使用下述Newton法。这种方法收敛速度很快。其缺点是
9、计算量大，二是很赖于初始点的选择。18.2.1 算法的基本思路考虑到 到的迭代过程，在点处对Taylor展开： 若Hesse矩阵正定，则存在，由此求出二次函数Q(z)的极小点为 ：. 以此作为f(z)极小点的一个新的近似。此公式即为Newton迭代公式。其几何意义如下：(图18.2.1 ) 函数f(z)过点的等值面为：，在点Zk处用一个二次曲面代替此等值面，即：。当正定时，它是一个超椭球面。而的极小点正是这个超椭球的中心，此点作为的极小点的一个新的近似。例18.2.1 用Newton法求的极小点。 解 取初点 则：代入Newton迭代公式得： 此即为问题的最优点。18.2.2 算法过程以知目标
10、 函数, 梯度，Hesse阵，给定终止准则H及控制误差限1）选定初始点计算2）计算3）由方程4）令5）判别终止准则H是否满足。若满足，则打印最优解： 转2）。在此算法中，没有直接用Newton迭代公式,而是通过3求解线性方程组进行。因为这样可以减少计算工作量，而且解线性方程组有标准程序。上面我们看到Newton法用于具有对称正定矩阵的二次函数时，一次迭代即可得到极小点。而对于一般的具有对称正定Hesse矩阵的函数，在极小点附近近似地呈现为二次函数，所以可以想象Newton法在解点附近具有较高的收敛速度。18.2.3 收敛性定理18.2.1 若（1）是的驻点，即（2）在的邻域中具有直到三阶的连续
11、有界偏导数，即对均有： (3) Hessen矩阵的逆阵存在，且对 均 有，则由Newton迭代公式所产生的序列. 若收敛，则收敛阶为2。注： 证明：因为序列收敛，不妨设当时，总有由 , 虽然 此二式两边相减并利用条件（3）得：考虑梯度的第i个分量在处的展开：令，相应的设为。利用条件（2），对于 可推得：故根据定义可知是2阶收敛的。定理18.2.1：设定理1中条件（1）,（2）,（3）成立。且（4）若取初始点， 则由Newton迭代公式产生的序列收敛于 。证明：先用数学归纳法证明：若，则，时，由定理1证明结果知： 由条件（4）即： 因而， ， 故：设 ， 经证 ，因为：因为 故 又 Newton
12、法的一个重要缺点之一就是要计算,因而必须非奇异,否则迭代就无法进行。而且即使非奇异，也不保证算法一定收敛。例: ，则则 而 。它的极小在t=0达到,此时Newton法不能产生新点,而不是极小点,其原因在于不正定, 即 不恒为正, 为了使Newton法适应于不是正定的,甚至奇异的情形,必须对Newton法作进一步修正。 方法1: Marquart-Levanberg法.搜索方向取为 其中，为 一个非负数, 为一给定矩阵, 至少为半正定矩阵.算法过程：给定这种方法是Newton法和最速下降法的结合,它可以克服这两个方法各自的一些缺点。在中若把取为单为矩阵，或取对角线上为正数的对角阵,此时,在这个迭
13、代公式中 取充分小时, 的第二项不起多大作用,从而方法近似于Newton法,当它取足够大时,Ak中第二项起主要作用,故而方法近似于最速下降法,并且当非正定时, 取适当大, 一定为正定。方法2 GoldstainPrice法这种方法也可以看成Newton和最速下降法二者的结合，也可以弥补而方法的缺点。设我们已有点，下面分别讨论如何找到搜索方向和步长。当迭代到后，首先计算一个矩阵，其中的第i列向量为 现在有了搜索方向和步长 ，则迭代公式为：，在此方法中，显然为f(z)的二阶导数矩阵的一个近似，迭代中有时取梯度方向，有时取近似Newton方向，而步长的选择是保证每步迭代f(z)的值均下降。算法过程：
14、给定 f(z). . 初点.正数r . 0 例18.2.1 解 取 迭代两次即可求得最优解 , ,.此时这个方法克服了非正定甚至非奇异的情形，也克服了最速下降法的锯齿现象。Newton法的优点是收敛速度快，但它可能失败，失败的原因有：（1）存在，但用Newton法时出现（因为Newton法中没有用直线搜索只是在处的二次近似函数的极小点，并不保证一定有下降性）；（2）Newton方向与正交；（3）存在，但不正定；（4）不存在。 对于（1），（3），（4），我们前面已给出了一些克服办法，对于（2）只要取搜索方向为负梯度方向，或用一次一维搜索也是可以解决的。Newton法更主要的缺点是每次迭代都要计算 的二阶导数矩阵，并对该矩阵求逆。前者要求计算个二阶偏导数，工作量很大。后者对n很大时，也是很困难的。为了减少工作量，可以采用多次迭代再计算一次二阶导数矩阵，这样做可收到满意效果。为了节省存储，可用松弛法（后面将介绍）
