使用导数的最优化方法.ppt

《使用导数的最优化方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章使用导数的最优化方法无约束最优化问题2.最速下降法4.共轭梯度法5.拟牛顿法3.牛顿法一.无约束最优化问题无约束非线性规划问题的求解方法分为解析法和直接法两类。解析法需要计算函数的梯度，利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法直接法仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直接方法。无约束非线性规划问题的求解方法分为解析法和直接法两类。一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方

2、向是解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。本章主要介绍解析法;另一类只用到目标函数值,不必计算导数,通常称为直接方法,放在第11章讨论.本章考虑如下的下降算法：主要介绍最速下降法、牛顿法，共轭梯度法，拟牛顿法等10.1最速下降法10.1.1最速下降方向考虑无约束问题(6.1.2)其中函数具有一阶连续偏导数.人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法

3、.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向.人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要

4、地位.下面我们先来讨论怎样选择最速下降方向.我们知道,函数在点处沿方向的变化率可用方向导数来表达,对于可微函数,方向导数等于梯度与方向的内积,即(6.1.2)因此,求函数在点处的下降最快的方向,可归结为求解下列非线性规划:(6.1.3)根据Schwartz不等式,有去掉绝对值符号,可以得到(6.1.4)由上式可知,当(6.1.5)时等号成立.因此,在点处沿(6.1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.这里要特别指出,在不同尺度下最速下降方向是不同的.前面定义的最速下降方向,是在向量的殴氏范数不大

5、于1的限制得到的,属于殴氏度量意义下的最速下降方向.如果改用其他度量,比如,设为对称正定矩阵,在向量的范数不大于1的限制下,极小化,则得到的最速下降方向与前者不同.10.1.2最速下降算法最速下降法的迭代公式是(10.1.6)其中是从出发的搜索方向,这里取在点处的最速下降方向,即是从出发沿方向进行一维搜索的步长,即满足(10.1.11)计算步骤如下:1.给定初点,允许误差,置.2.计算搜索方向3.若,则停止计算;否则,从出发,沿进行一维搜索,求,使4.令,置,转步2..例10.1.1用最速下降法解下列问题:解：第二

6、次迭代：第三次迭代：在最速下降法的一位搜素中即在最速下降法中相邻两次搜索方向是正交的。对于二次严格凸函数其中A为n维对称正定矩阵可以求出步长因子k（本章习题7）锯齿现象最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向d(k+1)与前一次搜索方向d(k)总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。最速下降法的收敛性从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的

7、下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的(定理10.1.2)，而且恰好是线性收敛的。§10.2牛顿法6.2.1牛顿法设是二次可微实函数,.又设是的极小点的一个估计,我们把在展成Taylor级数,并取二阶近似:其中是在处的Hessian矩阵.为求的平稳点,令即(10.2.1)设可逆,有(10.2.1)得到牛顿法的迭代公式(10.2.2)其中是Hessian矩阵的逆矩阵.这样,知道后,算出在这一点处目标函

8、数的梯度和Hessian矩阵的逆,代人(10.2.2),便得到后继点,用代替,再用(10.2.2)计算,又得到的后继点.依此类推,产生序列.在适当的条件下,这个序列收敛.则牛顿法产生的序列收敛于.实际上,当牛顿法收敛时,有下列关系:其中C是某个常数.因此,牛顿法至少2级收敛,参看文献[19].可见牛顿法的收敛速率是很快的.例10.2.1用牛顿法解下列问题:我