最佳化的牛頓法（Newton's method for optimization）
/ NOO-tun /
最速下降只感覺得到斜率，像在霧中下坡卻不知谷地如何彎曲。牛頓法還感覺得到曲率：它不只知道哪邊是下坡，更知道地面如何彎，因此能一個大膽的跳躍直接瞄準局部碗的底部。在梯度下降緩爬鋸齒之處，牛頓法——當它管用時——收斂快得驚人。
其想法是用二階泰勒展開（一個二次碗）在 x_k 附近模擬函數，然後跳到那個碗的底部。二次式為 m(p) = f(x_k) + grad f(x_k)^T p + (1/2) p^T H_k p，其中 H_k 是海森（曲率）矩陣。令模型的梯度為零求其極小，得到牛頓步 H_k p = -grad f(x_k)，即 p = -H_k^{-1} grad f(x_k)，並 x_{k+1} = x_k + p（為安全常配一個線搜尋步長）。注意這其實就是把求解方程 grad f(x) = 0——一階最佳性條件——的牛頓法，套用到向量函數上。在海森正定的局部極小附近，誤差每步平方：這就是二次收斂，每次迭代正確位數倍增，所以幾步就達到完整的雙精度。
難處是真實的，值得直說。第一，你需要海森矩陣，且每步要解一個 n×n 線性系統——約 O(n^3) 運算與 O(n^2) 儲存——當 n 很大時不可承受（這就是擬牛頓法與 L-BFGS 存在的理由）。第二，快速收斂只是局部的：遠離極小，或海森非正定時（鞍點或極大附近），原始牛頓步可能指向上坡、劇烈越過頭，或收斂到錯誤類型的駐點。所以實務的「加保險」牛頓法會把海森修正成正定，並加上線搜尋或信賴域，用一部分原始速度換取全域可靠性。
從 x_0 = 2 最小化 f(x) = x^4 - 3x^2 + 2。此處 f'(x) = 4x^3 - 6x、f''(x) = 12x^2 - 6，牛頓步為 x_{k+1} = x_k - f'(x_k)/f''(x_k)。從 2 跳到約 1.30、再到 1.05、再到極接近真正極小點 sqrt(3/2) = 1.2247...，誤差大致每步平方而迅速逼近。
用曲率跳到二次模型的底部——誤差每步平方。
二次收斂是局部且有條件的：僅在海森正定的極小附近、且起點不差時成立。在遠處或鞍點附近，原始牛頓步可能上升或發散——所以必須以修正後的海森加上線搜尋或信賴域來加保險。