最優(yōu)化理論方法-牛頓法

牛頓法牛頓法作為求解非線性方程的一種經(jīng)典的迭代方法，它的收斂速度快，有內(nèi)在函數(shù)可以直接使用。結(jié)合著matlab可以對其進(jìn)行使用，求解方程。牛頓迭代法(Newton'smethod)又稱為牛頓-拉夫遜方法(Newton-Raphsonmetho),它是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法其基本思想是利用目標(biāo)函數(shù)的二次丫1?！刚归_，并將其極小化。牛頓法使用函數(shù)fG)的泰勒級數(shù)的前面幾項來尋找方程fG)=o的根。牛頓法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程fG)=0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根，此時非線性收斂，但是可通過一些方法變成線性收斂。牛頓法的幾何解釋：kkX(*)方程fG)=0的根X*可解釋為曲線y=fG)與kkX(*)f(1=fX)+(Xk可知，若記為X-X=ad，則滿足dTg<0的方向d是下降方向。當(dāng)a取定后，kk kk kdTg的值越小，即-dTg的值越大，函數(shù)下降的越快。由Cauchy-Schwartz不等kk kk式：dTg<11dllIIg，故當(dāng)且僅當(dāng)d=-g時，dTg最小，從而稱-g是最速下降kk"k^ ''k kk kk k方向。最速下降法的迭代格式為：X=X-ag。k+1 kkk(2)牛頓法：

設(shè)/設(shè)/6)是二次可微實(shí)函數(shù)，xeRn,kHesse矩陣V?fG)正定。在x附近2stV2f2stV2f(x)s+s)?q(k)(s)=f(x>s+Vf(x)tkks=x-x,q(k)(s)為f(x)的二次近似。將上式右邊極小化，便得:kx=x-「V2f(x%Vf(x)， 這就是牛頓法的迭代公式。k+1kL k」 k在這個公式里，步長因子a=1。令G=V2f(x),g=Vf(x)，則上式也可k k kk k寫成：x=x一G-1gk+1kkk顯然，牛頓法也可以看成在橢球范數(shù)Ihi下的最速下降法。七上事實(shí)上，對于f(x+s)2f(x)+gTs，k kks是極小化問題mingTs的解。該極小化問題依賴于所取的范數(shù)，當(dāng)采取l范k seRn|s 2數(shù)時，s=-g，所得方法為最速下降法。當(dāng)采用橢球范數(shù)/時，kk Gks=-G-ig，所得方法即為牛頓法。k kk對于正定二次函數(shù)，牛頓法一步即可達(dá)到最優(yōu)解。而對于非二次函數(shù)，牛頓法并不能保證有限次迭代求得最優(yōu)解，但由于目標(biāo)函數(shù)在極小點(diǎn)附近近似于二次函數(shù)，故當(dāng)初始點(diǎn)靠近極小點(diǎn)時，牛頓法的收斂速度一般是快的。牛頓法收斂定理：設(shè)feC(2)，x充分靠近x*，Vf(x*)=0，如果V2f(x*)正定，且Hesse矩陣G(x)k滿足Lipschitz條件，即存在P>0，使得對所有i,j，有:Gj(x)-G(y)佰P||x-y||，其中G(x)是Hesse矩陣G(x)的(i,j)元素，則對一切k，牛頓迭代公式有意義，jj且所得序列｛x｝收斂到x*，并且具有二階收斂速度。k在實(shí)際求解中，當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)解時，Hesse矩陣G不一定正定。牛頓方k向不一定是下降方向，其收斂性不能保證。這說明恒取步長因子為1的牛頓法是不合適的，應(yīng)該在牛頓法中采用某種一維搜索來確定步長因子。但是應(yīng)該強(qiáng)調(diào)，僅當(dāng)步長因子｛a｝收斂到1時，牛頓法才是二階收斂的。這時牛頓法的迭代公式k為：d=—g—ig x=x+adkk°k，k+1 kkk其中a是一維搜索產(chǎn)生的步長因子。k帶步長因子的牛頓法步1選取初始數(shù)據(jù)，取初始點(diǎn)x，終止誤差￡>0，令k=0。0步2計算且卜。若||g』<￡，停止迭代，輸出xk,否則進(jìn)行步3.步3解方程組構(gòu)造牛頓方向，即解Gd=-g，求出d。kk k步4進(jìn)行一維搜索，求a使得kf(x+ad)=minf+adkkk k ka>0令x=x+ad,k:=k+1轉(zhuǎn)步2k+1kkk牛頓法的計算步驟：TOC\o"1-5"\h\z步驟1準(zhǔn)備選定初始近似值x，計算f=f(x)，f'=f'(x)。0 0 00 0步驟2迭代按公式：x=x-f迭代一次，得新的近似值x，10f1 10\o"CurrentDocument"f=f(x)，f'=f'(x)。1 11 1步驟3控制如果x滿足憐<8，或[f<8，則終止迭代，以x作為所求的1 1 1 11 2 1根；否則轉(zhuǎn)步驟4.此處，8,8是允許誤差，而：12卜70|,當(dāng)囪<C時；3=[^^,當(dāng)|x|>C時，〔x1其中C是取絕對誤差或相對誤差的控制常數(shù)，一般可取C=1。步驟4修改如果迭代次數(shù)達(dá)到預(yù)先制定的次數(shù)N，或者廣=0，則方法失敗;1否則以Q,f,f)代替(x,f,f')，轉(zhuǎn)步驟2繼續(xù)迭代。111 0004牛頓法的改進(jìn)在優(yōu)化問題的計算中，牛頓迭代法是非線性方程求根中一種很實(shí)用的方法，它具有簡單的迭代格式和較快的收斂速度，它二次收斂到單根，線性收斂到重根。數(shù)值計算中的經(jīng)典牛頓法面臨的主要問題是Hesse矩陣G不正定，這時候二次模型不一定有極k小點(diǎn)，甚至沒有平穩(wěn)點(diǎn)。當(dāng)G不定時，二次模型函數(shù)是無界的。kGoldstein和Price(1967)提出當(dāng)G非正定時，采用最速下降方向-goGoldfeldkk等人(1966年)提出了一種修正方法，即使牛頓方向偏向最速下降方向-鼻。更明確的說，就是將模型的Hesse矩陣G改變成G+y乙其中v>0，使得G+vIk kk k kk正定。該算法的框架如下：給出初始點(diǎn)xeRn。第k步迭代為：0(1)^令^二G+vI,其中：kkkv=0，如果G正定；v>0,否則。k kk(2)計算G的Cholesky分解，G=LDL。k kkkk(3)解Gd=—g得dok kk(4)令x=x+dk+1kk牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計算f(x)0'(x),計算量較kk大且有時f'(x)計算較困難，二是初始近似值x只在根x*附近才能保證收斂，k0如x給的不合適可能不收斂。0為克服這兩個缺點(diǎn)，通?？梢韵率鰞蓚€方法：(1)簡化牛頓法，也稱平行弦法。其迭代公式為，x=x-Cf(x),C中0,1,k+1k k迭代函數(shù)9(x)=x一Cf(x)o???(2)牛頓下山法：牛頓法的收斂性依賴于初始值x的選取。如果x偏離所求根00x*較遠(yuǎn)，則牛頓法可能發(fā)散。為防止迭代發(fā)散，對迭代過程再附加一項要求，即具有單調(diào)性：f(x)|<f(x)滿足這項要求的算法稱下山法。將牛頓法與下山法結(jié)合k+11 k起來使用，即在下山法保證函數(shù)值穩(wěn)定