阻尼牛顿法定稿.ppt.ppt

牛顿法与阻尼牛顿法 团队成员 崔尚金英博郭向姝多丽娅赵丽霞窦永贵尹逊增宋红喜陈建王思远冯文秀牛顿法主讲 崔尚阻尼牛顿法主讲 金英博 牛顿法1 基本原理在第k次迭代的迭代点的邻域内 把展开成泰勒级数的二次函数式去近似代替原目标函数 然后求出该二次函数的极小点 作为对原目标函数求优的下一个迭代点 依此类推 通过多次重复迭代 使迭代点逐步逼近原目标函数的极小点 释图 companylogo 设目标函数是连续二阶可微的 将函数在点按泰勒级数展开 并取到二次项 对x求导 其极值点必满足一阶导数为零 所以 得到式中 为hessian矩阵的逆矩阵 在一般情况下 不一定是二次函数 因而也不可能是的极值点 但是在点附近 函数和是近似的 所以可以用点作为下一次迭代 即得如果目标函数是正定二次函数 那么是个常矩阵 逼近式是准确的 因此由点出发只要迭代一次既可以求的极小点 式与一维搜索公式比较 则有搜索方向 步长因子 牛顿法的迭代算式 其中称为牛顿方向 2 迭代步骤一给定初始点 计算精度 令k 0 二计算点的梯度 及其逆矩阵 三构造搜索方向 四沿方向进行一维搜索 得迭代点五收敛判断 若 则为近似最优点 迭代停止 输出最优解和终止计算 若不满足 令k k 1 转第二步继续迭代 原始牛顿法的特点若用原始牛顿法求某二次目标函数的最优解 则构造的逼近函数与原目标函数是完全相同的二次式 其等值线完全重合 故从任一点出发 一定可以一次达到目标函数的极小点 因此 牛顿法是具有二次收敛性的算法 其优点是 对于二次正定函数 迭代一次即可以得到最优解 对于非二次函数 若函数二次性较强或迭代点已经进入最优点的较小邻域 则收敛速度也很快 原始牛顿法的缺点是 由于迭代点的位置是按照极值条件确定的 并未沿函数值下降方向搜索 因此 对于非二次函数 有时会使函数值上升 即f xk 1 f xk 而使计算失败 3 举例用牛顿法求函数的极小值 解 1 取初始点 2 计算牛顿方向 故 3 极小值 数学分析表明 牛顿法具有很好的局部收敛性质 对二次函数来说 仅一步就达到优化点 但对一般函数来说 在一定条件下 当初始点的选取充分接近目标函数的极小点时 有很快的收敛速度 但若初始点选取离最小点比较远 就难保证收敛 牛顿法必须求一阶 二阶导数及求逆阵 这对较复杂的目标函数来说 是较困难的 阻尼牛顿法的迭代公式 阻尼牛顿法的计算过程和算法框图 阻尼牛顿法计算框图 阻尼牛顿法算例 3 牛顿方向 ok 验证算法的准确性 fminsearch 函数作用是找出使这个目标函数最小化的x值 首先 注意到时 所以该问题的目标函数有极小值 梯度和hesse矩阵如下 梯度 hesse阵 若取初始点 则对应的梯度 hesse矩阵的逆此时牛顿方向不是目标函数的下降方向 牛顿迭代点对应的函数值 经过数值实验可以看出 牛顿法不能求出目标函数的极小值 求解二维优化问题 另外 当沿着方向进搜索时 由于目标函数所以线搜索的最小点仍为 无法应用阻尼牛顿法解决该问题 求目标函数极小点 初值此时hesse矩阵奇异 故无法求出它的逆阵 阻尼牛顿法到此不能继续进行 阻尼 牛顿法的困难 应用牛顿法的主要困难是hesse矩阵可能奇异 或者接近奇异 即使该矩阵是可逆的 它也未必是正定矩阵 此时 导出的牛顿法迭代格式的二次函数不一定有极小点 甚至没有驻点 为了保证近似目标函数的二次函数是严格凸的 存在极小点 就需要对二次函数的hesse矩阵进行修正 修正牛顿法的基本思想是 在确定搜索方向时 对hesse矩阵增加一个校正矩阵 使之正定 这样可以保证搜索方向是目标函数的下降方向 简介几种修正方法 牛顿法的效能特点 缺点 1 对目标函数要求高 函数必须具有连续的一阶 二阶偏导数 同时其赫森矩阵必须正定且非奇异性 2