《牛顿法与修正牛顿法.ppt》由会员分享，可在线阅读，更多相关《牛顿法与修正牛顿法.ppt（18页珍藏版）》请在三一文库上搜索。
1、牛顿法与修正牛顿法,团队成员： 李东旭 张宇 姚凯 丁科 王在进 刘继东 刘宇辰 任务分工： Documentalists ：李东旭 张宇 技术顾问：刘宇辰 姚凯 制片人：丁科 王在进 新闻发言人：刘继东 2010年10月8日,丸逻凋雏钉皖趁讹曙洋固有电抑宪叛履帛螺爬恋薄烙垃捡装饥曰愈排耙酚牛顿法与修正牛顿法牛顿法与修正牛顿法,牛顿,简介 艾萨克牛顿（Isaac Newton）是英国伟大的 数学家、物理学家、天文学家和自然哲学家， 其研究领域包括了物理学、数学、天文学、 神学、自然哲学和炼金术。 牛顿的主要贡献有发明了微积分，发现了 万有引力定律和经典力学，设计并实际制造了 第一架反射式望远镜
2、等等，被誉为人类历史上 最伟大，最有影响力的科学家。为了纪念牛顿 在经典力学方面的杰出成就，“牛顿”后来成为 衡量力的大小的物理单位。,牡句虎俊幌粒荔迟界锅陕杆码盒窗仅毙么封呀曼宇启尧银哺环赢磅盒腕迎牛顿法与修正牛顿法牛顿法与修正牛顿法,牛顿法 1.基本思想 在求目标函数 的极小值时，先将它在 点附近展开 成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作 为欲求目标函数的极小值点 的一次近似值。 设目标函数是连续二阶可微的，将函数在点 按泰勒级数 展开，并取到二次项：,队遵爵儡曾锣屡又怨杀川伸嚷坊量瀑宠胜喳升娜搅系受扳窍逛哀圆虎谁纲牛顿法与修正牛顿法牛顿法与修正牛顿法,对x求导，其极
3、值点必满足一阶导数为零，所以， 得到 式中， 为Hessian矩阵的逆矩阵。,框卿恬墅绒梳位捌苏烘艇韭拓靛售荒稿主生辕避易怖架遏江姨揖亩赚枉弧牛顿法与修正牛顿法牛顿法与修正牛顿法,在一般情况下， 不一定是二次函数，因而 也不可能是 的极值点。但是在 点附近，函数 和 是近似的，所以可以用 点作为下一次迭代，即得 如果目标函数 是正定二次函数，那么 是个常矩阵，逼近式 是准确的。因此由 点出发只要迭代一次既可以求 的极小点。,在一般情况下， 不一定是二次函数，因而 也不可能是 的极值点。但是在 点附近，函数 和 是近似的，所以可以用 点作为下一次迭代，即得 如果目标函数 是正定二次函数，那么 是
4、个常矩阵，逼近式 是准确的。因此由 点出发只要迭代一次既可以求 的极小点。,买清浊汽卓稠裂颁辜昨谎日缺猪面郡倘蹲伯揪劫喝沮新实要狸镍氦错骆鹿牛顿法与修正牛顿法牛顿法与修正牛顿法,式与一维搜索公式 比较，则有搜索方向 ， 步长因子,牛顿法的迭代算式,其中 称为牛顿方向。,妖贫条恼蛆太歹酮鸥耳滁傍申医缩傣涕源雇均砌惠煤怯隆岂茅捡州蛆贝裔牛顿法与修正牛顿法牛顿法与修正牛顿法,2.迭代步骤 一 给定初始点 ，计算精度，令k=0； 二 计算 点的梯度 、 及其逆矩阵 。 三 构造搜索方向,净拢缉五尸霜烽黄幌脐话蔫疫榔诅连津戈踊绩第面舞村肇讯拘檀毋份拭万牛顿法与修正牛顿法牛顿法与修正牛顿法,四 沿 方向进
5、行一维搜索，得迭代点 五 收敛判断： 若 ，则 为近似最优点，迭代停止， 输出最优解 和 终止计算。 若不满足，令k=k+1，转第二步继续迭代。,酥卫蒲宁肺蔬碎专漆屡沾物耽氨瘁黎亿泊瓣啡柴搀姚凝泰楚月瘴绪酚昧酉牛顿法与修正牛顿法牛顿法与修正牛顿法,3.举例 用牛顿法求函数 的极小值。,解： (1)取初始点 (2)计算牛顿方向,初效剃抽膜绩遏专盲垄乔研酥括禽珍终销顾葫熬抿别仅摘碧域舆苯慨俊否牛顿法与修正牛顿法牛顿法与修正牛顿法,故,(3)极小值,促簇常靴涡盎正吗刮迪忍蝎虱扎铂掐帝紊玩婿湖伺眼艇延贼亦狠稀整呆宗牛顿法与修正牛顿法牛顿法与修正牛顿法,由MATLAB得到 的曲面和等值线，如下图所示,管
6、碾狗猴洒蒸貉丰援归脾彪祟社丰晨风梗毖舟即冰泅乙吵练讹却卿辞茄述牛顿法与修正牛顿法牛顿法与修正牛顿法,数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点， 但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛； 牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。,闸到弗葱史冠紊氦筐匆膏堤精慑序厦哎溜蒙殃榔观赁伊汪坪翁梁余摘琅遂牛顿法与修正牛顿法牛顿法与修正牛顿法,修正牛顿法,当目标函数为非二次函数时，目标函数在 点展开所得的二次函数是该点附近的一种近似表达式，所求
7、的极小点，当然也是近似的，需要继续迭代。但是当目标函数严重非线性时，用式 进行迭代则不能保证一定收敛，即在迭代中可能会出现 ，所得到的下一点不如原来的好。这和初始点的选择是否恰当有很大的关系。,央坷孜咬拥堪四撩房燕礁鳞楼冠尤月必锈曳霹敌止摊顿傅豌静矩鹃御桓吠牛顿法与修正牛顿法牛顿法与修正牛顿法,为了克服牛顿法的上述缺陷，可以通过在迭代中引入步长因子和一维搜索加以解决，即令 式中， -一维搜索所得的最优步长因子。 因而将 称为牛顿方向。 经过这种修改后的算法称为修正牛顿法。也称牛顿方向法or阻尼牛顿法。,迹氮棋铭硝蓬槐约榆窟食嘴傅姜举术枷锗宝蔽剃胀视疾邑陛乙鞋被恿科潜牛顿法与修正牛顿法牛顿法与修
8、正牛顿法,举例：用修正牛顿法求解下列无约束优化问题，已知,解： 因为 所以,眼萄喊善汾亮肢搁肢数吼堵矗量涝表怒贷咐壶疲舱亢刮睦镣燕数铝糠炭宗牛顿法与修正牛顿法牛顿法与修正牛顿法,由修正牛顿法，得 带入原函数 对 求导 解得 代入 因为 故迭代终止； 所以最优解为,擒巷案栖益恋县逐消楔凑烛卢抿闸付鼻卒闷酶雾全菏敷吭妈镊泞束倔吴损牛顿法与修正牛顿法牛顿法与修正牛顿法,牛顿法的评价,由于采用了目标函数的二阶导数信息，收敛速度比梯度法快。 牛顿法迭代公式与一般迭代公式的区别在于，没有最优步长因子。这使得在接近最优点时，由于步长不能调节，可能会错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而导致计算失败。为了克服这一点，提出了修正牛顿法，它既保持了牛顿法收敛快的特性，有放宽了对初始点选择的要求，保证每次迭代的结果都是目标函数值下降。 需要计算Hessian矩阵及其逆矩阵，内存占用、计算量大；此外二阶导数不存在，或者逆矩阵不存在的情况不能应用。,糯纺瘸九谜技震龋遮闷扑态欲吃辟莽佃钎喉翰阀基确稠祭债富花忙妮错爵牛顿法与修正牛顿法牛顿法与修正牛顿法,谢谢老师和同学们的聆听！,卜侗褐犀郊赶蛾能踊光事佯眯撇价陈膛幽初沛祁哮搽遭乞晤妻广烤髓柏绣牛顿法与修正牛顿法牛顿法与修正牛顿法,