研究人員發現最優化問題的終極優化方法

★加星zzllrr小樂公眾號數學科普不迷路！

目前主流的單純形法——一種廣泛應用于平衡復雜物流約束的技術——已然達到極致。

圖源：Nash Weerasekera / Quanta Magazine

作者：Steve Nadis（量子雜志特約撰稿人）2025-10-13

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

1939年，加州大學伯克利分校一年級研究生喬治·丹齊格（George Dantzig）上統計學課遲到了，他從黑板上抄了兩道題，以為是家庭作業。他后來回憶說，這道作業“比平時難做”，于是向教授道歉，因為他多花了幾天時間才完成。幾周后，教授告訴他，他解決了統計學中兩個著名的開放性問題。丹齊格的研究成果為他的博士論文奠定了基礎，幾十年后，更是為電影 《心靈捕手》

Good Will Hunting

丹齊格于1946年二戰剛結束后獲得博士學位，并很快成為新成立的美國空軍的數學顧問。與所有現代戰爭一樣，二戰的勝負取決于有限資源的審慎分配。但與以往的戰爭不同，這場戰爭真正具有全球性，其勝利很大程度上得益于強大的工業實力。美國可以比敵人生產更多的坦克、航空母艦和轟炸機。鑒于此，軍方對最優化問題產生了濃厚的興趣——即如何在可能涉及數百甚至數千個變量的情況下，戰略性地分配有限的資源。

空軍委托丹齊格尋找解決此類最優化問題的新方法。為此，他發明了單純形法（simplex method），這種算法借鑒了近十年前他在解決黑板問題時開發的一些數學技巧。

近80年后，單純形法仍然是在復雜約束條件下進行物流或供應鏈決策時最廣泛使用的工具之一。它高效可行。“它一直運行得很快，而且從未有人見過它不快，”法國國家科學研究中心（CNRS）的索菲·惠伯茨（Sophie Huiberts）說道。

與此同時，丹齊格方法的一個奇特特性長期以來一直蒙上陰影。1972年，數學家證明，完成一項任務所需的時間可能會隨著約束數量的增加而呈指數增長。因此，無論該方法在實踐中有多快，理論分析總是會給出最壞的情況，這意味著它可能需要更長的時間。對于單純形法，“我們研究算法的傳統工具不起作用，”惠伯茨說。

然而，在一篇將于12月在計算機科學基礎大會上發表的新論文中 https://arxiv.org/abs/2504.04197 ，惠伯茨和慕尼黑工業大學的博士生Eleon Bach（埃利昂·巴赫）似乎已經克服了這個問題。他們提高了算法的速度，并提供了理論依據，解釋了為什么長期以來人們擔心的指數級運行時間在實踐中不會出現。這項工作建立在丹尼爾·斯皮爾曼（Daniel Spielman）和滕尚華于2001年取得的一項里程碑式成果 https://arxiv.org/abs/cs/0111050 的基礎上，滕尚華表示，這項工作“非常出色，且精彩”。

Eleon Bach（埃利昂·巴赫）是這項新成果的共同作者之一。

圖源：Eleon Bach

“這是一項非常令人印象深刻的技術工作，它巧妙地結合了之前研究中開發的許多想法，[同時添加]了一些真正好的新技術理念，”波恩大學數學家拉斯洛·維格 (László Végh) 說，他沒有參與這項工作。

最優化幾何

單純形法旨在解決如下一類問題：假設一家家具公司生產衣櫥、床和椅子。碰巧的是，每個衣櫥的利潤是每把椅子的三倍，而每張床的利潤是每把椅子的兩倍。如果我們用 a 、 b 和 c 分別表示每種家具產量，將其寫成一個表達式，那么總利潤與 3a + 2b + c 成正比。

為了實現利潤最大化，公司應該生產每種產品多少？答案取決于公司面臨的約束條件。假設公司每月最多生產 50 件產品，那么 a + b + c 小于或等于 50。衣櫥的生產難度更大——最多只能生產 20 個——所以 a 小于或等于 20。椅子需要特殊的木材，而且供應有限，所以 c 必須小于 24。

單純形法將類似情況（盡管通常涉及更多變量）轉化為幾何問題。想象一下，在三維空間中繪制 a 、 b 和 c 的約束圖形。如果 a 小于或等于 20，我們可以想象在三維圖形上有一個垂直于 a 軸的平面，并在 a = 20 處與其相交。我們規定解必須位于該平面上方或下方的某個位置。同樣，我們可以創建與其他約束相關的邊界。這些邊界結合起來，可以將空間劃分成一個復雜的三維形狀，稱為多面體（polyhedron）。

索菲·惠伯茨（Sophie Huiberts）持有一個最優化問題的幾何模型。

圖源：Sophie Huiberts

單純形算法從頭到尾的執行過程，用幾何學的表達方式來說，就是尋找一條路徑——比如從最底下的頂點到最上面的頂點——它需要的步驟最少，或者說，追蹤的邊數最少。總步驟數又與算法的運行時間（或“復雜度”）相關，目標是用最少的步驟解決問題。在這張圖中，找出從底部到頂部的最短路徑，就等于找出這種算法可以采用的最高效形式。

找到一條快速直接的路徑或許很容易，但往往因為以下兩點并不容易：首先，原始形狀可能比我們的例子復雜得多，包含更多的面、頂點和邊。其次，沒有地圖指引你。你無法看到你試圖導航的整個對象。相反，你從一個頂點開始，選擇先走哪條邊。在下一個頂點，你又重復同樣的步驟，以此類推，你并不確定你選擇的這條邊會把你帶到哪里。

如果你運氣極差，可能會在每個頂點都走錯，然后被困在迷宮里。“你可能會走從 A 到 B最長的路，”巴赫說，“因為在每個拐角處，都會有人告訴你可能走錯方向。”這種情況可能會導致最糟糕的結果，需要花費指數級的時間才能完成。

2001年，斯皮爾曼和滕尚華證明了哪怕是最微小的隨機性也能幫助避免這種結果。回到前面的例子——盡管這可能大大簡化了斯皮爾曼和滕尚華的論證——假設你遇到的每個角落都有六個選擇。如果你總是被告知最壞的方向，你就會陷入困境。然而，如果你依靠擲骰子，你就有六分之五的機會避免最糟糕的選擇，從而可能避免災難。考慮到現實世界中的測量從來都不精確，在過程中注入隨機性和不確定性元素是合理的。斯皮爾曼和滕尚華以完全不同的方式引入了隨機性，但他們證明了運行時間永遠不會比約束數量的某個固定冪（例如 n2 ） 更差，這就是所謂的多項式時間的一個例子。這比指數時間要好得多，指數時間的形式是 2? 。

滕尚華（上）和丹尼爾·斯皮爾曼（下）在2001年取得的里程碑式成果中使用了隨機性。

圖源：Emilio Flores / Quanta Magazine ；Brandon Schulman

然而，這并沒有完全解決問題。Huiberts指出，他們的多項式時間值仍然相當高——它們包含一個30次方的項，這對于指數來說是一個相當大的數字。因此，在過去的二十年里，研究人員一直在逐步降低這個值。

在新論文中，Bach 和 Huiberts 在算法中引入了更多隨機性，證明了運行時間肯定比之前建立的運行時間要短得多。他們還證明，基于斯皮爾曼和滕尚華建立的方法的算法不可能比他們得到的值更快。Huiberts 表示，這說明“我們完全理解了單純形法的這個模型”。

波恩大學計算機科學家 Heiko R?glin 表示：“這標志著我們對單純形算法的理解取得了重大進展，首次為該方法的實際效率提供了真正令人信服的解釋。”

盡管如此，Huiberts 并不認為這是研究的終點。斯皮爾曼和滕尚華于2001年開創的方法展示了如何將運行時間從指數級縮短到多項式級。下一步合乎邏輯的做法是發明一種能夠隨著約束數量線性擴展的方法。“這是所有這些研究的北極星，”她說。但這需要一個全新的策略。“我們短期內還無法實現這一目標。”

雖然 Bach 和 Huiberts 的努力引起了同行們的理論興趣，但這項工作尚未產生任何直接的實際應用。然而，它或許可以緩解人們對依賴目前基于單純形法的軟件的一些擔憂。“雖然實際實驗表明這些問題總是可以在多項式時間內解決，”設計線性規劃軟件的愛丁堡大學數學講師 Julian Hall 說道，但 Bach 和 Huiberts 的研究為這一直覺提供了更有力的數學支持。“因此，現在更容易說服那些害怕指數級復雜性的人了。”

參考資料

https://www.quantamagazine.org/researchers-discover-the-optimal-way-to-optimize-20251013/

https://arxiv.org/abs/2504.04197

https://arxiv.org/abs/cs/0111050

小樂數學科普近期文章

出版社和作家自薦通道

小樂數學科普薦書

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

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

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

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

加星★

數學科普不迷路！