内容来源：https://www.quantamagazine.org/researchers-discover-the-optimal-way-to-optimize-20251013/

内容总结：

【本报讯】在运筹学领域沿用近八十年的经典算法“单纯形法”近日迎来理论突破。两位欧洲数学家通过引入随机性技术，首次为这一算法的实际高效性提供了令人信服的理论解释，并显著提升了其运算速度上限。

单纯形法由美国数学家乔治·丹齐格于1947年创立。这位传奇学者在伯克利求学时期，曾误将黑板上的两道统计学未解难题认作课后作业并成功破解，这段经历后来成为电影《心灵捕手》的创作灵感。二战后，丹齐格受聘于美国空军，为解决大规模资源调配问题，基于早期研究创立了该算法。如今，单纯形法已成为物流规划、供应链管理等复杂决策场景的核心工具。

尽管该算法在实践中始终表现优异，但理论界自1972年起便发现其存在缺陷：在极端情况下，运算时间会随问题复杂度呈指数级增长。法国国家科研中心的索菲·惠伯特指出：“传统分析工具对单纯形法失效，这成为悬在学界头顶的达摩克利斯之剑。”

最新发表于计算机科学基础年会的研究中，惠伯特与慕尼黑工业大学博士生埃莱昂·巴赫成功突破了这一理论困境。他们通过强化算法中的随机性机制，不仅实现了加速效果，更从数学层面证实了长期担忧的指数级耗时问题在实践中几乎不会出现。该研究构建于2001年斯皮尔曼-滕尚华开创的“平滑分析”理论之上，被学界评价为“精湛而优美的工作”。

德国波恩大学计算机科学家海科·罗格林认为，这项研究标志着“对人类最常用优化算法的理解取得重大进展”。爱丁堡大学数学讲师朱利安·霍尔指出，该成果增强了人们对现有优化软件的信心，“让担心指数复杂度问题的人们更容易被说服”。

尽管理论价值显著，研究团队坦言该成果尚不能直接应用于实际场景。惠伯特表示，下一步目标是实现运算时间与问题规模的线性增长，但这需要全新的技术路径，“我们短期内还无法触及这颗北极星”。

（根据《量子杂志》数学研究报道编译）

中文翻译：

研究人员发现最优化的方法

1939年，加州大学伯克利分校的一堂统计学课程上，迟到的研究生新生乔治·丹齐格将黑板上的两道题目误认为课后作业。他后来回忆道，这份作业"比往常更难完成"，还因多花了几天时间向教授致歉。几周后，教授告诉他这两道题竟是统计学领域两道著名的未解难题。丹齐格的这项成果不仅构成了他的博士论文基础，数十年后更成为电影《心灵捕手》的创作灵感。

1946年获得博士学位后，丹齐格旋即成为新成立的美国空军数学顾问。与所有现代战争相同，二战的胜负取决于有限资源的合理配置；但不同于以往的是，这场冲突真正具有全球规模，且很大程度上是靠绝对工业实力取胜的。美国仅凭能够生产比敌国更多的坦克、航空母舰和轰炸机就占据优势。有鉴于此，军方对最优化问题——即如何在涉及数百甚至数千个变量的情况下战略性地分配有限资源——表现出浓厚兴趣。

空军委托丹齐格寻找解决这类最优化问题的新方法。为此他发明了单纯形法，这个算法借鉴了近十年前他解决黑板难题时开发的数学技巧。

近八十年后的今天，当需要在复杂约束条件下做出物流或供应链决策时，单纯形法仍是应用最广泛的工具之一。法国国家科学研究中心（CNRS）的索菲·休伯特斯指出："它始终运行迅速，从未有人见过它运行缓慢的情况。"

然而有个奇特性质长期笼罩着丹齐格的方法。1972年数学家证明，完成任务所需时间会随着约束条件数量呈指数级增长。休伯特斯解释道："对于单纯形法而言，我们研究算法的传统工具并不适用。"

但在即将于12月计算机科学基础会议上发表的新论文中，休伯特斯与慕尼黑工业大学博士生埃莱奥诺·巴赫似乎攻克了这个难题。他们不仅提升了算法速度，更从理论上解释了为何长期担忧的指数级运行时间未在实践中出现。这项建立在2001年丹茨·斯皮尔曼与滕尚华里程碑式成果基础上的研究，被滕尚华誉为"卓越而精美"。

未参与该研究的波恩大学数学家拉兹洛·韦格表示："这项技术工作令人印象深刻，它巧妙融合了先前多条研究路线的思想，同时加入了真正巧妙的新技术理念。"

最优几何

单纯形法旨在解决这类问题：假设某家具公司生产衣柜、床和椅子，每件衣柜的利润恰好是椅子的三倍，每张床的利润是椅子的两倍。用a、b、c分别表示三类家具的产量，总利润可表示为3a+2b+c。

如何确定各类产品的最优产量？答案取决于约束条件：月产量不超过50件（a+b+c≤50），衣柜工艺复杂最多生产20件（a≤20），椅子所需特殊木材供应有限（c＜24）。

单纯形法将这类涉及多个变量的情境转化为几何问题。想象在三维坐标系中绘制约束条件：a≤20对应垂直于a轴且穿过a=20的平面，解必须位于该平面下方。所有约束边界共同将空间分割成复杂的三维多面体。

从几何角度看，单纯形算法的执行过程类似于在多面体表面寻找从最低点到最高点的最短路径。步数总量关乎算法运行时间（即"复杂度"），目标是以最少步骤解决问题。在此图像中找出从底到顶的最短路线，就相当于确定算法最高效的形式。

寻找快速路径本非难事，但存在两大挑战：首先实际形状远比示例复杂，具有更多面、顶点和棱边；其次没有导航地图，只能从某个顶点出发，在未知前路的情况下逐点选择行进方向。

巴赫解释道："若运气极差，可能在每个转角都选错方向，陷入迷宫般的最长路径。"这正是导致最坏情况需要指数级时间的原因。

2001年斯皮尔曼与滕尚华证明，微量随机性即可避免这种困境。以简化模型说明：假设每个转角有六个方向，若总是被指引至最差方向就会陷入困境；但若依靠骰子随机选择，就有六分之五几率避开最差选择。考虑到现实世界测量从不可能绝对精确，引入随机元素具有合理性。他们通过全新方式引入随机性，证明运行时间最坏情况也不会超过约束数量的固定幂次（如n²），即多项式时间，远优于指数时间（如2ⁿ）。

但问题尚未完全解决。休伯特斯指出，他们的多项式时间值仍然偏高——包含30次幂项，这对指数而言相当大。过去二十年间，研究人员一直在逐步降低这个数值。

巴赫与休伯特斯在新论文中通过增强算法随机性，确保证运行时间显著低于既往结论。他们还证明基于斯皮尔曼-滕尚华方法的算法不可能超越他们获得的数值。休伯特斯表示："这表明我们完全理解了单纯形法的这个模型。"

波恩大学计算机科学家海科·罗格林评价道："这标志着我们对单纯形算法的理解取得重大进展，首次为该方法实践效率提供了真正令人信服的解释。"

但休伯特斯认为这并非终点。自2001年斯皮尔曼与滕尚华将运行时间从指数级降至多项式后，下一个目标是与约束数量成线性比例。她坦言："这是所有研究的北极星，但需要全新策略，我们短期内难以实现。"

尽管巴赫与休伯特斯的研究主要引起领域内同行的理论兴趣，尚未产生直接实际应用，但有助于消除人们对现有单纯形法软件的疑虑。爱丁堡大学设计线性编程软件的数学讲师朱利安·霍尔指出："虽然实践表明这些问题总在多项式时间内解决，但巴赫与休伯特斯为这种直觉提供了更强数学支撑。现在更容易说服那些担忧指数复杂度的人了。"

英文来源：

Researchers Discover the Optimal Way To Optimize
Introduction
In 1939, upon arriving late to his statistics course at the University of California, Berkeley, George Dantzig — a first-year graduate student — copied two problems off the blackboard, thinking they were a homework assignment. He found the homework “harder to do than usual,” he would later recount, and apologized to the professor for taking some extra days to complete it. A few weeks later, his professor told him that he had solved two famous open problems in statistics. Dantzig’s work would provide the basis for his doctoral dissertation and, decades later, inspiration for the film Good Will Hunting.
Dantzig received his doctorate in 1946, just after World War II, and he soon became a mathematical adviser to the newly formed U.S. Air Force. As with all modern wars, World War II’s outcome depended on the prudent allocation of limited resources. But unlike previous wars, this conflict was truly global in scale, and it was won in large part through sheer industrial might. The U.S. could simply produce more tanks, aircraft carriers and bombers than its enemies. Knowing this, the military was intensely interested in optimization problems — that is, how to strategically allocate limited resources in situations that could involve hundreds or thousands of variables.
The Air Force tasked Dantzig with figuring out new ways to solve optimization problems such as these. In response, he invented the simplex method, an algorithm that drew on some of the mathematical techniques he had developed while solving his blackboard problems almost a decade before.
Nearly 80 years later, the simplex method is still among the most widely used tools when a logistical or supply-chain decision needs to be made under complex constraints. It’s efficient and it works. “It has always run fast, and nobody’s seen it not be fast,” said Sophie Huiberts of the French National Center for Scientific Research (CNRS).
At the same time, there’s a curious property that has long cast a shadow over Dantzig’s method. In 1972, mathematicians proved that the time it takes to complete a task could rise exponentially with the number of constraints. So, no matter how fast the method may be in practice, theoretical analyses have consistently offered worst-case scenarios that imply it could take exponentially longer. For the simplex method, “our traditional tools for studying algorithms don’t work,” Huiberts said.
But in a new paper that will be presented in December at the Foundations of Computer Science conference, Huiberts and Eleon Bach, a doctoral student at the Technical University of Munich, appear to have overcome this issue. They’ve made the algorithm faster, and also provided theoretical reasons why the exponential runtimes that have long been feared do not materialize in practice. The work, which builds on a landmark result from 2001 by Daniel Spielman and Shang-Hua Teng, is “brilliant [and] beautiful,” according to Teng.
“It’s very impressive technical work, which masterfully combines many of the ideas developed in previous lines of research, [while adding] some genuinely nice new technical ideas,” said László Végh, a mathematician at the University of Bonn who was not involved in this effort.
Optimal Geometry
The simplex method was designed to address a class of problems like this: Suppose a furniture company makes armoires, beds and chairs. Coincidentally, each armoire is three times as profitable as each chair, while each bed is twice as profitable. If we wanted to write this as an expression, using a, b and c to represent the amount of furniture produced, we would say that the total profit is proportional to 3a + 2b + c.
To maximize profits, how many of each item should the company make? The answer depends on the constraints it faces. Let’s say that the company can turn out, at most, 50 items per month, so a + b + c is less than or equal to 50. Armoires are harder to make — no more than 20 can be produced — so a is less than or equal to 20. Chairs require special wood, and it’s in limited supply, so c must be less than 24.
The simplex method turns situations like this — though often involving many more variables — into a geometry problem. Imagine graphing our constraints for a, b and c in three dimensions. If a is less than or equal to 20, we can imagine a plane on a three-dimensional graph that is perpendicular to the a axis, cutting through it at a = 20. We would stipulate that our solution must lie somewhere on or below that plane. Likewise, we can create boundaries associated with the other constraints. Combined, these boundaries can divide space into a complex three-dimensional shape called a polyhedron.
The execution of the simplex algorithm from start to finish, represented geometrically, involves finding the path — from, say, the bottom vertex to the uppermost point — that involves the fewest steps or, equivalently, traces the fewest edges. The total number of steps, in turn, relates to the runtime (or “complexity”) of the algorithm, with the goal being to solve the problem in the minimum number of steps. Identifying the shortest route from bottom to top in this picture amounts to figuring out the most efficient form that such an algorithm can take.
Finding a quick and direct path might be easy, were it not for two things: First, the original shape is likely to be far more complicated than our example, with many more faces, vertices and edges. And second, there is no map to guide you. You can’t see the entire object you’re trying to navigate. Instead, you start at one vertex and make a choice regarding which edge to follow first. You do the same at the next vertex, and so on, not knowing for sure where the edge you chose will take you.
If you are extraordinarily unlucky, you could take the wrong turn at each vertex and get stuck in a labyrinth. “You could walk the longest possible path to get from A to B,” Bach said, “because at each corner there’s someone who tells you that you should go in the wrong direction.” That’s the kind of situation that could lead to the worst-case scenarios that take an exponential amount of time to complete.
In 2001, Spielman and Teng proved that the tiniest bit of randomness can help prevent such an outcome. Going back to the previous example — at the risk of greatly oversimplifying Spielman and Teng’s argument — let’s suppose that there are six choices at every corner you come to. If you’re always told the worst direction to go in, you’ll be in trouble. However, if you instead rely on a roll of the dice, you’ll have a five-out-of-six chance of avoiding the worst pick, and disaster may be averted. Injecting an element of randomness and uncertainty into the process is reasonable, given that in the real world, measurements are never exact. Spielman and Teng introduced randomness in an entirely different way, but they showed that the running time can never be worse than the number of constraints raised to a fixed power — for instance, n2 — which is an example of what’s called polynomial time. That’s a lot better than exponential time, which takes the form of, say, 2n.
Nevertheless, this didn’t completely solve the issue. Their polynomial time values were still rather high, Huiberts noted — they included a term raised to the power of 30, which is a pretty big number for an exponent. So, over the past two decades, researchers have been making incremental progress in bringing this value down.
In their new paper, Bach and Huiberts relied on even more randomness in their algorithm to show that runtimes are guaranteed to be significantly lower than what had previously been established. They also showed that an algorithm based on the approach established by Spielman and Teng cannot go any faster than the value they obtained. It tells us, Huiberts said, “that we fully understand [this] model of the simplex method.”
“This marks a major advance in our understanding of the [simplex] algorithm,” said Heiko Röglin, a computer scientist at the University of Bonn, “offering the first really convincing explanation for the method’s practical efficiency.”
Nevertheless, Huiberts does not see this as the end of the line. The approach that started in 2001 with Spielman and Teng showed how runtimes can be reduced from exponential to polynomial time. The next logical step is to invent a way to scale linearly with the number of constraints. “That is the North Star for all this research,” she said. But it would require a completely new strategy. “We are not at risk of achieving this anytime soon.”
While the efforts of Bach and Huiberts are of theoretical interest to colleagues in their field, the work has not yielded any immediate practical applications. Nevertheless, it may serve to calm some of the worries that people might have about relying on software available today that is based on the simplex method. “While practical experiments show that these problems are always solved in polynomial time,” said Julian Hall, a lecturer in mathematics at the University of Edinburgh who designs linear programming software, Bach and Huiberts have provided stronger mathematical support for that intuition. “Hence it’s now easier to convince those who fear exponential complexity.”