On the facet pivot simplex method for linear programming

本文提出了一种用于线性规划的新型面枢轴单纯形法，数值测试表明其优于传统的顶点枢轴方法，为发现多项式时间枢轴算法带来了新的希望。

要点

想象一下，你正在一座城市中寻找设立柠檬水摊位的绝对最佳位置。这座城市形状如同一座复杂的多面体建筑（多胞形），而你的目标是找到那个能为你带来最多收益的角落。

七十多年来，解决这一问题的标准方法是顶点枢轴法（由乔治·丹齐格发明）。可以将这种方法想象成一名游客在建筑物的外部行走。他们从一个角落（顶点）出发，观察相邻的角落，然后走向看起来更好的那个。他们沿着边缘从一个角落跳到另一个角落，直到找到最佳位置。

问题在于，有时这座建筑被设计成拥有错综复杂的角落迷宫。在最坏的情况下，游客可能必须以某种令人筋疲力尽的顺序，走遍每一个角落，才能找到最佳位置。这就像穿过一个随着建筑物变大而呈指数级延长的迷宫。

新构想：“面枢轴”法

在本文中，作者杨亚光提出了一种解决该问题的新方法，称为面枢轴单纯形法。

与其沿着角落（顶点）行走，不如想象你是一名建筑检查员，正在审视建筑物的面（facets）。

• 旧方法（顶点）： 你是一名从一个角落跳到另一个角落的游客。
• 新方法（面）： 你是一名检查员，通过交换定义你当前“基座”的面（facets），从而更接近最佳位置。

以下是新方法的简单运作原理：

1. 从面开始，而非角落： 算法不是从一个角落开始，而是先选择一组定义临时（可能不完美）位置的面（约束条件）。
2. 交换面，而非角落： 算法审视当前“未满足”的面（例如一个方向错误的面）。它选出最糟糕的一个，并将其替换为另一个有助于解决问题的面。
3. 无需"Phase 1"绕行： 旧方法通常需要一个漫长且昂贵的"Phase 1"行程，仅仅为了在开始寻找最佳位置之前找到一个有效的起始角落。新方法非常巧妙：它从一个数学上保证能立即生效的设置开始，完全跳过了那段漫长的绕行。这就像拥有一把能瞬间打开建筑大门的魔法钥匙，而不是先尝试撬锁。

为何令人兴奋？

论文声称，这种新方法之所以非常有前景，主要有两个原因：

• 在复杂迷宫中速度更快： 作者在"Klee-Minty 立方体”上测试了该方法，这些是专门设计用来诱骗旧游客方法耗时极久的数学迷宫。新的换面法解决这些迷宫的速度要快得多，仅需几步而非数千步。
• 更具鲁棒性： 在针对大量现实世界数学问题（Netlib 基准测试）的测试中，新方法几乎成功解决了所有问题。旧的“游客”方法有时会陷入停滞或耗时极长，而“对偶”方法（另一种类型的游客）有时会因为建筑的几何结构过于棘手而放弃。换面法更好地处理了这些棘手的几何结构。

局限与希望

论文承认，对于非常大且简单的问题，旧方法（或其他如“内点法”的方法，这就像驾驶无人机穿过建筑物内部）可能仍然更快。

然而，巨大的希望在于，这种新的“换面”方法可能是解开一个著名 60 年数学谜题的关键：我们能否找到一种对所有问题都保证快速（多项式时间）的方法？

几十年来，数学家们一直试图证明旧的“跳角”方法足够快，但他们发现了该方法极其缓慢的案例。这种新的“换面”方法提供了一个全新的视角。它不依赖那些陈旧的规则，早期的测试表明，它可能是通往一种对所有类型的线性规划问题都既快速又可靠的解决方案的路径。

总结： 本文介绍了一种通过交换“面”（facets）而非跳跃“角落”来解决数学优化问题的新方法。它跳过了枯燥的设置步骤，比旧方法更好地处理了棘手的迷宫，并为数学家们带来了新的希望，即找到一种适用于所有问题的完美、快速的解决方案。

技术摘要

技术摘要：关于线性规划的超平面枢轴单纯形法

问题陈述
本文探讨了用于求解线性规划（LP）问题的标准顶点枢轴单纯形法的计算效率与理论局限性。尽管 Dantzig 的顶点单纯形法在实践中依然非常有效，但它缺乏已证明的多项式时间复杂度界限。理论上，顶点方法的最坏情况涉及指数级迭代次数（如 Klee-Minty 立方体所示），而寻找多项式时间枢轴算法的尝试数十年来一直未果。此外，传统的顶点方法通常需要一个计算昂贵的“第一阶段”过程来寻找初始可行基解，特别是对于涉及不等式和边界约束的一般线性规划问题。

方法论
作者提出了一种超平面枢轴单纯形法，该方法从根本上将枢轴操作从顶点转移到了超平面（约束）上。

• 一般形式：该方法在一般线性规划形式上运作：
  $$\min c^T x$$
  $$\text{subject to } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  与通过引入松弛变量将不等式转换为等式的标准形式不同，该方法直接将不等式约束视为可行多面体的超平面。

• 算法逻辑：

  • 基的定义：与基于变量（顶点）的基不同，该算法维护一组 $d$ 个线性无关的超平面（约束）作为基，其中 $d$ 是问题的维度。
  • 迭代过程：算法从一个初始基解开始（通常直接由边界约束导出），该解不一定可行。在每次迭代中，它选择一个进入超平面（非基约束）和一个离开超平面（基约束）来更新基。
  • 可行性与最优性：该算法将目标向量 $c$ 表示为当前基超平面的非负线性组合（满足由 Farkas 引理推导出的条件）。它通过替换超平面以减少约束违反，从而迭代改进解。
  • 终止：当找到基本可行解时，过程停止。根据所提出的最优性定理，如果目标向量可以表示为可行点处活跃基超平面的非负组合，则该点是最优的。
  • 有限收敛：本文证明，如果在选择进入和离开超平面时应用“最小/最低索引规则”，算法将避免循环并在有限步数内终止。

• 与对偶单纯形法的关键区别：虽然超平面枢轴法与对偶单纯形法在几何上有一些相似之处（即在约束基之间移动），但它是独特的，因为它仅在原始问题上操作，无需显式构建或求解对偶问题。它直接处理一般形式，避免了转换为标准形式的过程。

主要贡献

1. 算法提议：本文提出了一种特定的超平面枢轴算法（算法 4.1），可求解一般线性规划问题，而无需第一阶段初始化步骤。
2. 理论保证：作者提供了基于 Farkas 引理的数学证明，表明该算法能在有限次迭代中找到最优解，并正确识别不可行或无界问题。
3. 实现：提供了该算法的 MATLAB 实现，以及 Dantzig 单纯形法、对偶单纯形法和内点法的实现，用于比较。
4. 约束处理：该方法自然地处理下界、上界和自由变量，无需引入人工松弛变量，与标准形式转换相比，从而减小了问题规模。

实验结果
作者在多个基准集上进行了数值测试：

• Netlib 基准：在带有下界和上界的标准 Netlib 问题上，超平面枢轴法通常比 Dantzig 的最负枢轴规则需要更少的 CPU 秒数。它成功解决了对偶单纯形法因秩亏或病态而失败的问题。
• 大规模问题：对于非常大的问题（例如 $n > 50,000$），正如预期，内点法（IPM）优于所有枢轴方法。然而，在对偶单纯形法失败的地方，超平面枢轴法表现出了鲁棒性。
• Klee-Minty 立方体：在 Klee-Minty 变体上，超平面枢轴法的性能显著优于 Dantzig 的顶点法，所需的迭代次数远少于顶点法（通常为维度 $d$ 的线性或近线性），而顶点法需要指数级迭代。
• 随机一般问题：对于标准方法需要第一阶段的通用线性规划问题，超平面枢轴法比 Dantzig 方法效率高得多，因为它绕过了第一阶段初始化。
• 标准随机问题：对于不需要第一阶段的标准线性规划问题，观察到 Dantzig 方法在 CPU 时间上略有效率，尽管迭代次数相当。

意义与主张
本文声称，超平面枢轴单纯形法为基于顶点的方法提供了一个有前景的替代方案，特别是对于具有不等式约束的一般线性规划问题。其主要意义在于：

• 消除第一阶段：通过从由边界约束导出的基解开始，它避免了传统单纯形法处理一般问题所需的昂贵初始化阶段。
• 鲁棒性：在病态的 Netlib 问题上，它表现出比对偶单纯形法更强的数值稳定性。
• 多项式复杂度的希望：虽然作者并未声称已证明多项式时间界限，但他们指出，这种新型枢轴算法（在超平面上而非顶点上操作）为寻找多项式枢轴单纯形法提供了一条新途径，从而解决 Smale 第 9 个问题。
• 实际效率：该方法被证明极具竞争力，且对于涉及许多不等式约束的问题，往往优于 Dantzig 方法，且无需将其转换为等式的开销。

作者保持了谦逊的态度，承认内点法在超大规模问题上仍然更优，并且超平面枢轴法是一个新方向，需要进一步研究以充分理解其理论复杂度界限。