精选
研究者发现了优化的最佳方法
用于平衡复杂物流约束的一种广泛使用的技术是单纯形方法。实现这一方法的领先方案不再有改进的空间了。
Steve Nadis 著
左 芬 译
【译注：原文2025年10月13日刊载于QuantaMagazine，链接见文末。】
1939年，加州大学伯克利分校一年级研究生George Dantzig上统计课去晚了，就从黑板上抄下了两个题目，以为它们是布置的家庭作业。他发现作业“比往常难多了”，他后来叙述道，所以多花了几天才完成并为此向老师道歉。几周后，他的老师告诉他，他解决了统计学中两个著名的未解难题。Dantzig的这些结果成为了他的博士论文的基础，并在数十年后启发了电影《心灵捕手》（“Good Will Hunting”）。
Dantzig 1946年获得博士学位，就在第二次世界大战刚结束后，接着很快成为了新成立的美国空军的数学顾问。正如所有现代战争一样，第二次世界大战的结果取决于有限资源的合理分配。不过与之前的战争不同，这次大战在规模上真正是全球的，而它得以获胜在很大程度上是依靠纯粹的工业力量。比起它的敌人来，美国不过是能生产更多的坦克、航空母舰和轰炸机而已。知晓这一点，军方就尤其关注优化问题——也就是，在涉及数百甚至数千个变量的情形下如何战略性地分配有限的资源。
空军委派Dantzig去构思新的方法来解决类似这些的优化问题。作为回应，他发明了单纯形（simplex）方法，对近十年前他在解决黑板问题时发展的一些数学技术加以利用而得出的一个算法。
近80年过去了，当需要在复杂的约束下做出后勤或供应链决策时，单纯形方法仍然位于最广泛使用的工具之列。它高效且起作用。“它总是运行得很快，从来没人见过它变慢过，”法国国家科学研究中心（简称CNRS）的Sophie Huiberts称。
与此同时，有一条古怪的性质让Dantzig的方法长期以来都蒙着阴影。1972年，数学家证明它完成一项任务花费的时间有可能会随着约束的数目而指数式地增长。因此，无论这一方法在实践中有多快，理论分析始终会找出最坏方案，使得它花费指数长的时间。对于单纯形方法，“我们研究算法的传统工具不再奏效了，”Huiberts说道。
Eleon Bach是新结果的共同作者之一。
可是在12月份举办的计算机科学基础会议上将展示的一篇新文章中，Huiberts和慕尼黑工业大学的一个博士生Eleon Bach似乎解决了这一争议。她们对算法予以加速，并提供了理论依据来说明为何一直以来担心的指数运行时间不会在实践中出现。这一工作是建立在Daniel Spielman与滕尚华2001年的里程碑式成果的基础之上的，而滕对其的评价是，“出色【且】优美。”
“这是非常厉害的技术性工作，它熟练地将此前研究思路中的许多点子结合起来了，【并加入了】一些极其巧妙的新技术想法，”波恩大学数学家，未参与这一工作的László Végh 称。
最优几何
单纯形方法是设计出来处理如下这类问题的：比方说一个家具公司会生产衣橱、床和椅子。刚好，每个衣橱的盈利是椅子的三倍，而每张床的盈利是椅子的两倍。如果我们想把这个写成一个表达式，可以用
来分别代表每种家具的产量，我们说总盈利正比于
。
为了最大化盈利，该公司应该每样家具生产多少呢？答案取决于它面临的约束。比方说公司每月最多可以产出50件家具，那么
必须小于或等于50 。衣橱更难制造——只能产出不超过20个——所以
小于或等于20。椅子需要特殊的木材，是限制供应的，所以
必须小于24。
单纯形方法把这种情形——不过常常涉及多得多的变量——转变成一个几何问题。设想在三维中把我们对的约束画出来。假定要小于或等于20，我们可以想象在一个三维图中有一个垂直于轴的平面，并在
处穿过它。我们可以要求解必须处在平面上或者之下。类似地，我们可以生成跟其它约束相关联的边界。组合起来，这些边界会在空间中分离出一个复杂的三维形状，一个多面体。
Sophie Huiberts拿着优化问题的一个几何模型。
如果从几何上表示的话，那么单纯形算法从头到尾的执行就是在寻找一条路径——从比方说最底下的点到最顶上的点——并让它步数最少，或者等价地，经过最少的边。总的步数进而关联到算法的运行时间（或者“复杂性”），而目标则是在最少的步数内解决问题。在这一图像中识别从底到顶的最短路径等同于找出这类算法所能取得的最有效形式。
找出快速而直接的路径可能很容易，但会有两个阻碍：首先，原始的形状很可能远比我们的例子复杂，会有多得多的面、顶点和边。其次，没有地图可以引导你。当你努力行进时你是看不见整个物体的。取而代之的是，你从一个顶点出发，对于先走哪一条边做出选择。在下一个顶点你也同样处理，这样一直下去，但并不确切知晓你选择的边会把你带到什么地方去。
如果你超乎寻常地不幸，你可能在每个顶点都选择了错误的方向，从而陷进了一个迷宫。“你会走上从A到B的最长的路，”Bach说道，“因为在每个转角都有人让你走错误的方向。”这种情况就会导致最坏的方案，而这需要指数量的时间才能完成。
2001年，Spielman和滕证明，最微小份额的随机性就可以阻止这样一种结果。回到此前的例子中——冒着极大地简化Spielman与滕的证明这样一种风险——我们假定在你到达的每个转角都有六种选择。如果你总是被告知最差的方向，那你就会陷入困境。不过，如果你转而依赖一个骰子掷出的点数，你会有六分之五的机会避开最坏的选择，于是灾难就可以避免。在过程中注入少许随机性和不确定性是合理的，因为在现实世界中，测量从来就不是精确的。Spielman和滕在引入随机性时采用了一种截然不同的方式，不过他们证明，运行时间永远不会差于约束数目的一个确定的幂次——例如，
——而这正是所谓多项式时间的例子。这要远远优于指数时间，也就是比方说
这种形式。
滕尚华（左）与Daniel Spielman在他们2001年的里程碑式成果中使用了随机性。
然而，这并没有完全解决这一争议。他们的多项式的次数还是相当高，Huiberts注意到——他们引入的一个项的幂次高达30，而对于幂次来说30是非常大的一个数了。因此，在过去二十年里，研究者们在降低这一数值上逐步往前推进。
在他们的新文章中，Bach与Huiberts在她们的算法中利用更多的随机性来证明，运行时间可以确保显著低于此前取得的纪录。他们还证明，以Spielman与滕发现的方法为基础的算法不可能比她们获得的结果更快了。它说明，Huiberts称，“我们已经彻底理解了单纯形方法的【这一】模型了。”
“这标志着我们在理解【单纯形】算法上的巨大进步，”波恩大学计算机科学家Heiko Röglin说道，“它首次为这一方法的实际有效性提供了真正有说服力的解释。”
不过，Huiberts并不认为这就给这一方向划上句号了。Spielman与滕2001年始创的方法展示了如何将运行时间从指数降到多项式。下一个合理的步骤是发明一种方法，让它的时间随着约束的数目线性增长。“那是所有这类研究的北极星，”她说。不过这将需要一种全新的策略。“近期的话我们还不太可能实现这一点。”
尽管Bach 与 Huiberts的成果在她们领域的同行们看来是有理论意义的，这一工作还没有产生任何即时的实际应用。不过，它或许可以用来平息人们对当前存在的基于单纯形方法的软件的担忧。“尽管实际测试表明这些问题总是可以在多项式时间解决，”爱丁堡大学的数学讲师，线性规划软件设计者Julian Hall说道，Bach与Huiberts为这一直观经验提供了更强的数学支持。“因此现在要说服那些担心指数复杂性的人就容易多了。”
原文链接：
https://www.quantamagazine.org/researchers-discover-the-optimal-way-to-optimize-20251013/
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。
链接地址：https://wap.sciencenet.cn/blog-863936-1508392.html?mobile=1
收藏
