一種簡單而廣泛使用的數(shù)學(xué)技術(shù)最終可以應(yīng)用于無限復(fù)雜的問題。

圖源：Michele Sclafani|Quanta Magazine

點擊zzllrr小樂公眾號主頁右上角設(shè)為星標★數(shù)學(xué)科普不迷路！

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

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2025-3-25

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

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

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

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

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

“牛頓法在最優(yōu)化中有1000種不同的應(yīng)用，”Ahmadi說道。“我們的算法有可能取代它?！?/p>

1680年代，艾薩克·牛頓發(fā)明了一種尋找最優(yōu)解的算法。三個世紀后，數(shù)學(xué)家們?nèi)栽谑褂煤屯晟扑姆椒ā?/p>

圖源：Godfrey Kneller/公共領(lǐng)域

百年歷史的技術(shù)

數(shù)學(xué)函數(shù)將輸入轉(zhuǎn)換為輸出。通常，一個函數(shù)最重要的特征是其最?。ㄝ斎耄┲怠a(chǎn)生最小可能輸出的輸入組合。

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

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

Amir Ali Ahmadi（阿米爾·阿里·艾哈邁迪）發(fā)現(xiàn)，無論何時何地，最優(yōu)化問題都隨處可見。

圖源：Mathematisches Forschungsinstitut Oberwolfach奧伯沃爾法赫數(shù)學(xué)研究所檔案

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

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

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

尋找最優(yōu)解

在1680年代，艾薩克·牛頓發(fā)明了一種求函數(shù)最小值的方法它的最優(yōu)解。幾個世紀后，數(shù)學(xué)家們?nèi)匀辉谑褂盟乃惴ā?/p>

1. 猜一猜

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

2. 繪制曲線模型

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

3. 找到下一個點

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

4. 重復(fù)

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

5. 繼續(xù)前進

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

圖源：Mark Belan/Quanta Magazine

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

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

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

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

但他的策略的關(guān)鍵是將一個復(fù)雜的函數(shù)轉(zhuǎn)換成一個更簡單的函數(shù)。這些更復(fù)雜的泰勒方程超出了牛頓的數(shù)學(xué)處理能力。

?Jeffrey Zhang和他的合著者以正確的方式調(diào)整函數(shù)，從而拓寬了強大優(yōu)化技術(shù)的范圍。?

圖源：Jeffrey Zhang

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

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

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

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

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

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

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

尋找回旋余地

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

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

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

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

圖源：Camille Carpenter Henriquez

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

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

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

他們實際上是在泰勒展開式中添加了一個修正因子，將其變成了具有兩種所需性質(zhì)的方程?！拔覀兛梢陨晕⒏淖兲├照归_式，使其更容易最小化?？紤]泰勒展開式，但稍作修改，”艾Ahmadi說。

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

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

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

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

賓夕法尼亞大學(xué)的Jason Altschuler表示：“最優(yōu)化領(lǐng)域的許多想法需要花費數(shù)年時間才能完全付諸實踐。但這似乎是一個全新的視角?！?/p>

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

“從理論上講，我們目前的算法確實更快，”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

科普薦書

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

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

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

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

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數(shù)學(xué)科普不迷路！