07.第7讲 牛顿法 DFP变尺度法.pptVIP

牛顿法 基本思想： 在求目标函数 的极小值时，先将 在 处附件做泰勒展开，取二次近似函数式，然 后求出这个二次函数的极小点，并将该点作为 原目标函数的近似极小点，若此值不能满足精 度要求，则以此近似极小点作为下一轮迭代的 初始点，继续上述过程，直至满足要求为止。 DFP变尺度法 变尺度法基本思想： 变尺度法是在克服梯度法收敛慢和牛顿法 计算量大的缺点上发展起来的。它利用牛顿法 的迭代形式，然而不直接计算 ，而是 用一个对称正定矩阵 近似地代替 。 在迭代过程中不断改进，最后逼近 这种方法，省去了塞黑矩阵的计算和求逆，计 算量大为减少。 * * 牛顿法的迭代公式： 在目标函数 在 点处取二阶泰勒展开： 求二次近似函数 的极小点，即令 若 是二次函数，则 就是 的极小点，否则只是一个近似点，需进一步迭代。 牛顿法的迭代公式： 由于牛顿法迭代公式中没有步长因子 ，或者说 步长因子 ，这对非二次型目标函数，有时候 会出现函数值上升即 的情况。这 表明牛顿法不能保证函数值稳定下降，在严重的情况 下甚至可能造成迭代点的发散而导致计算失败，为克服上述弊端，提出阻尼牛顿法，其迭代公式为： 式中 ， ——阻尼因子； ——牛顿方向。 牛顿法的特点： 牛顿法不仅利用了函数的一阶导数信息，还利用了二阶导数信息，故其收敛速度比梯度法快得多。但牛顿法需计算塞黑矩阵及其逆矩阵，计算量存储量都很大，且都是以维数 比例增加，维数高时这个问题更加突出。此外，若塞黑矩阵是奇异矩阵时，其逆矩阵不存在，这种方法就不能使用。 变尺度法的迭代公式： 为变尺度矩阵，在迭代过程中不断修正。 在初试点 取 ，则上式变为： 而当 时，即 则为： DFP变尺度法及其递推公式： 变尺度矩阵递推公式： 其中 为k次迭代的修正矩阵。 DFP算法的迭代修正矩阵是 式中 ，即两迭代点信息之差； ，即目标函数一阶导数差 *