优化 | 内点法与单纯形法的一个关键区别：谁能真正落在 LP 的顶点上

来源：市场资讯

（来源：运筹OR帷幄）

很多人在学习线性规划求解器时，都会遇到一个看似“漫不经心”、其实非常重要的问题：

• 内点法可以很快得到一个 LP 的最优解；

• 但它通常不保证这个最优解是一个顶点解 / 基解；

• 单纯形法则不同，它的迭代对象本身就是基可行解，所以算法结束时天然落在一个最优基解上。

是不是顶点解到底会影响以下几件事：

• 求解器是否能返回 basis；

• 是否方便做 reoptimization；

• 是否便于做灵敏度分析；

• 对整数规划的 LP 松弛而言，是否更利于后续 cut、branch、rounding 和 warm start。

1994 年 Bixby 和 Saltzman 的论文就把这个问题作为一个核心挑战来讨论：如何从 interior point solution 中恢复一个 optimal LP basis。现代求解器(Gurobi/CPLEX/COPT) 无一例外都有类似的策略 （称之为 Crossover）来将内点法得到的非顶点最优解恢复为一个顶点最优解。 本篇文章仅从科普的角度来拆解内点法为何难以直接获取顶点解，以及为什么顶点解重要。

1 用一个简单例子从几何直觉出发

内点法可以得到 LP 的最优解，但一般不保证得到的是“顶点最优解 / 最优基解”；而单纯形法的迭代对象本身就是基解，所以它结束时天然落在一个最优基解上。

我们先从一个简单的小例子出发，来直观阐述上述结论：

它的可行域是二维平面里的一个三角形，三个顶点是：

因为目标就是最大化 ，所以所有满足

的点都是最优解。具体的可行域见下图：

这条最优边的两个端点 和 是顶点；但中间点，比如

也是最优解，只是它显然不是顶点。

我们知道单纯形法是在顶点之间跳跃的算法。它的状态始终是基可行解，也就是顶点解；每一步 pivot 的本质，是从一个顶点走到相邻顶点。因此，对上面这个例子来说，单纯形法最终一定会停在：

总之，它会返回一个最优顶点解。

然而对于内点法来说情况则完全不同。内点法本身搜索的过程就不是沿着多面体的边界跑，而是从可行域内部逐步向外部推进。那么对于我们这个简单的例子来说

• 内点法搜索过程不会贴着边走；

• 内点法搜索过程会从三角形内部朝着最优面靠近；

• 当最优解不是唯一，而是一整条边都最优时，它通常会逼近这条最优边的“中间位置”，而不是某个端点。

进一步我们可以得到内点法最终很可能收敛到 线段中间的某个点上去，而大概率并不会收敛到两个顶点上去。

2 进一步用代数的方式解释：内点法为什么通常无法保证得到顶点解？

上面是几何直觉。下面我们把这个现象写成内点法子问题。对于前面的 LP，内点法会求解一系列带障碍项的子问题，例如：

这里要求：

这个目标由两部分组成：

1. 原始目标: ：推动你去优化原 LP；

2. 障碍项：, 它会在接近边界时趋向 ，因此强烈排斥边界。

我们从上述内点法的目标函数也可以看出内点法在搜索过程中遵循的原则是：

• 既要让目标值尽量好；

• 又要尽量别靠边界太近。

在我们的例子里，最优面是直线段 。如果比较这一条边上的不同点：

• 端点 和 贴着更多边界；

• 中间点 离两侧边界更“均衡”。 所以 barrier 会偏向最优面的中间，而不是顶点。内点法可以保证达到最优值，但不能天然保证返回的是最优顶点解。

在求解器中如果想要用内点法求解LP的顶点解，就先让内点法把最优值的 interior solution 算出来，再交给 simplex 一侧去恢复出来一个基解。

3 为什么我们需要顶点解？

到这里你自然会产生一个问题：既然 interior solution 也是最优解，那为什么还要执着于去找顶点解？

答案是：在很多优化算法和求解器工程里，顶点解不仅仅是“一个解”，它还是一种非常重要的结构性状态。在标准形 LP 里，顶点解和 basic feasible solution (BFS) 是等价的。也就是说，拿到顶点解，本质上就是拿到了一个 basis。而有了 basis，很多事情才能高效做起来，具体来说分为以下几个方面：

它让重优化变得高效：实际模型往往不是只解一次。 约束右端项变一点、目标系数改一点、加几条约束、删几条变量，模型就要重新求。这时，如果手里有一个旧 basis，很多 LP 可以直接在这个 basis 的基础上 warm start，而不必从零开始。 这也是 simplex 体系在 reoptimization 中一直非常强的原因之一。

Basis 本身会提供很多额外的重要信息：很多教材里耳熟能详的概念，例如 reduced cost，本质上都不是“只要有一个最优解就行”，而是与当前最优 basis 紧密相关。以 Gurobi 为例，目标系数和变量上下界的灵敏度属性都明确标注为：only available for basic solutions。所以如果你只有 interior solution，而没有 crossover 后的 basis，那么这类经典灵敏度分析就没有现成接口可用。

整数规划中很多时候需要顶点解：在 MIP 里，很多理论和工程机制比方说 cuts、branching 状态传递、basis warm start、节点 LP 的连续重优化——本来就是围绕 LP 极点/基解这一结构来组织的。此外，大多数情况下顶点解比非顶点解更加接近整数，这一点对整数规划问题来说尤为重要。

综上所述：我们需要顶点解，不只是因为它“看起来更极端”，而是因为它承载了 basis、组合结构、重优化能力、灵敏度分析能力，以及与整数规划模块衔接的能力。

4 数值实验结果

Gurobi 官方提供了专门的参数来控制 Crossover。Crossover 的作用就是把内点法得到的 interior solution 转换成一个 basic solution。

我们分别对比打开Gurobi的 Crossover 和 关闭 Crossover 两组实验，看对于同一个线性规划问题是不是获得的最优解如我们之前分析的结果。

以 Gurobi 为例，官方文档明确说明：

• Crossover=0 表示关闭 crossover，这时 barrier 返回的是 interior solution；

• 默认值 Crossover=-1 表示 自动选择策略；

如果我们想关闭掉 Crossover 可以这些写：

import gurobipy as gpfrom gurobipy import GRB# 创建模型m = gp.Model("lp_example")# 参数设置m.setParam("Presolve", 0)   # 关闭 presolvem.setParam("Method", 2)     # 内点法 (Barrier)m.setParam("Crossover", 0)  # 关闭 crossover# 变量：x1, x2 >= 0，连续变量x1 = m.addVar(lb=0.0, vtype=GRB.CONTINUOUS, name="x1")x2 = m.addVar(lb=0.0, vtype=GRB.CONTINUOUS, name="x2")# 约束：x1 + x2 <= 1m.addConstr(x1 + x2 <= 1, name="c1")# 目标：max x1 + x2m.setObjective(x1 + x2, GRB.MAXIMIZE)# 求解m.optimize()# 打印最优解if m.Status == GRB.OPTIMAL:print(f"最优目标值: {m.ObjVal}")print(f"x1 = {x1.X}")print(f"x2 = {x2.X}")else:print(f"模型未得到最优解，状态码: {m.Status}")

最后运行后得到的结果如下所示： 最优目标值: 0.9999999997224607；x1 = 0.49999999986123034； x2 = 0.49999999986123034

因为我们强制关闭了 Crossover，所以内点法只能得到一个非顶点解。数值实验的结果确实也印证了我们之前的理论。

反过来如果打开 Crossover，只需将上述设置 Crossover 参数的代码（当然什么也不设置也是可以的，因为默认就是打开状态）修改为如下所示即可：

m.setParam("Crossover", -1)  # 开启 crossover

修改后我们发现日志会多出来关于Crossover的内容：

那么进一步得到最终结果如下所示： 最优目标值: 1.0；x1 = 1.0；x2 = 0.0； 此时返回的是一个顶点解。

这并不是 barrier 本身突然“喜欢顶点”了，而是因为 Crossover 帮你把非顶点解恢复成了一个顶点解。

5 总结

很多初学者者会把“内点法”和“单纯形法”的区别简单理解成：一个适合大规模求解，一个适合中小规模求解，一个是多项式复杂度的算法，一个从算法复杂度来说是指数级别的。这样的理解方式当然有一部分事实基础，但还不够抓住本质。

更本质的差别是：

• 单纯形法从头到尾都把“基解 / 顶点”作为自己的工作对象；

• 内点法从头到尾都把“内部路径”作为自己的工作对象。

二者虽然都能到达 LP 的最优值，但它们天然产出的“最优解的形态”并不一样。前者天然给你 basis，后者只能给你 interior solution；

而现代求解器之所以要设计 Crossover 算法，正是为了把这两种世界接起来。Gurobi 文档对这一点的表述非常直接：内点法先给出 interior point solution，Crossover 再把它转成 basic solution

如果你更关心“如何把 interior point solution 恢复成 optimal basis”，可以继续看 Bixby 和 Saltzman 1994 年的经典文章（见参考文献【1】）；直到今天为止 Crossover 依然是 LP 求解器工程中的必不可少的关键模块。

参考文献：

【1】Bixby R E, Saltzman M J. Recovering an optimal LP basis from an interior point solution[J]. Operations Research Letters, 1994, 15(4): 169-178.