无约束最优化的梯度方法

《无约束最优化的梯度方法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十八章无约束最优化的梯度方法,目的是在找一点称为此无约束最优化问题的全局最优点。然而在实际中，大多数最优化方法只能求到局部最优点，即在中可找到一点使得在的某个邻域中有。但在实际中，可以根据问题的意义来判断求得的局部极小点是否为全局最优点，无约束最优化可以分为两大类:一类是使用导数的方法，也就是根据目标函数的梯度（一阶导数）有时还要根据hesse矩阵（即二阶导数）所提供的信息而构造出来的方法，称为梯度方法。如：最速下降法，Newton法，共轭梯度法和变尺度法。另一类是不使用导数的方法，统称为直接方法。前者收敛速度快，但计算复杂（一阶

2、，二阶导数）后者不用导数，适应性强，但收敛速度慢。因此在可以求得目标函数导数信息时，尽可能用前一方法，而若求目标函数导数很困难，或者根本不存在导数时，就用后一种方法。18.1最速下降法最速下降法是求多元函数极值的最古老的数值算法，它直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。其缺点是收敛速度较慢。18.1.1算法思路假定我们已经迭代到第K次，即已有，从出发进一步迭代。(图18.1.1)显然应沿下降方向进行，而下降最快的方向是，为使目标函数沿此方向下降的最多，沿此方向进行直线搜索，从而得

3、到第k+1次迭代点，即。其中步长因子满足。按我们以前的记号，上面两式可记为：（18.1.1）当给定初始点（可任选），就可产生一个序列。在满足一定条件时，此序列必收敛于的极小点。称以（18.1.1）为迭代公式的算法为最速下降法。414以后为方便，记：18.1.2算法过程已知目标函数及其梯度，给定终止准则H及终止限1）选定初始点，计算2）做直线搜索3）判定终止准则H是否满足，若满足则打印最优解，终止。否则转2）。将最速下降法用于具有对称正定矩阵Q的二次函数：而此处即为：，其中即：,从而：因此：18.1.3锯齿现象最速下降法在两个相邻点之

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

5、路。因此反而是不好的。为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发明了不少方法，如：（1）选择不同初始点。例如：对问题：取初点，为求，沿方向从出发求的极点，即在线搜索代入函数式，则解得，然后再从开始迭代，经过10次迭代，近似得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接近最优点时，步长很小，目标函数值下降很慢。如果不取初点为而取虽然后一初点较前一初点离最优点远，但迭代中不含上面出现的锯齿现象。这时：一步就得到了极小点。可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事

6、。（2）采用不精确的一维搜索。用一维搜索求出的步长为时，我们不取，而用的一个近似值作为如取=0.9。这样可使相邻两个迭代点处的梯度不正交，从而改变收敛性。对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长λ的方法，称为固定步长最速下降法。只要λ充分小，总有：但λ到底取多大，没有统一的标准，λ取小了，收敛太慢，而λ取大了，又会漏掉极小点。18.1.4用于二次函数时的收敛速度定理18.1.1对于二次函数Q为对称正定，分别为其最小最大特征值，从任意初点出发，对此二次函数，用最速下降法产生的序列414，对于有：并

7、且由于而的极小点恰好是。故最速下降法对于二次函数关于任意初点均收敛，而且是线性收敛的。下面说明最速下降法收敛性的几何意义。考虑具有对称正定矩阵，其中这个函数的等值线为,c＞0改写为：这是以和为半轴的橢圆。图18.1.3图18.1.4从下面的分析可见，两个特征值的相对大小决定最速下降法的收敛性。（1）当时，等值线变为圆。此时414因而由上述定理知：既只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标函数时，只需迭代一步就到了极小点。（2）,等值线为椭圆。此时对于一般的初始点将产生锯齿现现象。（3）当等值线是很扁的椭圆。此时

8、，对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。图18.1.518.1.5加速最速下降法的收敛性上面我们已经证明最速下降法具有收敛性，收敛速度较慢，为了加速其收敛性，Shah等人于己于人1964年提出了一种“平行切线法”（简记为