[工学]4无约束优化方法.ppt

问题提出 最速下降法优点 最速下降法缺点 习题 基本思想 算法构造 牛顿法算法 从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念 对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升，即出现f(xk+1)f(xk)的现象 阻尼牛顿法算法 算法特点 共轭方向及其性质 共轭方向法算法 共轭方向法基本定理 共轭梯度法 共轭梯度法基本性质 FR共轭梯度法算法 作业：p66, 4, 9 DFP校正公式 作　业 作业 P66 13 14 15 证： 定理2: 设 为 阶正定阵， 向量组 关于 共轭， 对正定二次函数 由任意 开始， 依次进行 次精确线有哪些信誉好的足球投注网站： 则： （１） （２） 是 在 上的极小点． 推论: 当 时， 为正定二次函数在 上的极小点． 记： 左乘 并使 得： 取： 定理3: 对于正定二次函数， 采用精确线有哪些信誉好的足球投注网站 的共轭梯度法在 步后终止， 且对 成立下列关系式： （共轭性） （正交性） （下降条件） Step1: 给出 Step2: 计算 如果 停． Step3: Step4: 由精确线有哪些信誉好的足球投注网站求 Step5: 转Step2. 例4： 用FR共轭梯度法求解： 解： (2) Newton法最突出的优点是收敛速度快,在这一点上其它算法无法比拟的.因此,建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解. 然而Newton法还有一个严重缺陷,就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵,当问题的维数n较大时,计算量迅速增加,从而就抵消了Newton法的优点． §4.4 变尺度法 为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算，这就是本节要给大家介绍的变尺度算法． 变尺度法是一种非常好的方法．其中DFP算法和BFGS算法，可以说直到目前为止在不用Hesse矩阵的方法中是最好的算法． 一、变尺度法基本原理 在Newton法中，由基本迭代格式 其中 令 于是有 其中 是初始点， 和 分别是目标函数 在 点 的梯度和Hesse矩阵． 为了消除这个迭代公式中的Hesse逆矩阵 可用某种近似矩阵 来替换它，即构造一个矩阵序列 去逼近Hesse逆矩阵序列 ．此时迭代式变为 事实上,式中 无非是确定了第 次迭代的有哪些信誉好的足球投注网站方向.为了取得更大的灵活性,我们考虑更一般的迭代公式 其中步长因子 通过从 出发沿 作直线搜 索来确定 此式是代表很广的一类迭代公式. 例如,当 （单位矩阵）时，它变为最速下降法的迭代 公式．为使 确实与 近似并且有容易计算的特点， 必须对 附加某些条件： 第一，为保证迭代公式具有下降性质，要求 中的每 一个矩阵都是对称正定的．理由是，为使有哪些信誉好的足球投注网站方向 是下降方向，只要 成立即可，即 成立． 当 对称正定时,此式必然成立,从而保证 具有下降性质． 第二，要求 之间的迭代具有简单形式．显然， 　是最简单的形式了．其中 称为校正矩阵，称为校正公式． 第三， 必须满足拟Newton条件． 所谓拟Newton 条件由下面的推导给出． 设迭代过程已进行到 步， 和 均已求出，现在推导 所必须满足的条件． 设目标函数 具有连续的二阶偏导数．现在将 在 处展成二阶泰勒公式: 令 ，于是有 即