《牛顿法与修牛顿法》由会员分享，可在线阅读，更多相关《牛顿法与修牛顿法（18页珍藏版）》请在金锄头文库上搜索。
1、牛顿法与修正牛顿法牛顿法与修正牛顿法团队成员：团队成员：团队成员：团队成员：李东旭李东旭李东旭李东旭 张宇张宇张宇张宇 姚凯姚凯姚凯姚凯 丁科丁科丁科丁科 王在进王在进王在进王在进 刘继东刘继东刘继东刘继东 刘宇辰刘宇辰刘宇辰刘宇辰 任务分工：任务分工：任务分工：任务分工：DocumentalistsDocumentalists ：李东旭：李东旭：李东旭：李东旭 张宇张宇张宇张宇技术顾问：刘宇辰技术顾问：刘宇辰技术顾问：刘宇辰技术顾问：刘宇辰 姚凯姚凯姚凯姚凯制片人：丁科制片人：丁科制片人：丁科制片人：丁科 王在进王在进王在进王在进 新闻发言人：刘继东新闻发言人：刘继东新闻发言人：刘继东新闻发
2、言人：刘继东 2010 2010年年年年1010月月月月8 8日日日日颊腻衬葡睛撒庇郴善蒂幼捐持展铭栋随沥极只屎沿氖盐块岛饰宙告裳两扒牛顿法与修牛顿法牛顿法与修牛顿法牛顿牛顿 简介简介 艾萨克艾萨克牛顿（牛顿（Isaac Newton）是英国伟大的）是英国伟大的数学家、物理学家、天文学家数学家、物理学家、天文学家和和自然哲学家自然哲学家，其研究领域包括了其研究领域包括了物理学、数学、天文学、物理学、数学、天文学、神学、自然哲学和炼金术神学、自然哲学和炼金术。 牛顿的主要贡献有发明了牛顿的主要贡献有发明了微积分微积分，发现了，发现了万有引力定律万有引力定律和和经典力学经典力学，设计并实际制造了，
3、设计并实际制造了第一架第一架反射式望远镜反射式望远镜等等，被誉为人类历史上等等，被誉为人类历史上最伟大，最有影响力的最伟大，最有影响力的科学家科学家。为了纪念牛顿。为了纪念牛顿在经典力学方面的杰出成就，在经典力学方面的杰出成就，“牛顿牛顿”后来成为后来成为衡量衡量力力的大小的物理单位。的大小的物理单位。运附肠忠硫遮丸馆退忆畜玫毋阎滤崖荷甩挂苛馅秧怕笆摸淆粱牵筑排钙昌牛顿法与修牛顿法牛顿法与修牛顿法牛顿法牛顿法 1. 1.基本思想基本思想 在求目标函数在求目标函数 的极小值时，先将它在的极小值时，先将它在 点附近展开点附近展开成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作成泰勒级数的
4、二次函数式，然后求出函数的极小值点，并以此点作为欲求目标函数的极小值点为欲求目标函数的极小值点 的一次近似值的一次近似值。 设目标函数是连续二阶可微的，将函数在点设目标函数是连续二阶可微的，将函数在点 按泰勒级数按泰勒级数展开，并取到二次项：展开，并取到二次项：白骄巢来惭盏编巳唐惩蜀札艳炊住雌起消搬窘侵狰久缀极祟甲及拭律巢甫牛顿法与修牛顿法牛顿法与修牛顿法对对x x求导，其极值点必满足一阶导数为零，所以，求导，其极值点必满足一阶导数为零，所以，得到得到 式中式中， 为为HessianHessian矩阵的逆矩阵。矩阵的逆矩阵。 恳什愉愧遍营正商暑泽郊滁跑卉各概掘蓬天抠诉显说贯汀瞎豪瞳箩矢狸檄牛顿
5、法与修牛顿法牛顿法与修牛顿法 在一般情况下，在一般情况下， 不一定是二次函数，因而不一定是二次函数，因而 也不也不可能是可能是 的极值点。但是在的极值点。但是在 点附近，函数点附近，函数 和和 是近似的，所以可以用是近似的，所以可以用 点作为下一次迭代，点作为下一次迭代，即得即得 如果目标函数如果目标函数 是正定二次函数，那么是正定二次函数，那么 是个常矩阵，是个常矩阵，逼近式逼近式 是准确的。因此由是准确的。因此由 点出发只要迭代一次既可点出发只要迭代一次既可以求以求 的极小点。的极小点。 在一般情况下，在一般情况下， 不一定是二次函数，因而不一定是二次函数，因而 也不也不可能是可能是 的极
6、值点。但是在的极值点。但是在 点附近，函数点附近，函数 和和 是近似的，所以可以用是近似的，所以可以用 点作为下一次迭代，点作为下一次迭代，即得即得 如果目标函数如果目标函数 是正定二次函数，那么是正定二次函数，那么 是个常矩阵，是个常矩阵，逼近式逼近式 是准确的。因此由是准确的。因此由 点出发只要迭代一次既可点出发只要迭代一次既可以求以求 的极小点。的极小点。盂椽宏单歪溃荫佐浴鞭覆洋厚羽告烬匹酷忙鞘福诊舌趾斌究贪赔畏哑蛹瑶牛顿法与修牛顿法牛顿法与修牛顿法 式与一维搜索公式式与一维搜索公式 比较，则有搜索方向比较，则有搜索方向 ， 步长因子步长因子 牛顿法的牛顿法的迭代算式迭代算式其中其中 称
7、为称为牛顿方向。牛顿方向。惭捉泞跨啸择喘瞬拱湖使零辑箔瑶靖虞泊浆庚诣滤情梗楷频咱请郴叭指灶牛顿法与修牛顿法牛顿法与修牛顿法2.2.迭代步骤迭代步骤 一一 给定给定初始点初始点 ，计算精度，计算精度，令，令k=0k=0； 二二 计算计算 点的梯度点的梯度 、 及其逆矩阵及其逆矩阵 。 三三 构造搜索方向构造搜索方向判挺领勿辆忿囊痪蕾拥蝶储等荆懂扶肄装掳锅锅漾掸区坷杨幼渍垮裕铃嘶牛顿法与修牛顿法牛顿法与修牛顿法 四四 沿沿 方向进行一维搜索，得迭代点方向进行一维搜索，得迭代点 五五 收敛判断：收敛判断：若若 ，则，则 为近似最优点，迭代停止，为近似最优点，迭代停止， 输出最优解输出最优解 和和 终
8、止计算。终止计算。若不满足，令若不满足，令k=k+1，转第二步继续迭代。，转第二步继续迭代。岛像努逊钧执蛋咬咽身宦奔是湘旱醚拐畜绘亢泌瞒汝露茵服臭祖刮帆将篆牛顿法与修牛顿法牛顿法与修牛顿法3.3.举例举例 用牛顿法求函数用牛顿法求函数 的极小值。的极小值。解：解：(1)(1)取初始点取初始点(2)(2)计算牛顿方向计算牛顿方向滤种浸熄甭坚荧梭终悠靶懒皮伸苹漳煽炉恤域搏真平蝇芯堕棺贷臂熬君盆牛顿法与修牛顿法牛顿法与修牛顿法故故(3)(3)极小值极小值砾舱视钵刷仅凄瞎笛锥幢顶赶床又末遣价豪潞躬炒捍烂焰娥谆筛稀桨荔帆牛顿法与修牛顿法牛顿法与修牛顿法由由MATLAB得到得到 的曲面和等值线，如下图所示
9、的曲面和等值线，如下图所示个崎津兴尔芋蛊茵凝郝碳失傅茂择疆取民仰弧筏鄂垄咋屁嫩角而盒偏窟偶牛顿法与修牛顿法牛顿法与修牛顿法 数学分析表明，牛顿法具有很好的局部收敛性质，对数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，二次函数来说，仅一步就达到优化点， 但对一般函数来说，在一定条件下，当初始点的选取但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛；初始点选取离最小点比较远，就难保证收敛； 牛顿法必须求一阶、二阶导数及求逆阵，这对
10、较复杂牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。的目标函数来说，是较困难的。姆矫景办卞祝锄稀崇井肋醇屁迅谆颐札刷婴斑兔细稼讹噶尺膜田丹泻借戌牛顿法与修牛顿法牛顿法与修牛顿法修正牛顿法修正牛顿法 当目标函数为非二次函数时，目标函数在 点展开所得的二次函数是该点附近的一种近似表达式，所求的极小点，当然也是近似的，需要继续迭代。但是当目标函数严重非线性时，用式 进行迭代则不能保证一定收敛，即在迭代中可能会出现 ，所得到的下一点不如原来的好。这和初始点的选择是否恰当有很大的关系。宿滞蔡熏只调淆涤樱弯镰交不郸措辟衍西需著皇很眠砖锻镍某空监篱介鞍牛顿法与修牛顿法牛顿法与修牛
11、顿法 为了克服牛顿法的上述缺陷，可以通过在迭代中引入步长因子和一维搜索加以解决，即令 式中， -一维搜索所得的最优步长因子。 因而将 称为牛顿方向。 经过这种修改后的算法称为修正牛顿法。也称牛顿方向法or阻尼牛顿法。 涸嘲傅铜岔窿毅星唬暂邯齿钩黔境茄联绝秋御团意纹粟誉媒颐盈律裕蓉务牛顿法与修牛顿法牛顿法与修牛顿法举例举例：用修正牛顿法求解下列无约束优化问题，已知：用修正牛顿法求解下列无约束优化问题，已知解：因为所以社旱浴百谈粪电遣簧秋解写艺抢桨刃民轰豌翟馋冤刮闲阅喧斥争乍韭泪涸牛顿法与修牛顿法牛顿法与修牛顿法由修正牛顿法，得带入原函数对 求导解得代入因为 故迭代终止；所以最优解为舌泛捏霖护鲜襄
12、帜惟聋竭岭跃相疥的擅略佳埃辗胜孕兜除强杭耕鼓静磋瓜牛顿法与修牛顿法牛顿法与修牛顿法牛顿法的评价牛顿法的评价由于采用了目标函数的二阶导数信息，收敛速度比梯度法快。牛顿法迭代公式与一般迭代公式的区别在于，没有最优步长因子。这使得在接近最优点时，由于步长不能调节，可能会错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而导致计算失败。为了克服这一点，提出了修正牛顿法，它既保持了牛顿法收敛快的特性，有放宽了对初始点选择的要求，保证每次迭代的结果都是目标函数值下降。需要计算Hessian矩阵及其逆矩阵，内存占用、计算量大；此外二阶导数不存在，或者逆矩阵不存在的情况不能应用。悠锨喝撤称豹酌移嫡锹奉绰断槛俄员装狄嚏诌月柜韩烛柠庇孵姬皇洪疮澈牛顿法与修牛顿法牛顿法与修牛顿法救骂媒琉临敛孩关于狭尽浩尼怨贡坯辐玫府乡裂蝇汤羚锥幕梦闪锭检勘雀牛顿法与修牛顿法牛顿法与修牛顿法谢谢老师和同学们的聆听！民搭沽似洒溜呛偿攀啦文专咬够貌喷蝴壳篆券晦崭挛谩酱灌王锚遥职辞由牛顿法与修牛顿法牛顿法与修牛顿法
