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

§10.4 拟牛顿法 6.4.1 拟牛顿条件 前面介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵. Newton法的优缺点都很突出。 优点：高收敛速度（二阶收敛）； 缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。 拟Newton法是模拟Newton法给出的一个保优去劣的算法 拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。 由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经成为一类公认的比较有效的算法 下面分析怎样构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆. 前面已经给出牛顿法的迭代公式,即 ?k是从 xk 出发沿牛顿方向搜索的最优步长. 设在第 次迭代后,得到点 ,我们将目标函数 在点 展成Taylor级数,并取二阶近似,得到 由此可知,在 附近有 令 ,则 记作 (10.4.3) (10.4.4) 则有 (10.4.5) 又设Hessian矩阵 可逆,则 (10.4.6) 这样,计算出 后,可以根据(10.4.6)估计在 处的Hessian矩阵的逆.因此,为了用不包含二阶导数的矩阵 取代牛顿法中的Hessian矩阵 的逆矩阵,有理由令 满足 (10.4.7) 式(10.4.7)有时称为拟牛顿条件.下面旧来研究怎样确定满足这个条件的矩阵 . 10.4.3 DFP算法 著名的 DFP 方法是 Davidon 首先提出, 后来又被 Fletcher 和 Powell 改进的算法,又称为变尺度法.在这种方法中,定义校正矩阵为 (6.4.16) 容易验证,这样定义校正矩阵 ,得到的矩阵 (6.4.17) (10.4.7) 满足拟牛顿条件(6.4.7).(6.4.17)称为DFP公式. DFP方法计算步骤如下: 1.给定初始点 ,允许误差 . 2.置 (单位矩阵),计算出在 处的梯度 3.令 4.从 出发,沿方向 搜索,求步长 ,使它满足 令 5.检验是否满足收敛准则,若 则停止迭代,得到点 ;否则,进行步6.. 6.若 ,则令 ,返回步2.;否则,进行步7.. 7.令 利用公式(6.4.17)计算 置 ,返回步3.. 例10.4.1 用DFP方法求解下列问题: 初始点及初始矩阵分别取为 推论： 共轭方向法 对于上述正交方向法，它是下降算法吗？ 不难得到： 故正交方向法，它是下降算法。 可由一组线性无关向量组，类似于schmidt正交化过程， §10.3 共轭梯度法 10.3.2 共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法. 下面,重点介绍Fletcher-Reeves共轭梯度法,简称FR法. 共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性. 我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形. 10.3.2. 共轭梯度法 如何选取一组共轭方向？ 以下分析算法的具体步骤。 我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形 初始搜索方向为最速下降