4、线性约束优化：单纯形法核心思想、内点法入门、投影梯度法、线性规划的对偶理论
线性约束优化，说白了就是目标函数和约束条件都是线性的。这类问题在工程中太常见了——资源分配、生产排程、投资组合，几乎天天打交道。我刚开始做优化时，觉得线性规划太简单，不就是画几条直线找交点吗？后来遇到一个供应链调度问题，变量上千个，约束几百条，才明白这里面门道深着呢。
这一章我们聊四个核心方法：单纯形法、内点法、投影梯度法，还有对偶理论。每个方法都有自己的脾气，选对了事半功倍。
4.1 单纯形法核心思想
单纯形法，线性规划的祖师爷。1947年丹齐格提出，到现在还是工业界的标配。它的核心思想其实很朴素：最优解一定在可行域的顶点上。
你想想看，线性函数在凸多面体上的极值，要么在顶点，要么在边界上。单纯形法就是从一个顶点出发，沿着边走到相邻的、目标函数值更好的顶点，直到走不动为止。
核心步骤：
- 找一个初始可行解（顶点）
- 检查当前顶点是否最优（检验数判断）
- 如果不是，选一个进基变量和一个离基变量
- 旋转操作，移动到相邻顶点
- 重复直到最优
我在项目中遇到过一个问题：单纯形法在最坏情况下是指数复杂度的。但别慌，实际应用中它几乎总是多项式时间。为什么？因为那些指数级坏例子太刻意了，真实问题很少那么极端。
个人经验：单纯形法对稀疏问题特别友好。如果你的约束矩阵大部分是0，用单纯形法比内点法快得多。我曾经处理过一个物流网络问题，变量10万+，但每个约束只涉及3-5个变量，单纯形法几分钟就搞定了。
4.2 内点法入门
内点法，1984年卡马卡提出，是单纯形法的强劲对手。它的思路完全不同——不从顶点走，而是从可行域内部穿过去。
说白了，内点法把约束条件变成障碍函数，加在目标函数上。这样迭代点就不会碰到边界，然后慢慢放松障碍项的权重，让解逐渐逼近真正的边界最优解。
# 内点法核心思路（伪代码）
def interior_point(A, b, c, x0, mu=1.0, tau=0.9):
x = x0
while not converged:
# 构造障碍函数梯度
grad = c - mu * sum(1/x_j)
# 求解牛顿方向
dx = solve_newton_system(A, grad)
# 回溯线搜索，保证x > 0
alpha = backtracking(x, dx)
x = x + alpha * dx
# 减小障碍参数
mu = mu * tau
return x
内点法有个好处：迭代次数几乎不随问题规模增长。我做过对比测试，同样是10000个变量的问题，单纯形法要迭代几千次，内点法30-50次就收敛了。当然，每次迭代的计算量更大，因为要解一个大型线性方程组。
避坑指南：我曾经在一个金融风控项目里直接用内点法，结果矩阵接近奇异，牛顿方向算出来全是NaN。后来加了正则化项才稳住。记住，内点法对数值稳定性要求高，一定要做好预处理。
4.3 投影梯度法
投影梯度法，适合约束比较简单的情况——比如只有边界约束（box constraints）或线性等式约束。它的想法很直接：先沿着梯度方向走一步，然后投影回可行域。
嗯，这里要注意：投影操作本身可能很贵。如果可行域是简单的超立方体，投影就是截断，快得很。但如果是一般多面体，投影本身又是一个二次规划问题，那就得不偿失了。
适用场景对比：
| 约束类型 | 投影难度 | 推荐程度 |
|---|---|---|
| 边界约束（x ≥ 0） | O(n)，直接截断 | 强烈推荐 |
| 超立方体（l ≤ x ≤ u） | O(n)，逐元素截断 | 推荐 |
| 线性等式（Ax = b） | O(n³)，需解线性系统 | 谨慎使用 |
| 一般多面体 | 需要求解QP | 不推荐 |
我建议，如果你的问题只有非负约束，投影梯度法是最简单的选择。代码好写，调试方便，收敛性也有保证。
4.4 线性规划的对偶理论
对偶理论，线性规划里最美妙的部分。每个线性规划问题（原问题）都有一个对应的对偶问题。原问题求最小，对偶问题求最大；原问题的约束对应着对偶问题的变量。
为什么对偶重要？三个原因：
- 下界估计：对偶问题的任意可行解，都给出原问题最优值的下界（或上界）
- 敏感性分析：对偶变量就是影子价格，告诉你资源每增加一单位，目标值能改善多少
- 算法加速：很多算法（比如单纯形法）同时求解原问题和对偶问题，效率更高
我记得有一次做生产计划优化，原问题有5000个变量，求解很慢。后来发现对偶问题只有50个变量，几分钟就解完了，然后通过互补松弛条件反推出原问题的最优解。这就是对偶的力量。
互补松弛条件是对偶理论的核心：原问题的最优解和对偶问题的最优解之间，满足一个简单的关系——如果某个原约束是松的（不紧），那么对应的对偶变量必须为0。反过来也一样。
# 互补松弛条件
# 原问题：min c'x, s.t. Ax ≥ b, x ≥ 0
# 对偶问题：max b'y, s.t. A'y ≤ c, y ≥ 0
# 最优解满足：
# y_i * (A_i x - b_i) = 0, ∀i
# x_j * (c_j - A'_j y) = 0, ∀j
这个条件在工程中特别有用。比如你做一个资源分配问题，对偶变量告诉你哪些资源是瓶颈，哪些资源有富余。我经常用这个来给客户做决策建议——别盲目增加所有资源，先看影子价格最高的那个。
4.5 四种方法对比总结
最后，我把这四种方法放在一起对比一下，方便你选型：
| 方法 | 核心思想 | 适用规模 | 收敛速度 | 实现难度 |
|---|---|---|---|---|
| 单纯形法 | 沿顶点移动 | 中小规模（变量<1万） | 中等，但实际很快 | 中等 |
| 内点法 | 从内部逼近 | 大规模（变量>1万） | 快，O(√n)次迭代 | 高 |
| 投影梯度法 | 梯度下降+投影 | 简单约束问题 | 线性收敛 | 低 |
| 对偶理论 | 转换问题视角 | 辅助分析 | 不直接求解 | 中等 |
我个人习惯是：先看约束类型。如果约束简单，投影梯度法走起。如果问题规模大，内点法更稳。如果问题规模中等且稀疏，单纯形法最靠谱。至于对偶理论，它更像一个分析工具，帮你理解问题的结构，而不是一个直接求解器。
这一章的内容就到这里。四种方法各有千秋，没有银弹。关键是根据你的问题特点，选最合适的工具。下次遇到线性约束优化问题，你应该知道从哪个方向入手了。