研究人员发现最优化问题的终极优化方法

目前主流的单纯形法——一种广泛应用于平衡复杂物流约束的技术——已然达到极致。

图源：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年，斯皮尔曼和滕尚华证明了哪怕是最微小的随机性也能帮助避免这种结果。回到前面的例子——尽管这可能大大简化了斯皮尔曼和滕尚华的论证——假设你遇到的每个角落都有六个选择。如果你总是被告知最坏的方向，你就会陷入困境。然而，如果你依靠掷骰子，你就有六分之五的机会避免最糟糕的选择，从而可能避免灾难。考虑到现实世界中的测量从来都不精确，在过程中注入随机性和不确定性元素是合理的。斯皮尔曼和滕尚华以完全不同的方式引入了随机性，但他们证明了运行时间永远不会比约束数量的某个固定幂（例如 n⊃2; ） 更差，这就是所谓的多项式时间的一个例子。这比指数时间要好得多，指数时间的形式是 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