牛顿法与修正牛顿法.ppt

牛顿法与修正牛顿法,团队成员： 李东旭 张宇 姚凯 丁科 王在进 刘继东 刘宇辰 任务分工： Documentalists ：李东旭 张宇 技术顾问：刘宇辰 姚凯 制片人：丁科 王在进 新闻发言人：刘继东 2010年10月8日,牛顿,简介 艾萨克·牛顿（Isaac Newton）是英国伟大的 数学家、物理学家、天文学家和自然哲学家， 其研究领域包括了物理学、数学、天文学、 神学、自然哲学和炼金术。 牛顿的主要贡献有发明了微积分，发现了 万有引力定律和经典力学，设计并实际制造了 第一架反射式望远镜等等，被誉为人类历史上 最伟大，最有影响力的科学家。为了纪念牛顿 在经典力学方面的杰出成就，“牛顿”后来成为 衡量力的大小的物理单位。,牛顿法 1.基本思想 在求目标函数 的极小值时，先将它在 点附近展开 成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作 为欲求目标函数的极小值点 的一次近似值。 设目标函数是连续二阶可微的，将函数在点 按泰勒级数 展开，并取到二次项：,对x求导，其极值点必满足一阶导数为零，所以， 得到 式中， 为Hessian矩阵的逆矩阵。,在一般情况下， 不一定是二次函数，因而 也不可能是 的极值点。但是在 点附近，函数 和 是近似的，所以可以用 点作为下一次迭代，即得 如果目标函数 是正定二次函数，那么 是个常矩阵，逼近式 是准确的。因此由 点出发只要迭代一次既可以求 的极小点。,在一般情况下， 不一定是二次函数，因而 也不可能是 的极值点。但是在 点附近，函数 和 是近似的，所以可以用 点作为下一次迭代，即得 如果目标函数 是正定二次函数，那么 是个常矩阵，逼近式 是准确的。因此由 点出发只要迭代一次既可以求 的极小点。,式与一维搜索公式 比较，则有搜索方向 ， 步长因子,牛顿法的迭代算式,其中 称为牛顿方向。,2.迭代步骤 一 给定初始点 ，计算精度，令k=0； 二 计算 点的梯度 、 及其逆矩阵 。 三 构造搜索方向,四 沿 方向进行一维搜索，得迭代点 五 收敛判断： 若 ，则 为近似最优点，迭代停止， 输出最优解 和 终止计算。 若不满足，令k=k+1，转第二步继续迭代。,3.举例 用牛顿法求函数 的极小值。,解： (1)取初始点 (2)计算牛顿方向,故,(3)极小值,由MATLAB得到 的曲面和等值线，如下图所示,数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点， 但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛； 牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。,修正牛顿法,当目标函数为非二次函数时，目标函数在 点展开所得的二次函数是该点附近的一种近似表达式，所求的极小点，当然也是近似的，需要继续迭代。但是当目标函数严重非线性时，用式 进行迭代则不能保证一定收敛，即在迭代中可能会出现 ，所得到的下一点不如原来的好。这和初始点的选择是否恰当有很大的关系。,为了克服牛顿法的上述缺陷，可以通过在迭代中引入步长因子和一维搜索加以解决，即令 式中， -一维搜索所得的最优步长因子。 因而将 称为牛顿方向。 经过这种修改后的算法称为修正牛顿法。也称牛顿方向法or阻尼牛顿法。,举例：用修正牛顿法求解下列无约束优化问题，已知,解： 因为 所以,由修正牛顿法，得 带入原函数 对 求导 解得 代入 因为 故迭代终止； 所以最优解为,牛顿法的评价,由于采用了目标函数的二阶导数信息，收敛速度比梯度法快。 牛顿法迭代公式与一般迭代公式的区别在于，没有最优步长因子。这使得在接近最优点时，由于步长不能调节，可能会错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而导致计算失败。为了克服这一点，提出了修正牛顿法，它既保持了牛顿法收敛快的特性，有放宽了对初始点选择的要求，保证每次迭代的结果都是目标函数值下降。 需要计算Hessian矩阵及其逆矩阵，内存占用、计算量大；此外二阶导数不存在，或者逆矩阵不存在的情况不能应用。,谢谢老师和同学们的聆听！,