小樂數學科普：三百年后，艾薩克·牛頓的工具得到更新——譯自量子雜志Quanta Magazine

一種簡單而廣泛使用的數學技術最終可以應用于無限復雜的問題。

圖源：Michele Sclafani|Quanta Magazine

點擊zzllrr小樂公眾號主頁右上角設為星標★數學科普不迷路！

作者：Kevin Hartnett（量子雜志特約撰稿人）2025-3-24

譯者：zzllrr小樂（數學科普公眾號）2025-3-25

研究人員每天都在尋找最優解。他們可能想知道在哪里建立一個主要航空樞紐。或者確定如何在投資組合中最大化回報同時最小化風險。或者開發能夠區分交通信號燈和停車標志的自動駕駛汽車。

從數學上講，這些問題可以轉化為尋找函數的最小值。但在所有這些情況下，函數都過于復雜，無法直接評估。取而代之的是，研究人員必須得到近似的最小值。

事實證明，實現這一目標的最佳方法之一是使用艾薩克·牛頓（Isaac Newton，1643 - 1727）300多年前開發的一種算法。該算法相當簡單。有點像蒙著眼睛在陌生的地形中尋找最低點。當你邁開雙腳時，你唯一需要的信息就是你是在上坡還是下坡，以及坡度是上升還是下降。利用這些信息，你可以相對快速地得到最小值的近似值。

盡管牛頓法非常強大——幾個世紀后，它仍然是解決當今物流、金融、計算機視覺甚至純數學問題的關鍵——但它也有一個明顯的缺點。它并不適用于所有函數。因此，數學家們一直在研究這項技術，想出不同的方法來擴大其應用范圍，同時又不犧牲效率。

去年夏天，三位研究人員公布了牛頓法的最新改進 https://arxiv.org/abs/2311.06374 。普林斯頓大學的Amir Ali Ahmadi和他的前學生Abraar Chaudhry（現就職于佐治亞理工學院）和Jeffrey Zhang（現就職于耶魯大學）擴展了牛頓法，使其能夠有效地處理迄今為止最廣泛的函數類。

“牛頓法在最優化中有1000種不同的應用，”Ahmadi說道。“我們的算法有可能取代它。”

1680年代，艾薩克·牛頓發明了一種尋找最優解的算法。三個世紀后，數學家們仍在使用和完善他的方法。

圖源：Godfrey Kneller/公共領域

百年歷史的技術

數學函數將輸入轉換為輸出。通常，一個函數最重要的特征是其最小（輸入）值——產生最小可能輸出的輸入組合。

但找到最小值很難。函數可能有幾十個變量的高次冪，無法進行公式分析；它們的解的圖像形成高維景觀，無法從鳥瞰視角探索。牛津大學的Coralia Cartis說，在這些高維景觀中，“我們想找到一個山谷。有些是局部山谷；有些是最低點。你試圖找到這些東西，問題是：有什么信息可以指導你找到它們？”

1680年代，牛頓認識到，即使你處理的是非常復雜的函數，你仍然總能獲得至少兩條信息來幫助你找到它的最深谷。首先，你可以計算函數所謂的一階導數，即斜率：函數在給定點的陡度（坡度）。其次，你可以計算斜率本身的變化率（函數的二階導數）。

Amir Ali Ahmadi（阿米爾·阿里·艾哈邁迪）發現，無論何時何地，最優化問題都隨處可見。

圖源：Mathematisches Forschungsinstitut Oberwolfach奧伯沃爾法赫數學研究所檔案

假設你正在嘗試尋找某個復雜函數的最小值點。首先，選擇函數上你認為可能接近真實最小值的一點。計算該點處函數的一階和二階導數。這些導數可用于構造一個特殊的二次方程——如果你的函數位于二維平面中，則為拋物線（parabola）；如果你的函數是高維的，則是稱為拋物面（paraboloid）的杯狀形狀。這個二次方程稱為泰勒逼近（Taylor approximation，也稱泰勒近似），與你選擇的點處的函數大致相似。

現在計算二次方程的最小值點，而不是原始方程的最小值點——使用眾所周知的公式，你可以輕松地做到這一點。（這是因為二次方程很簡單；當方程變得更復雜時，計算最小值就變得困難了。）你會得到一個點。然后把這個點的坐標插回到你的原始函數中，你會得到一個函數上的新點，希望這個新點更接近它的真實最小值。然后重新開始整個過程。

牛頓證明，如果你不斷重復這個過程，你最終會找到原始更復雜函數的最小值。這種方法并不總是有效，特別是當你從離真實最小值太遠的點開始的時候。但在大多數情況下，它是有效的。而且它有一些理想的性質。

尋找最優解

在1680年代，艾薩克·牛頓發明了一種求函數最小值的方法它的最優解。幾個世紀后，數學家們仍然在使用他的算法。

1. 猜一猜

   在曲線上選擇一個起點，靠近你認為最小值可能所在的位置。

   
   

2. 繪制曲線模型

   生成一個大致類似于該點曲線的拋物線。

   
   

3. 找到下一個點

   計算拋物線的最小值，并使用它來移動到曲線上的新點。

   
   

4. 重復

   使用這個新起點，重復步驟2-3。

   
   

5. 繼續前進

   隨著你重復這些步驟，你會很快收斂到最小值。
   

圖源：Mark Belan/Quanta Magazine

原始來源：https://arxiv.org/abs/2305.07512

其他迭代方法，如梯度下降（gradient descent，當今機器學習模型中使用的算法）以線性速率收斂到真實最小值。牛頓法收斂速度要快得多：以“二次”速率。換句話說，它可以在比梯度下降更少的迭代次數中識別最小值。

牛頓法的每次迭代比梯度下降的迭代更耗費計算資源，這就是為什么研究人員在某些應用中更喜歡使用梯度下降，比如訓練神經網絡。但牛頓法仍然非常高效，使其在各種情況下都很有用。

如果牛頓不只是在每個點取一階和二階導數，而是取三階和四階導數，他本可以更快地編寫出收斂到真實最小值的方法。這將使他得到更復雜的泰勒近似值，指數大于2。

但他的策略的關鍵是將一個復雜的函數轉換成一個更簡單的函數。這些更復雜的泰勒方程超出了牛頓的數學處理能力。

?Jeffrey Zhang和他的合著者以正確的方式調整函數，從而拓寬了強大優化技術的范圍。?

圖源：Jeffrey Zhang

“牛頓對二次多項式進行了求解。他這樣做是因為沒有人知道如何最小化高階多項式，”Ahmadi說。

在此后的幾個世紀里，數學家們一直致力于擴展他的方法，探索從更復雜的函數泰勒近似中能榨出多少信息。

例如，在19世紀，俄羅斯數學家帕夫努蒂·切比雪夫（Pafnuty Chebyshev，1821 - 1894）提出了牛頓法的一個版本，用三次方程（指數為3）來逼近函數。但是當原始函數涉及多個變量時，他的算法不起作用。

更近的一次是在2021年，尤里·涅斯捷羅夫（Yurii Nesterov，現就職于布達佩斯考文紐斯大學）展示了如何用三次方程有效地近似任意數量變量的函數 https://link.springer.com/article/10.1007/s10107-019-01449-1 。

但他的方法無法擴展到使用四次方程、五次方程等來近似函數，否則會降低其效率。盡管如此，這一證明仍然是該領域的一個重大突破。

現在，Ahmadi、Chaudhry和Zhang將Nesterov的結果又推進了一步。他們的算法適用于任意數量的變量和任意數量的導數。此外，它在所有這些情況下仍然有效——這是迄今不可能實現的。

但首先，他們必須找到一種方法來讓難題變得更容易。

尋找回旋余地

目前還沒有一種快速、通用的方法來尋找高次函數的最小值點。這一直是牛頓法的主要限制。但有些類型的函數具有易于最小化的特征。在這項新研究中，Ahmadi、Chaudhry和Zhang證明總是可以找到具有這些特征的近似方程。然后他們展示了如何調整這些方程高效運用牛頓法。

什么性質使得方程式易于最小化？有兩點：

首先，方程式應該是碗狀的，或“凸的”（convex）。它只有一個谷值，而不是許多谷值——這意味著當你試圖最小化它時，你不必擔心將任意谷值誤認為最低谷值。

Abraar Chaudhry和兩位同事最近找到了一種方法來改進已有數百年歷史的尋找函數最小值點的方法。

圖源：Camille Carpenter Henriquez

第二個性質是方程可以寫成平方和。例如，5x2+16x+13 可以寫成 (x+2)2+(2x+3)2。近年來，數學家已經開發出最小化具有任意大指數的方程的技術，只要它們既是凸函數又是平方和。

然而，這些技術在牛頓法中用處不大。大多數情況下，你使用的泰勒近似不會具有這些良好的性質。

但是Ahmadi、Chaudhry和Zhang想出了如何使用一種名為半定規劃（semidefinite programming）的技術來對泰勒近似進行足夠的調整，使其既成為平方和又成為凸函數，但又不至于使其脫離它應該近似的原始函數。

他們實際上是在泰勒展開式中添加了一個修正因子，將其變成了具有兩種所需性質的方程。“我們可以稍微改變泰勒展開式，使其更容易最小化。考慮泰勒展開式，但稍作修改，”艾Ahmadi說。

他和他的同事隨后證明，使用這個修改版的泰勒展開式——涉及任意多個導數——他們的算法仍然會收斂到原始函數的真實最小值。

此外，收斂速度會隨著所用導數的數量而變化：正如使用兩個導數允許牛頓法以二次速率接近真實最小值一樣，使用三個導數使研究人員能夠以立方速率接近它，依此類推。

Ahmadi、Chaudhry和Zhang創建了一個更強大的牛頓法版本，與以前的技術相比，它可以用更少的迭代次數達到函數的真實最小值。

與牛頓法的原始版本一樣，這種新算法的每次迭代在計算上仍然比梯度下降等方法更昂貴。因此，目前，這項新工作不會改變自動駕駛汽車、機器學習算法或空中交通管制系統的運作方式。在這些情況下，最好的選擇仍然是梯度下降。

賓夕法尼亞大學的Jason Altschuler表示：“最優化領域的許多想法需要花費數年時間才能完全付諸實踐。但這似乎是一個全新的視角。”

如果隨著時間的推移，運行牛頓法所需的底層計算技術變得更加高效——使得每次迭代的計算成本更低——那么Ahmadi、Chaudhry和Zhang開發的算法最終可以在包括機器學習在內的各種應用中超越梯度下降。

“從理論上講，我們目前的算法確實更快，”Ahmadi說。他補充說，他希望10到20年后，該算法在實踐中也能保持更快。

參考資料

https://www.quantamagazine.org/three-hundred-years-later-a-tool-from-isaac-newton-gets-an-update-20250324/

https://arxiv.org/abs/2311.06374

https://arxiv.org/abs/2305.07512

https://link.springer.com/article/10.1007/s10107-019-01449-1

科普薦書

【更多讀者好評數學書單推薦、數學科普作家自薦、出版社書單推薦通道已陸續打開，敬請期待】

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！