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

牛頓法牛頓法為求解非線方程的種經(jīng)典的迭方法，的收斂速度，有內(nèi)函數(shù)可直接使用。合著可以對(duì)其進(jìn)行用，求方程。牛頓迭代法（又稱為牛頓拉夫遜法（Newton-Raphsonmethod是牛頓17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法,其基本思想是利用目標(biāo)函數(shù)的二次展開，并將其極小化。牛頓法使用函數(shù)f前面幾項(xiàng)來尋方程f法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程f具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根，此時(shí)非線性收斂，但是可通過一些方法變成線性收斂。牛頓法的幾何解釋：方程

*

可解釋為曲線f焦點(diǎn)的橫坐標(biāo)。如下圖：設(shè)x是根*的某個(gè)近似值，過曲線yfx的P引切線，并k將該切線與x軸的交點(diǎn)橫坐標(biāo)牛頓法亦稱為切線法。2牛頓代公式：最下法（）

k

作為x*的新的近似值。鑒于這種幾何背景，/

Tk2Tk2以負(fù)梯度方向作為極小化算法的下降方向，也稱為梯度法。設(shè)函數(shù)f近連續(xù)可微，且kk

由泰勒展開式：f

k

k

k

（*）k可知，若記xk

，則滿dk

T

g的方d是下降方向。當(dāng)k

取定后，d

T

g的值越小，

T

g的值越大，函數(shù)下降的越快。由不等式：

Tk

k

k

，故當(dāng)且僅時(shí)kkk

T

g最小，從而是最速下降k方向。最速下降法的迭代格式為：x

k

k

k

。k（牛法設(shè)f函數(shù)，xR

n

，

2

fx附近用二次Taylor開近似f，f

s

s

12

sTfsqk

的二次近似。將上式右邊極小化，便得：x

x

2

f

x

x

，

這就是牛頓法的迭代公式。在這個(gè)公式里，步長因Gf也可kkkk寫成：

G

顯然，牛頓法也可以看成在橢球范數(shù)

下的最速下降法。G

事實(shí)上，對(duì)于，ks是極小化問題min

gs的解極小化問題依賴于所取的范數(shù)采l范數(shù)時(shí)s，所得方法為最速下降法。當(dāng)采用橢球范數(shù)kk

G

時(shí)，s，所得方法即為牛頓法。k/

對(duì)于正定二次函數(shù)牛頓法一步即可達(dá)到最優(yōu)解而對(duì)于非二次函數(shù)牛頓法并不能保證有限次迭代求得最優(yōu)解，但由于目標(biāo)函數(shù)在極小點(diǎn)附近近似于二次函數(shù)，故當(dāng)初始點(diǎn)靠近極小點(diǎn)時(shí)，牛頓法的收斂速度一般是快的。牛法斂理設(shè)f2充分靠x*k

0

2

f矩G滿足Lipschitz條件，即存

，使得對(duì)所有i,j，有：Gij

x

Gij

y

xy，其矩Gk，牛頓迭代公式有意義，ij且所得序*，并且具有二階收斂速度。在實(shí)際求解中，當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)解時(shí)，Hesse矩不一定正定。牛頓方k向不一定是下降方向其收斂性不能保證這說明恒取步長因子為牛頓法是不合適的，應(yīng)該在牛頓法中采用某種一維搜索來確定步長因子。但是應(yīng)該強(qiáng)調(diào)，僅當(dāng)步長因?yàn)椋?/p>

時(shí)牛頓法才是二階收斂的時(shí)牛頓法的迭代公式

，

x

k

xk

k

k其是一維搜索產(chǎn)生的步長因子。k帶步長因子牛頓法步1選取初始數(shù)據(jù)，取初始點(diǎn)x，終止誤0

，k。步2計(jì)算。若kk

，停止迭代，輸出，否則進(jìn)行步3.k步3解方程組構(gòu)造牛頓方向，即Gd，求d。k步4進(jìn)行一維搜索，得kf

xkk

k

k令xk

xk

k

,k:k

轉(zhuǎn)步2/

f1x1f1x1牛頓法的計(jì)算步驟：步驟1

準(zhǔn)備

選定初始近似值，計(jì)算ff0

0

，f

'0

f

'

0

。步驟2

迭代

按公式：fx010'0

迭代一次，得新的近似值x，1ff'f'11步驟3

控制

如果x滿足11

，或f1

2

，則終止迭代，以x作為所求的1根；否則轉(zhuǎn)步驟4.此處1

,

2

是允許誤差，而：

當(dāng)時(shí)；1011,當(dāng)x時(shí)，其中C是取絕對(duì)誤差或相誤差的控制常數(shù)，一般可C=1。步驟4

修改

如果迭代次數(shù)達(dá)到預(yù)先制定的次數(shù)N者f

'1

=0法失敗；否則f,f11

'1

f00

'0

繼續(xù)迭代。4牛頓法的進(jìn)在優(yōu)化問題的計(jì)算中牛頓迭代法是非線性方程求根中一種很實(shí)用的方法它具有簡單的迭代格式和較快的收斂速度，它二次收斂到單根，線性收斂到重根。數(shù)值計(jì)算中的經(jīng)典牛頓法面臨的主要問題是Hesse矩G不正定，這時(shí)候二次模型不一定有極k小點(diǎn)，甚至沒有平穩(wěn)點(diǎn)。G不定時(shí)，二次模型函數(shù)是無界的。和（出G非正定時(shí)用最速下降方Goldfeldk等人1966年）提出了一種修正方法，即使牛頓方向偏向最速下降方向。更k明確的說是將模型的Hesse矩改變GIvGIkkk正定。該算法的框架如下：給出初始點(diǎn)。第步迭代為：0/

k__kk__k（1）令I(lǐng)其中：kv，如G正定v否則。kkk（2）計(jì)G的Cholesky分解GDT。kk（3）G。k（4）xk

xk

k牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計(jì)算

f

'

，計(jì)算量較大且有時(shí)

'

難，二是初始近似值x只在根*0

附近才能保證收斂，如x給的不合適可能不收斂。0為克服這兩個(gè)缺點(diǎn)，通?？梢韵率鰞蓚€(gè)方法：（1）簡化牛頓法，也稱平行弦法。其迭代公式為，

k迭代函

（2）牛頓下山法：牛頓法的收斂性依賴于初始的選取。如x偏離所求根00*

較遠(yuǎn)，則牛頓法可能發(fā)散。為防止迭代發(fā)散迭代過程再附加一項(xiàng)要求，即具有單調(diào)性：f

k

k

滿足這