生活随笔
收集整理的這篇文章主要介紹了
牛顿迭代优化
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
引用zhiyong_will博主的工作，僅進(jìn)行小范圍修改
http://blog.csdn.net/google19890102/article/details/41087931
一、牛頓法概述
除了梯度下降法，牛頓法也是常用的的一種優(yōu)化算法。牛頓法的基本思想是利用迭代點處的一階導(dǎo)數(shù)(梯度)和二階導(dǎo)數(shù)(Hessen矩陣)對目標(biāo)函數(shù)進(jìn)行二次函數(shù)近似，然后把二次模型的極小點作為新的迭代點，并不斷重復(fù)這一過程，直至求得滿足精度的近似極小值。牛頓法的速度相當(dāng)快，而且能高度逼近最優(yōu)值。牛頓法分為基本的牛頓法和全局牛頓法
二、基本牛頓法
1、基本牛頓法的原理
基本牛頓法是一種是用導(dǎo)數(shù)的算法，它每一步的迭代方向都是沿著當(dāng)前點函數(shù)值下降的方向。 我們主要集中討論在一維的情形，對于一個需要求解的優(yōu)化函數(shù)，求函數(shù)的極值的問題可以轉(zhuǎn)化為求導(dǎo)函數(shù)。對函數(shù)進(jìn)行泰勒展開到二階，得到
對上式求導(dǎo)并令其為0，則為
即得到
這就是牛頓法的更新公式。
2、基本牛頓法的流程
給定終止誤差值，初始點，令；計算，若，則停止，輸出；計算，并求解線性方程組得解：；令，，并轉(zhuǎn)2。 三、全局牛頓法
? ?牛頓法最突出的優(yōu)點是收斂速度快，具有局部二階收斂性，但是，基本牛頓法初始點需要足夠“靠近”極小點，否則，有可能導(dǎo)致算法不收斂。這樣就引入了全局牛頓法。
1、全局牛頓法的流程
給定終止誤差值，，，初始點，令；計算，若，則停止，輸出；計算，并求解線性方程組得解：；記是不滿足下列不等式的最小非負(fù)整數(shù)：；令，，，并轉(zhuǎn)2。
2、Armijo搜索
全局牛頓法是基于Armijo的搜索，滿足Armijo準(zhǔn)則： 給定，，令步長因子，其中是滿足下列不等式的最小非負(fù)整數(shù):
? ?實驗部分使用Java實現(xiàn)，需要優(yōu)化的函數(shù)，最小值為：
四、算法實現(xiàn)
1、基本牛頓法Java實現(xiàn)
[java]?view plaincopy
?? package?org.algorithm.newtonmethod;?
public?class?NewtonMethod?{?? ????private?double?originalX;?? ????private?double?e;?? ????private?double?maxCycle;?? ????? ? ? ? ? ?? ????public?NewtonMethod(double?originalX,?double?e,?double?maxCycle)?{?? ????????this.setOriginalX(originalX);?? ????????this.setE(e);?? ????????this.setMaxCycle(maxCycle);?? ????} ? ?????? ????public?double?getOriginalX()?{?? ????????return?originalX;?? ????} ? ????public?void?setOriginalX(double?originalX)?{?? ????????this.originalX?=?originalX;?? ????} ? ????public?double?getE()?{?? ????????return?e;?? ????} ? ????public?void?setE(double?e)?{?? ????????this.e?=?e;?? ????} ? ????public?double?getMaxCycle()?{?? ????????return?maxCycle;?? ????} ? ????public?void?setMaxCycle(double?maxCycle)?{?? ????????this.maxCycle?=?maxCycle;?? ????} ? ????? ? ? ? ?? ????public?double?getOriginal(double?x)?{?? ????????return?x?*?x?-?3?*?x?+?2;?? ????}?? ?? ????? ?? ? ? ?? ????public?double?getOneDerivative(double?x)?{?? ????????return?2?*?x?-?3;?? ????} ? ????? ?? ? ? ?? ????public?double?getTwoDerivative(double?x)?{?? ????????return?2;?? ????} ? ????? ? ? ?? ????public?double?getNewtonMin()?{?? ????????double?x?=?this.getOriginalX();?? ????????double?y?=?0;?? ????????double?k?=?1;?? ?????????? ????????while?(k?<=?this.getMaxCycle())?{?? ????????????y?=?this.getOriginal(x);?? ????????????double?one?=?this.getOneDerivative(x);?? ????????????if?(Math.abs(one)?<=?e)?{?? ????????????????break;?? ????????????}?? ????????????double?two?=?this.getTwoDerivative(x);?? ????????????x?=?x?-?one?/?two;?? ????????????k++;?? ????????}?? ????????return?y;?? ????}?? ?? } ?
2、全局牛頓法Java實現(xiàn)
[java]?view plaincopy
package?org.algorithm.newtonmethod;?
public?class?GlobalNewtonMethod?{?? ????private?double?originalX;?? ????private?double?delta;?? ????private?double?sigma;?? ????private?double?e;?? ????private?double?maxCycle;?? ?? ????public?GlobalNewtonMethod(double?originalX,?double?delta,?double?sigma,?? ????????????double?e,?double?maxCycle)?{?? ????????this.setOriginalX(originalX);?? ????????this.setDelta(delta);?? ????????this.setSigma(sigma);?? ????????this.setE(e);?? ????????this.setMaxCycle(maxCycle);?? ????}?? ?? ????public?double?getOriginalX()?{?? ????????return?originalX;?? ????}?? ?? ????public?void?setOriginalX(double?originalX)?{?? ????????this.originalX?=?originalX;?? ????}?? ?? ????public?double?getDelta()?{?? ????????return?delta;?? ????}?? ?? ????public?void?setDelta(double?delta)?{?? ????????this.delta?=?delta;?? ????}?? ?? ????public?double?getSigma()?{?? ????????return?sigma;?? ????}?? ?? ????public?void?setSigma(double?sigma)?{?? ????????this.sigma?=?sigma;?? ????}?? ?? ????public?double?getE()?{?? ????????return?e;?? ????}?? ?? ????public?void?setE(double?e)?{?? ????????this.e?=?e;?? ????}?? ?? ????public?double?getMaxCycle()?{?? ????????return?maxCycle;?? ????}?? ?? ????public?void?setMaxCycle(double?maxCycle)?{?? ????????this.maxCycle?=?maxCycle;?? ????}?? ?? ????? ? ? ? ? ?? ????public?double?getOriginal(double?x)?{?? ????????return?x?*?x?-?3?*?x?+?2;?? ????}?? ?? ????? ? ? ? ? ?? ????public?double?getOneDerivative(double?x)?{?? ????????return?2?*?x?-?3;?? ????}?? ?? ????? ? ? ? ? ?? ????public?double?getTwoDerivative(double?x)?{?? ????????return?2;?? ????}?? ?? ????? ? ? ? ?? ????public?double?getGlobalNewtonMin()?{?? ????????double?x?=?this.getOriginalX();?? ????????double?y?=?0;?? ????????double?k?=?1;?? ?????????? ????????while?(k?<=?this.getMaxCycle())?{?? ????????????y?=?this.getOriginal(x);?? ????????????double?one?=?this.getOneDerivative(x);?? ????????????if?(Math.abs(one)?<=?e)?{?? ????????????????break;?? ????????????}?? ????????????double?two?=?this.getTwoDerivative(x);?? ????????????double?dk?=?-one?/?two;?? ????????????double?m?=?0;?? ????????????double?mk?=?0;?? ????????????while?(m?<?20)?{?? ????????????????double?left?=?this.getOriginal(x?+?Math.pow(this.getDelta(),?m)?? ????????????????????????*?dk);?? ????????????????double?right?=?this.getOriginal(x)?+?this.getSigma()?? ????????????????????????*?Math.pow(this.getDelta(),?m)?? ????????????????????????*?this.getOneDerivative(x)?*?dk;?? ????????????????if?(left?<=?right)?{?? ????????????????????mk?=?m;?? ????????????????????break;?? ????????????????}?? ????????????????m++;?? ????????????}?? ????????????x?=?x?+?Math.pow(this.getDelta(),?mk)*dk;?? ????????????k++;?? ????????}?? ????????return?y;?? ????}?? } ?
3、主函數(shù)
[java]?view plaincopy
package?org.algorithm.newtonmethod;
public?class?TestNewton?{?? ????public?static?void?main(String?args[])?{?? ????????NewtonMethod?newton?=?new?NewtonMethod(0,?0.00001,?100);?? ????????System.out.println("基本牛頓法求解："?+?newton.getNewtonMin());?? ?? ????????GlobalNewtonMethod?gNewton?=?new?GlobalNewtonMethod(0,?0.55,?0.4,?? ????????????????0.00001,?100);?? ????????System.out.println("全局牛頓法求解："?+?gNewton.getGlobalNewtonMin());?? ????}?? ?}?
總結(jié)
以上是生活随笔為你收集整理的牛顿迭代优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
