從你網(wǎng)購的包裹如何以最快速度送達(dá)，到航空公司如何規(guī)劃數(shù)千架飛機(jī)的航線以節(jié)省燃料，背后都有一個(gè)近 80 歲「高齡」的數(shù)學(xué)方法在默默工作。它被譽(yù)為優(yōu)化領(lǐng)域的基石，高效又令人信賴。然而，一個(gè)奇怪的事實(shí)是：幾十年來，沒有人能從理論上完美解釋它為何如此高效。現(xiàn)在，這個(gè)謎題的最后一塊拼圖，終于被找到了。

1939 年，當(dāng)時(shí)還是加州大學(xué)伯克利分校一年級研究生的喬治·丹齊格（George Dantzig）在一次統(tǒng)計(jì)學(xué)課上遲到了。他從黑板上抄下了兩個(gè)問題，以為是家庭作業(yè)。他后來回憶說，他發(fā)現(xiàn)這次的作業(yè)「比平時(shí)難得多」，并為自己多花了好幾天才完成而向教授道歉。

幾周后，他的教授告訴他，他成功解決了統(tǒng)計(jì)學(xué)領(lǐng)域兩個(gè)尚待解決的著名問題。

丹齊格的這項(xiàng)成果為他的博士論文奠定了基礎(chǔ)，并在幾十年后成為了電影《心靈捕手》的靈感來源。

喬治·丹齊格（George Dantzig，1914—2005），美國著名數(shù)學(xué)家，1947 年提出了單純形法，被稱為線性規(guī)劃之父。

丹齊格在 1946 年，也就是二戰(zhàn)剛結(jié)束后不久，獲得了博士學(xué)位，并很快成為了新成立的美國空軍的數(shù)學(xué)顧問。

與所有現(xiàn)代戰(zhàn)爭一樣，第二次世界大戰(zhàn)的勝負(fù)取決于對有限資源的審慎分配。但與以往的戰(zhàn)爭不同，這場沖突的規(guī)模是全球性的，其勝利在很大程度上是依靠純粹的工業(yè)實(shí)力取得的。當(dāng)時(shí)，美國能夠生產(chǎn)比其敵人更多的坦克、航空母艦和轟炸機(jī)。

了解到這一點(diǎn)后，軍方對優(yōu)化問題產(chǎn)生了濃厚興趣，即：在可能涉及成百上千個(gè)變量的情況下，如何戰(zhàn)略性地分配有限的資源？

美國空軍交給丹齊格的任務(wù)是，找出解決這類優(yōu)化問題的新方法。作為回應(yīng)，他發(fā)明了單純形法 (simplex method) ，這個(gè)算法借鑒了他在近十年前解決黑板問題時(shí)所發(fā)展出的一些數(shù)學(xué)技巧。

近 80 年后，當(dāng)需要在復(fù)雜的約束條件下做出后勤或供應(yīng)鏈決策時(shí)，單純形法仍然是使用最廣泛的工具之一。它高效且行之有效。法國國家科學(xué)研究中心 (CNRS) 的 Sophie Huiberts 說道：「它一直運(yùn)行得很快，沒人見過它變慢過?！?/span>

與此同時(shí)，一個(gè)奇特的性質(zhì)長期以來為丹齊格的方法蒙上了一層陰影。

1972 年，數(shù)學(xué)家們證明：該算法完成任務(wù)所需的時(shí)間可能會隨著約束條件的數(shù)量呈指數(shù)級增長。

因此，無論該方法在實(shí)踐中運(yùn)行得多快，理論分析始終給出最壞情況下的場景，暗示它可能需要指數(shù)級更長的時(shí)間。對于單純形法，「我們研究算法的傳統(tǒng)工具并不奏效，」 Huiberts 說。

但在即將于 12 月在計(jì)算機(jī)科學(xué)基礎(chǔ)（Foundations of Computer Science）會議上發(fā)表的一篇新論文中，Huiberts 和慕尼黑工業(yè)大學(xué)的博士生 Eleon Bach 似乎已經(jīng)克服了這個(gè)問題。

• 論文標(biāo)題：Optimal Smoothed Analysis of the Simplex Method
• 論文地址：https://arxiv.org/abs/2504.04197

他們不僅使該算法變得更快，還從理論上解釋了這一現(xiàn)象：長期以來令人擔(dān)憂的指數(shù)級運(yùn)行時(shí)間在實(shí)踐中并未出現(xiàn)。

這項(xiàng)成果建立在 Daniel Spielman 和滕尚華 (Shang-Hua Teng) 2001 年里程碑式成果《Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time》（arXiv:cs/0111050）之上。滕尚華表示，這項(xiàng)成果「卓越且優(yōu)美」。

「這是一項(xiàng)非常了不起的技術(shù)工作，它巧妙地結(jié)合了以往研究中發(fā)展的許多思想，同時(shí)增加了一些非常好的新穎技術(shù)構(gòu)想，」 波恩大學(xué)的數(shù)學(xué)家 László Végh 說道，他沒有參與這項(xiàng)研究。

從幾何角度來看，單純形算法的整個(gè)執(zhí)行過程，就是尋找一條路徑（比方說，從底部頂點(diǎn)到最高點(diǎn)），并且這條路徑包含的步驟最少，或者說，經(jīng)過的邊最少。總步數(shù)則與算法的運(yùn)行時(shí)間（或「復(fù)雜度」）相關(guān)，目標(biāo)是在最少的步數(shù)內(nèi)解決問題。在這張圖中找出從底部到頂部的最短路線，就相當(dāng)于找出了這類算法所能采取的最有效形式。

如果不是因?yàn)橐韵聝蓚€(gè)問題，找到一條快速直接的路徑可能會很容易：

• 第一，原始形狀可能比我們的例子復(fù)雜得多，有更多的面、頂點(diǎn)和邊。
• 第二，沒有地圖可以引導(dǎo)你。你無法看到你試圖導(dǎo)航的整個(gè)物體。相反，你從一個(gè)頂點(diǎn)開始，選擇要先沿著哪條邊走。在下一個(gè)頂點(diǎn)你做同樣的事情，依此類推，并不確定你選擇的邊會將你帶到哪里。

如果你運(yùn)氣特別差，你可能會在每個(gè)頂點(diǎn)都走錯(cuò)方向，最終陷入迷宮。「你可能會走上從 A 點(diǎn)到 B 點(diǎn)的最長路徑，」 Bach 說，「因?yàn)樵诿總€(gè)拐角處，都有人告訴你該走向錯(cuò)誤的方向?！?正是這種情況可能導(dǎo)致需要指數(shù)級時(shí)間才能完成的最壞情況。

2001 年，Spielman 和滕尚華證明：引入一點(diǎn)點(diǎn)隨機(jī)性可以幫助避免這樣的結(jié)果。

滕尚華（左）和 Daniel Spielman 在他們 2001 年的里程碑式成果中運(yùn)用了隨機(jī)性。

回到前面的例子（注意這里極大地簡化了 Spielman 和滕尚華的論證），讓我們假設(shè)你到達(dá)的每個(gè)拐角處都有六個(gè)選擇。如果總是有人告訴你走最差的方向，你就會陷入困境。然而，如果你依靠擲骰子來決定，你將有六分之五的機(jī)會避開最差的選擇，從而可能避免災(zāi)難。在過程中注入隨機(jī)性和不確定性的元素是合理的，因?yàn)樵诂F(xiàn)實(shí)世界中，測量永遠(yuǎn)不是精確的。

當(dāng)然，Spielman 和滕尚華引入隨機(jī)性的方式完全不同，但他們證明：運(yùn)行時(shí)間絕不會比約束數(shù)量的某個(gè)固定次冪更差（例如 n2 ）—— 這就是所謂的多項(xiàng)式時(shí)間 (polynomial time)。這比指數(shù)時(shí)間（例如 2? 的形式）要好得多。

最優(yōu)幾何

單純形法旨在解決這樣一類問題：假設(shè)一家家具公司生產(chǎn)衣柜、床和椅子。巧合的是，每個(gè)衣柜的利潤是椅子的三倍，而每張床的利潤是椅子的兩倍。如果我們想把這寫成一個(gè)表達(dá)式，用 a、b 和 c 分別代表生產(chǎn)的家具數(shù)量，那么總利潤將與 3a+2b+c 成正比。

為了實(shí)現(xiàn)利潤最大化，公司應(yīng)該各種物品各生產(chǎn)多少件呢？

答案取決于它面臨的約束條件。比方說，該公司每月最多能生產(chǎn) 50 件產(chǎn)品，因此 a+b+c≤50。衣柜的制造難度更大 —— 假設(shè)產(chǎn)量不能超過 20 個(gè)，所以 a≤20；椅子需要特殊的木材，而且供應(yīng)有限，所以 c 必須小于 24。

單純形法可將這類情況（通常涉及更多變量）轉(zhuǎn)化為一個(gè)幾何問題。

想象一下在一個(gè)三維圖表中繪制我們對 a、b 和 c 的約束條件。如果 a≤20，我們可以想象在三維圖上有一個(gè)垂直于 a 軸的平面，在 a=20 的位置將其切開。我們會規(guī)定，我們的解必須位于該平面上或其下方的某個(gè)位置。同樣，我們可以為其他約束條件創(chuàng)建邊界。這些邊界組合起來可以將空間分割成一個(gè)復(fù)雜的三維形狀，稱為多面體 (polyhedron)。

Sophie Huiberts 手持一個(gè)優(yōu)化問題的幾何模型。

然而，這并沒有完全解決問題。

Huiberts 指出，他們的多項(xiàng)式時(shí)間值仍然相當(dāng)高，其中包含一個(gè) 30 次冪的項(xiàng)，對于指數(shù)來說，這是一個(gè)相當(dāng)大的數(shù)字。

因此，在過去二十年里，研究人員一直在逐步降低這個(gè)數(shù)值。

在 Bach 和 Huiberts 的新論文中，他們在算法中應(yīng)用了更多的隨機(jī)性，以證明運(yùn)行時(shí)間可以保證遠(yuǎn)低于先前確立的水平。他們還證明：基于 Spielman 和滕尚華所建立方法的算法，其運(yùn)行速度無法超越他們獲得的值。Huiberts 說，這告訴我們，「我們完全理解了單純形法的這個(gè)模型?！?/span>

研究主要結(jié)果

盡管如此，Huiberts 并不認(rèn)為這是終點(diǎn)。

從 2001 年 Spielman 和滕尚華開始的方法展示了如何將運(yùn)行時(shí)間從指數(shù)級降低到多項(xiàng)式級。下一個(gè)合理的目標(biāo)是發(fā)明一種能夠與約束數(shù)量成線性關(guān)系擴(kuò)展的方法?！高@是所有這項(xiàng)研究的北極星 (North Star)，」她說。但這需要一種全新的策略?！肝覀兌唐趦?nèi)還不大可能實(shí)現(xiàn)它?！?/span>

雖然 Bach 和 Huiberts 的努力對他們領(lǐng)域的同行具有理論意義，但這項(xiàng)工作尚未產(chǎn)生任何直接的實(shí)際應(yīng)用。

Eleon Bach 是這項(xiàng)新成果的作者之一。

盡管如此，它可能會平息一些人對于依賴當(dāng)今基于單純形法的軟件可能產(chǎn)生的擔(dān)憂。愛丁堡大學(xué)數(shù)學(xué)講師、線性規(guī)劃軟件設(shè)計(jì)師 Julian Hall 表示：「雖然實(shí)踐實(shí)驗(yàn)表明這些問題總是在多項(xiàng)式時(shí)間內(nèi)解決」，但 Bach 和 Huiberts 的研究為這一直覺提供了更強(qiáng)的數(shù)學(xué)支持?！敢虼?，現(xiàn)在更容易說服那些擔(dān)心指數(shù)級復(fù)雜度的人了?！?/span>