牛頓法至少有兩個(gè)應(yīng)用方向，1、求方程的根，2、最優(yōu)化。牛頓法涉及到方程求導(dǎo)，下面的討論均是在連續(xù)可微的前提下討論。

?

1、求解方程。

并不是所有的方程都有求根公式，或者求根公式很復(fù)雜，導(dǎo)致求解困難。利用牛頓法，可以迭代求解。

原理是利用泰勒公式，在x0處展開，且展開到一階，即f(x) = f(x0)+(x－x0)f'(x0)

求解方程f(x)=0，即f(x0)+(x-x0)*f'(x0)=0，求解x =?x1=x0－f(x0)/f'(x0)，因?yàn)檫@是利用泰勒公式的一階展開，f(x) = f(x0)+(x－x0)f'(x0)處并不是完全相等，而是近似相等，這里求得的x1并不能讓f（x）=0，只能說f(x1)的值比f(x0)更接近f（x）=0，于是乎，迭代求解的想法就很自然了，可以進(jìn)而推出x(n+1)=x(n)－f(x(n))/f'(x(n))，通過迭代，這個(gè)式子必然在f（x*）=0的時(shí)候收斂。整個(gè)過程如下圖：

?

2、牛頓法用于最優(yōu)化

在最優(yōu)化的問題中，線性最優(yōu)化至少可以使用單純行法求解，但對(duì)于非線性優(yōu)化問題，牛頓法提供了一種求解的辦法。假設(shè)任務(wù)是優(yōu)化一個(gè)目標(biāo)函數(shù)f，求函數(shù)f的極大極小問題，可以轉(zhuǎn)化為求解函數(shù)f的導(dǎo)數(shù)f'=0的問題，這樣求可以把優(yōu)化問題看成方程求解問題（f'=0）。剩下的問題就和第一部分提到的牛頓法求解很相似了。

這次為了求解f'=0的根，把f（x）的泰勒展開，展開到2階形式：

這個(gè)式子是成立的，當(dāng)且僅當(dāng)?Δx?無線趨近于0。此時(shí)上式等價(jià)與：

求解：

得出迭代公式：

一般認(rèn)為牛頓法可以利用到曲線本身的信息，比梯度下降法更容易收斂（迭代更少次數(shù)），如下圖是一個(gè)最小化一個(gè)目標(biāo)方程的例子，紅色曲線是利用牛頓法迭代求解，綠色曲線是利用梯度下降法求解。

在上面討論的是2維情況，高維情況的牛頓迭代公式是：

其中H是hessian矩陣，定義為：

?

高維情況依然可以用牛頓迭代求解，但是問題是Hessian矩陣引入的復(fù)雜性，使得牛頓迭代求解的難度大大增加，但是已經(jīng)有了解決這個(gè)問題的辦法就是Quasi-Newton methond，不再直接計(jì)算hessian矩陣，而是每一步的時(shí)候使用梯度向量更新hessian矩陣的近似。

擬牛頓法基本思想

上一節(jié)指出，牛頓法收斂速度快，但是計(jì)算過程中需要計(jì)算目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)，難度較大；目標(biāo)函數(shù)的Hesse矩陣無法保持正定，從而令牛頓法失效。

為了解決這兩個(gè)問題，人們提出了擬牛頓法，即“模擬”牛頓法的改進(jìn)型算法。基本思想是不用二階偏導(dǎo)數(shù)而構(gòu)造出可以近似Hesse矩陣的逆的正定對(duì)稱陣，從而在“擬牛頓”的條件下優(yōu)化目標(biāo)函數(shù)。Hesse陣的構(gòu)造方法的不同決定了不同的擬牛頓法。

SR1算法

SR1算法是一個(gè)非常有特色的擬牛頓算法，有許多改進(jìn)的SR1算法研究。其中，SR1的一個(gè)突出優(yōu)點(diǎn)是在極小正定二次目標(biāo)函數(shù)時(shí)無需線搜索仍具有至多n步的終止性質(zhì)。

BFGS算法

BFGS算法是Broyden，Fletcher，Goldfarb，Shanno四位優(yōu)化大家在1970年幾乎同時(shí)從不同的優(yōu)化角度提出的。從發(fā)明到現(xiàn)在的40多年時(shí)間里，它仍然被認(rèn)為是最好的擬牛頓算法。

DFP算法

DFP算法是以Davidon、Fletcher、Powell發(fā)明人的名字首字母命名的。

DFP算法也是一種秩2的修正算法。推導(dǎo)步驟和BFGS算法是類似的，并且兩種修正公式之間構(gòu)成了對(duì)偶關(guān)系。記憶時(shí)候，可以只記住一種修正公式，然后利用對(duì)偶關(guān)系寫出另一種。

族算法

BFGS修正公式和DFP修正公式的加權(quán)線性組合構(gòu)成一類修正共識(shí)，其中含有一個(gè)參數(shù)的稱為Broyden族修正公式

后來人們又發(fā)展出含有兩個(gè)參數(shù)的Oren族算法和含有三個(gè)參數(shù)的Huang族算法。之所以開發(fā)這些算法，目的就是為了找到一個(gè)能夠超越BFGS的更優(yōu)算法。然而，經(jīng)過40多年的努力，這個(gè)愿望至今還沒有實(shí)現(xiàn)。

收斂性及進(jìn)一步修正

擬牛頓法對(duì)于一般非二次函數(shù)的收斂性，最早由Powell于1971年給出。目前得到的收斂結(jié)果都是假設(shè)目標(biāo)函數(shù)是凸的。對(duì)于一般的非凸目標(biāo)函數(shù)，擬牛頓法的收斂性還沒有統(tǒng)一的證明，只散見個(gè)別的案例。

比如，當(dāng)用于非凸函數(shù)極小值問題求解時(shí)，有例子表明BFGS采用精確線性搜索或者W-P搜索不收斂，而BFGS又是十分好用的算法，于是在為了克服BFGS的缺陷，又產(chǎn)生了不少修正算法，如MBFGS、CBFGS等。

總結(jié)

以上是生活随笔為你收集整理的牛顿法求极大极小值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。