牛頓法(Newton method)和擬牛頓法(quasi-Newton method)也是求解無約束最優化問題的常用方法，具有收斂速度快的優點。

牛頓法是迭代算法，每一步需要求解目標函數的海賽矩陣的逆矩陣，計算比較復雜。

擬牛頓法通過正定矩陣近似海賽矩陣的逆矩陣或海賽矩陣，簡化了這一計算過程。

本篇設計的算法有：牛頓法、擬牛頓法、DFP算法、BFGS算法、L-BFGS算法、Broyden類算法。

1.牛頓法

對于一個無約束問題：

，求該目標函數的極小值點。

我們知道，通常情況下對于目標函數來說，極小值點的一階導數為0。

而

的二階泰勒展開為：

其中，

,即為 的梯度向量在點 處的值； 是 的海賽矩陣（Hesse matrix）

那么函數的一階導數(對上面的二階泰勒展開求導)就可以表示為：

上式就是我們的一階導函數的直線近似，即上式為通過原函數的一階導函數在點

上的切線。

https://blog.csdn.net/u012294618/article/details/79750224

如上圖所示，已知第

次迭代得到的切線方程為： ；

我們令其為0得到：

；

從而解得第

次迭代點為： 。此時得到了一條新的切線，若目標函數為凸函數，則這個新的迭代點是逐步接近于極小值點的。

這個就是牛頓法！

但是我們可以看見在每一次的迭代過程中，都要涉及到

的計算，實際應用中，我們不直接計算它，而是將它轉化為求解線性代數方程組的形式：令 ，即 ，此時迭代過程變成：

來說一次，這就是牛頓法！！

牛頓法的迭代公式中由于沒有步長因子，是定步長迭代，對于非凸目標函數，有時會使函數值上升，即出現

的情況，甚至最終發散導致計算失敗。為了盡量避免這種情況發生，可以采用“阻尼牛頓法”，即增加了一個步長因子 ，將迭代式修改為：

牛頓法的一些致命缺點：

1.海賽矩陣的逆矩陣計算

計算量可能很大；

2.海賽矩陣可能無法保持正定，這樣就無法計算

，此時牛頓法失效。

這時我們就應該思考了，能不能繞過

的計算呢？擬牛頓法就可以。

2.擬牛頓法

擬牛頓法的基本思想是：不用求二階偏導數而構造出可以近似海賽矩陣（或海賽矩陣的逆）的正定對稱陣。

不同的構造方法對應能夠產生不同的擬牛頓法。（可以理解成，"擬牛頓法"是來近似"牛頓法"的，所以在“牛頓法”前面加了一個“擬”字。擬牛頓法可不止一種，它包含多種方法：如DFP算法、BFGS算法、Broyden類算法。）

我們說了，我們要構造一個近似海賽矩陣（或海賽矩陣的逆）的正定矩陣，首先需要滿足擬牛頓條件。

（1）擬牛頓條件

對

做泰勒展開我們得到了以下近似：

假設找到了下一步迭代點

，則有： 。

記

，則：

上述就是擬牛頓條件，即我們選擇的

的替補，應當滿足上面的條件才行。

從擬牛頓條件我們可知，有兩種替補方式：

1)選擇

作為 的替補。即 (Davidon-Fletcher-Powell)算法；

2)選擇

作為 的替補。即 (Broyden-Fletcher-Goldfarb-Shanno)算法。這兩種算法通稱“擬牛頓法”，這兩個算法名稱縮寫看起來高大上，但其實就是幾個人名的首字母縮寫，沒有什么高大上的含義。

（2）DFP算法

DFP算法用

作為 的近似或替補，我們知道海賽矩陣的更新是每一個迭代步驟上計算二階偏導得到的，此時用 做近似了之后怎么更新呢？我們直接給出更新公式：

可以證明，如果初始矩陣

是正定對稱的，則迭代過程中的每個矩陣 都是正定對稱的。并且一般我們取初始矩陣 ，即取初始矩陣為單位陣。那么每一步迭代中的 都能通過上式得到。

此時有個疑問，計算

時，要用到 ，這個值如何確定的？是這么來的：

是當前點的一階導，是可以計算出來的；我們置 ；進行一維搜索：求 使得 ；置 。

這就繞過了

的計算。

可以對照算法過程來理解，DFP算法過程如下：

輸入：目標函數

，梯度 ，精度要求 ；

輸出：

的極小點 。

1）選定初始點

，取 為正定對稱矩陣，置

2）計算

。若 ，則停止計算，得近似解 ；否則轉第3步

3）置

4）一維搜索：求

使得

5）置

6）計算

，若 ，則停止計算，得近似解 ；否則，按式 算出

7）置

，轉到第3步。

（3）BFGS算法

BFGS算法是最流行的你牛頓算法。它與DFP相比，性能更佳。該算法是用

來近似海賽矩陣 。同DFP算法，我們也直接給出 的迭代公式：

同DFP算法，也可以證明，如果初始矩陣

是正定對稱的，則迭代過程中的每個矩陣 都是正定對稱的。并且一般我們取初始矩陣 ，即取初始矩陣為單位陣。那么每一步迭代中的 都能通過上式得到。

BFGS的算法流程與DFP相似，如下：

輸入：目標函數

，梯度 ，精度要求 ；

輸出：

的極小點 。

1）選定初始點

，取 為正定對稱矩陣，置

2）計算

。若 ，則停止計算，得近似解 ；否則轉第3步

3）由

求出

4）一維搜索：求

使得

5）置

6）計算

，若 ，則停止計算，得近似解 ；否則，按式 算出

7）置

，轉到第3步。

上述就是具體地算法過程了，當然，我們也可以從BFGS算法矩陣

的迭代公式得到BFGS算法關于 的迭代公式。

首先我們介紹Sherman-Morrison公式（謝爾曼莫里森公式）：假設

是n階可逆矩陣， 是n維向量，且 也是可逆矩陣，則

這就是Sherman-Morrison公式。

如果我們記

，那么對 的迭代公式 兩次應用Sherman-Morrison公式得到 的迭代公式：

即稱此式為BFGS算法關于

的迭代公式。（公式的具體推導過程請參考本專欄的另一篇文章https://zhuanlan.zhihu.com/p/91230555）

（4）L-BFGS算法

在BFGS算法中，每一步迭代都需要用到一個

階矩陣 ，當 很大時，存儲這個矩陣將消耗大量計算機資源，需要的存儲空間大小為 。

L-BFGS算法就是為了解決這個問題而提出的，其目的是減少BFGS算法迭代過程中所需的內存開銷。

L-BFGS（Limited-memory BFGS或Limited-storage BFGS）是BFGS算法的進一步近似。其基本思想是：不再存儲完整的矩陣

，而是存儲計算過程中的向量序列 ，需要矩陣 時，利用向量序列 的計算來代替。而且，向量序列 也不是所有的都存儲，而是保留最新的 個，每次計算 時，只利用最新的 個向量序列。這樣一來，存儲空間由原來的 降至 。

（5）Broyden類算法

根據前面的內容，我們將由DFP算法中

的迭代公式得到的 記作 ；將由BFGS算法中 的迭代公式得到的 記作 ，它們都滿足擬牛頓條件，并且都是正定的，所以它們的線性組合

也滿足擬牛頓條件而且是正定的。其中

。

這樣，根據取不同的

值，就可以得到一系列的擬牛頓法，稱為Broyden類算法。

上面的所有擬牛頓算法都僅僅是簡述，例如DFP和BFGS算法的迭代公式沒有推導其由來，L-BFGS算法也僅僅是提了一下。如果需要深入理解，可以參考下面的這個博客鏈接：

https://blog.csdn.net/songbinxu/article/details/79677948

總結

以上是生活随笔為你收集整理的二阶偏微分方程组 龙格库塔法_牛顿法和拟牛顿法——（书中附录B）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。