blog

Intro: Operational Research, Optimization and Linear Programming

运筹学，最优化，线性规划，三者之间的关系是什么？

运筹学要解决的问题是，如何利用有限的资源，使得某些利益最大化；为了完成某个既定的目标，如何才能最小化资源消耗。最优化要解决的问题是，建立模型后如何求出最优解。运筹学片中解决实际问题，更注重建模；而最优化则侧重于对优化的理论研究。

线性规划是优化领域中研究最早、应用广泛且方法成熟的一个重要分支。我们将从线性规划开始，展开对运筹学的研究。

Linear Programming

Geometry Foundation

Affine and Convex Sets

如果一个非空集合 Q 满足对任意两点 $x_1, x_2 \in Q$，其仿射组合始终属于 Q，即对于任意 $\theta \in \mathbb{R}$ 有

$$ \theta x_1 + (1-\theta)x_2 \in Q $$

那么称 Q 是一个仿射集。

如果一个非空集合 C 满足，对任意 $x_1, x_2 \in C$，其凸组合始终属于 C，即对于任意 $0 \le \theta \le 1$ 有：

$$ \theta x_1 + (1-\theta)x_2 \in C $$

那么称 C 是一个凸集。

线性方程组的解集构成仿射集，而任意的仿射集必定是凸集。线性规划的可行域总是表现为凸集，这一性质在分析优化问题时，保证了局部极小值即为全局极小值。

Polyhedron, Hyperplanes and Halfspace

超平面是空间中满足线性等式的点集

$${x : a^T x = b} $$

其中 $a \in \mathbb{R}^n \ne 0, b \in \mathbb{R}$。 半空间是为超平面将空间划分成的两个区域之一，对应线性不等式的点集

$${x : a^T x \ge b},{x : a^T x \le b}$$

多面体定义为有限个半空间和超平面的交集，即有限个线性等式和不等式的解集：

$$ {x : A x \le b} $$

这些概念为约束条件提供了直观的几何载体。线性规划中的每一个等式和不等式约束在几何上对应于超平面和半空间。多面体是对线性规划可行域的直观理解，说明可行域是由平直边界围成的几何体。

Vertex, Extreme point and Basic feasible solution

对于多面体 $P = {x : A x \le b}$，若存在某个 $c \in \mathbb{R}^n$，使得对于多面体中所有其他的点 $y \ne x$ 均有：

$$ c^T x < c^T y $$

则称 $x$ 是多面体 P 的顶点。

若 $x \in Q$ 无法表示为 Q 内其它两个不同元素的凸组合，那么称 $x$ 是极限点。

若 $x \in P$ 满足 $n$ 个线性无关的紧约束，则 $x$ 是一个基本可行解。

可以证明对于多面体，$ \text{顶点} \Longleftrightarrow \text{极限点} \Longleftrightarrow \text{基本可行解} $

上述定理建立了代数与几何的直观连接。几何上多面体最突出的角点（极点与顶点），在代数上对应方程组的特定基底解（基本可行解），这正是单纯形法寻找最优解的立足点。

Ray, Recession Cone and Extreme Ray

给定非空集合 Q 和向量 $d$，如果对任意的 $x \in Q$ 和 $\alpha \ge 0$ 都有 $x + \alpha d \in Q$ 成立，则称 $d$ 为回收方向。Q 的所有回收方向的集合记作 $\text{rec}(Q)$。对于多面体 $P = {x : A x \le b}$，其回收锥为：

$$ \text{rec}(P) = {d \in \mathbb{R}^n : A d \le 0} $$

对于多面体回收锥中的非零元素（射线），如果它不能表示成多面体中其它两个线性无关的射线的正数倍组合，则该射线为极射线。

回收锥和射线理论刻画了可行域的无界性。通过极射线，能够提取出无限延伸方向的基底向量，这是理解无界线性规划目标函数为何发散的几何本质。

Separating Hyperplane Theorem

设 $Q \subset \mathbb{R}^n$ 是闭的非空凸集，$x_0 \notin Q$，必存在一个非零向量 $a \in \mathbb{R}^n$ 和标量 $b \in \mathbb{R}$，使得：

$$ a^T x_0 > b $$

并且对于任意 $x \in Q$ 都有：

$$ a^T x \le b $$

几何直观：如果在空间中放置了一个实心的、向外凸起的封闭物体（闭凸集），而在其外部有一个游离的点。无论这个点离物体多近，我们总能拿出一块无限大的平坦纸板（超平面），插在两者之间，使得点在纸板的一侧，而整个物体在纸板的另一侧。

此定理是建立整个凸优化和对偶理论的基石，提供了一种通过构造超平面来证明多面体结构等价性质（例如 Farkas 引理与强对偶性）的强力数学工具。

Minkowski-Weyl Theorem

设 $P \subset \mathbb{R}^n$ 是一个多面体，那么必定存在有限的向量集 ${v_1, ..., v_k}$ 和 ${u_1, ..., u_l}$ 使得：

$$ P = \operatorname{Conv}\{v_1, \ldots, v_k\} + \operatorname{Cone}\{u_1, \ldots, u_l\} $$

即多面体可以被表示为其顶点的凸组合与极射线的锥组合的 Minkowski 和。

几何直观：任何表面由平坦切面削成的具有棱角的几何空间（由半空间交集定义的外代数表示），等价于用若干个实实在在的角点和指向无穷远处的射线支架向外撑起来的几何空间（内几何表示）。

这一定理证明了无限空间中的可行域也可通过有限的数据点来完全重构和表达，使得理论推导极大简化。

Fundamental Theorem of Linear Programming

考虑线性规划问题 $\max {c^T x : x \in P}$，其中 P 是一个尖多面体（不包含一条直线），则如下论述成立：如果 P 非空，那么必定存在基本可行解；若 P 非空且目标函数无上界，那么存在向量 $d$ 满足在射线上目标函数能取得任意大值；若 P 非空且目标函数有上界，那么线性规划必定在某个顶点处取得最优解。

在常见的有界情形中，此定理指出线性规划的解必然在多面体的边界上，不可能在内部。它将搜索空间收缩为有限个顶点间的离散组合，为后续单纯形法提供了计算可行性保证。

Simplex Method

Standard Form and Slack Variables

如果线性规划问题最初包含不等式约束，通过引入非负的松弛变量 $ x_s \ge 0$，可将其转化为等式约束的标准形式：

$$ A x + x_s = b $$

松弛变量度量了当前解距离不等式约束边界的距离。当某个松弛变量为零时，说明对应的约束是紧凑的，即解恰好位于该超平面的边界上。

这是一种标准化的代数处理手段，使得一般形式的线性规划问题能够以矩阵方程组的形式进行计算。

Basic Variables, Non-basic Variables and Reduced Cost

线性规划在标准形式下往往有 $m$ 个等式约束，有 $n$ 个变量，且 $n$ 通常远大于 $m$，所以方程组有无数个解。 为了找到最优解，单纯形法采取了一种降维策略：人为挑选 $n-m$ 个变量，把它们设为 0，剩下的 $m$ 个变量就可以通过求解 $m$ 个方程唯一确定下来了。

基变量：被选中参与求解方程组的那 $m$ 个变量。它们对应矩阵 A 中线性无关的 m 列，拼成了可逆的基矩阵 B。在几何上，基变量大于 0 意味着我们在多面体的内部或某些松弛边界上，当它们刚好求出来是非负数时，我们就站在了多面体的一个顶点上。

非基变量：被强行设为 0 的那 $n-m$ 个变量。在几何上，一个变量等于 0 意味着当前的位置正紧贴某条特定的边界（超平面）。

接下来解释检验数 (Reduced Cost)。当我们站在一个顶点时，想要知道沿着某条边走能不能让结果更好，我们就需要试探：如果把某个被打入冷宫的非基变量释放出来（让它从 0 缓慢增加），会对目标函数产生什么影响？

$$ \Delta_j = c_j - c_B^T B^{-1} A_j $$

这个公式可以这么理解：

• 提取出的 $ c_j$ 是直接收益：引入这个非基变量带来的单位目标提升。
• 提取出的 $ B^{-1} A_j$ 是资源消耗率：非基变量的增加，势必会挤占原有 $m$ 个基变量的资源，因为等式约束的总量是固定的。
• 提取出的 $c_B^T B^{-1} A_j $ 是机会成本：为了平衡等式，原有的基变量被迫减少，从而损失的目标函数价值。

因此，检验数度量的就是释放该变量带来的净利润。如果在最大化问题中，所有非基变量的检验数都不大于 0，说明无论释放哪个方向，净利润都是亏损的。这就从代数上严格证明了，我们已经到达全局最优解。

考虑一个 toy example：生产产品 1 和 2，利润分别为 2 和 3。 目标函数：

$$ \max z = 2x_1 + 3x_2 $$

约束条件（比如产量限制）：

$$ x_1 + x_2 \le 4 \\ 2x_1 + x_2 \le 5 \\ x_1, x_2 \ge 0 $$

第一步，加入松弛变量 $x_3, x_4 $，把不等式变成等式标准形式：

$$ x_1 + x_2 + x_3 = 4 — 2x_1 + x_2 + x_4 = 5 $$

此时，目标函数变为：

$$ \max z = 2x_1 + 3x_2 + 0x_3 + 0x_4 $$

第二步，寻找初始极限点。令 $x_1 = x_2 = 0 $，此时$x_1, x_2 $ 就是非基变量。代入方程可得：

$$ x_3 = 4, x_4 = 5 $$

这两个就是当前的基变量。它们构成了初始基本可行解。

第三步，计算检验数。我们现在站在原点，总利润是 0。我们想知道，如果开始生产产品 1，即让非基变量 $ x_1$ 增加 1 单位，是否划算。

对于 $ x_1$，直接收益是 $ c_1 = 2$。增加 1 单位 $ x_1$，为了维持方程平衡，松弛变量 $ x_3$ 会被消耗减少 1，$ x_4$ 会被消耗减少 2。但松弛变量在目标函数中的利润系数是 0，机会成本为 0。净利润检验数 $ \Delta_1 = 2 - 0 = 2$。同理，对于 $ x_2$，直接收益是 3，机会成本是 0，检验数 $ \Delta_2 = 3$。

因为 $ \Delta_2 = 3 > 0$，这说明如果把 $ x_2$ 从非基变量变成基变量，也就是沿着 $x_2 $ 轴的方向离开原点，我们的目标函数会以斜率 3 稳步上升。单纯形法正是依据这个正的检验数，决定将 $ x_2$ 选入基变量，从而向着更高利润的下一个极限点进发。

Simplex Method and Iterative Calculation

单纯形法的具体求解步骤如下：

• 将问题化为标准形式并提取初始基本可行解；
• 计算所有非基变量的检验数，若均满足最优性条件则停止迭代并输出结果；
• 若存在改进空间，则选择一个检验数大于零的非基变量作为入基变量；
• 利用最小比值定理选取使得原基变量最先降为零的变量作为出基变量以保证下一次迭代的可行性，即计算：

$$ \min { (B^{-1} b)_i / (B^{-1} A_j)_i : (B^{-1} A_j)_i > 0 } $$

最后，利用矩阵初等行变换更新单纯形表，完成基底矩阵的转换并重复上述步骤。

几何直观：算法从多面体的一个极限点出发，沿着目标函数值增加的边，贪心地移动到下一个相邻的极限点，直至最优解。

这是线性规划中最基础且极其高效的精确求解算法，它通过有限次的单纯形表代数变换，完美实现了对高维几何空间中最优解的定向搜索。

Big-M Method and Two-phase Method

当初始基本可行解无法通过观察直接获得时，引入人工变量 $ \overline{x} \ge 0$ 构造增广矩阵。大 M 法通过在目标函数中添加极大的惩罚项来迫使人工变量在迭代中出基：

$$ \max c^T x - M \sum \overline{x}_i $$

两阶段法则构造第一阶段目标函数，旨在最小化人工变量之和以寻找初始可行解：

$$ \min \sum \overline{x}_i $$

这两种方法相当于在原有的高维空间外构建了一个具有显式原点起点的辅助多面体，通过不断压榨辅助维度的生存空间，最终引导迭代轨迹平滑地回到到原问题的多面体顶点上。

这种处理机制解决了线性规划问题在缺乏平凡初始解时无法启动单纯形法迭代的难题。

Degeneracy, Cycling and Resolution

退化指的是在基本可行解中存在取值为零的基变量，这可能导致单纯形法在同一点的多个等价基之间发生死循环。Bland 规则是一种解决死循环的有效策略，即在存在多个入基或出基变量候选时，始终选择下标最小的变量：

$$ \min { j : \Delta_j > 0 } $$

采用扰动法、字典序法或 Bland 规则打破了这种由几何对称性引发的陷阱，从代数理论上严格保证了单纯形法在最劣情况下的有限步终止性。

Common Pivoting Rules

转轴规则决定了单纯形法在面对多个可行的上升方向时的路径选择。常见规则有最大正检验数规则以及最陡边缘规则等。最陡边缘规则要求计算单位几何距离内目标提升最大的方向：

$$ \max (\Delta_j) / (|| B^{-1} A_j ||) $$

几何直观：如果把多面体表面视作多面山坡，不同的转轴规则决定了搜索轨迹是仅选择代数指标最优的边，还是选择在实际欧氏几何空间中爬升绝对斜率最大的边。

转轴规则的核心应用价值在于平衡单次单纯形表计算的开销与收敛所需的总迭代次数。

Linear Programming Duality

Primal and Dual Problems and Their Correspondence

对于任意一个标准的线性规划原始问题（Primal），都存在一个与其在数学结构上严格对称的对偶问题（Dual）。设原始问题为最大化形式：

$$ \max { c^T x : A x \le b, x \ge 0 } $$

则其对应的对偶问题为最小化形式：

$$ \min { b^T y : A^T y \ge c, y \ge 0 } $$

其中转换的对应关系为：原始问题的目标函数系数向量 $c$ 成为对偶问题的约束右端项；原始问题的约束右端项向量 $b$ 成为对偶问题的目标函数系数；原始问题的约束矩阵 $A$ 转置后成为对偶问题的约束矩阵；原始问题中的第 $i$ 个约束对应对偶问题中的第 $i$ 个变量，原始问题中的第 $j$ 个变量对应对偶问题中的第 $j$ 个约束。

考虑一个典型的生产计划问题作为原始问题。假设一家工厂生产桌子和椅子两种产品，目标是在给定资源下最大化总利润。

已知生产一张桌子的利润为 50，消耗 4 单位木材和 2 单位人工；生产一把椅子的利润为 30，消耗 3 单位木材和 1 单位人工。工厂拥有的资源上限为：木材 120 单位，人工 50 单位。设桌子产量为 $x_1$，椅子产量为 $x_2$。

原始问题（厂长的视角：优化生产组合以最大化总利润）：

$$ \max z = 50 x_1 + 30 x_2 \\ 4 x_1 + 3 x_2 \le 120 \\ 2 x_1 + x_2 \le 50 \\ x_1, x_2 \ge 0 $$

现在，转换视角，考虑一个外部采购商想要直接打包收购这家工厂的全部木材和人工资源，而不让工厂自行生产。采购商需要为木材设定单价 $y_1$，为人工设定单价 $y_2$。

对偶问题（采购商的视角：优化资源定价以最小化收购总成本）：

首先，采购商的目标是最小化支付给工厂的资源总收购金额：

$$ \min w = 120 y_1 + 50 y_2 $$

其次，采购商的报价必须满足一个基本商业逻辑：让厂长愿意出售资源。厂长会进行核算，如果用 4 单位木材和 2 单位人工自己生产一张桌子，能赚取 50 的利润；那么采购商为这些资源提供的总报价，绝对不能低于 50，否则厂长宁可留下资源自己生产桌子。同理，对生产一把椅子所消耗的资源报价也不能低于 30。这就构成了对偶约束：

$$ 4 y_1 + 2 y_2 \ge 50 \\ 3 y_1 + y_2 \ge 30 \\ y_1, y_2 \ge 0 $$

通过这个代数模型与经济视角的对应，可以清晰地解释对偶转换法则的内在逻辑：

原始问题的资源约束上限（120 和 50），构成了对偶问题中需要最小化的目标函数系数，因为它是采购商要收购的系统资源总量。

原始问题的目标函数系数（即产品利润 50 和 30），构成了对偶问题的约束右端项，因为它是厂长出让资源所能接受的机会成本底线。

原始问题的约束矩阵进行转置，是因为在原始问题中，矩阵按行表示某种资源在不同产品中的分配与消耗；而在对偶问题中，矩阵按列表示某种单一产品中所蕴含的各项资源的内部定价价值之和。

在这个框架下，对偶变量 $y_1, y_2$ 在经济学上即为资源的影子价格（Shadow Price），它揭示了每一单位物理资源在最优化生产系统内部的隐含经济价值。

这种对偶构造提供了一个从资源定价角度看待原始生产计划问题的全新视角，并且在原始问题变量极多而约束较少时，转而求解其对偶问题可以大幅降低计算维度和复杂度。

Shadow Price

影子价格定义为目标函数最优值对某个约束条件右端项常数的偏导数。设 $ z^*$ 为最优目标函数值，$ b_i$ 为第 i 个约束的资源限量，则第 i 种资源的影子价格 $ y_i^*$ 为：

$$ y_i^* = (\partial z^*) / (\partial b_i) $$

在最优解处，对偶问题的最优解向量 $ y^*$ 的各个分量即为对应原始问题约束的影子价格。

影子价格度量了在当前最优生产结构下，增加单位第 i 种资源所能带来的最大边际利润收益。如果某种资源的影子价格为正，说明该资源是限制利润进一步提升的瓶颈；如果为零，则说明该资源相对过剩。这一概念是大规模系统优化中进行灵敏度分析与资源定价的核心。

Weak and Strong Duality Theorems

弱对偶定理指出，对于任意的原始问题可行解 $x$ 和对偶问题可行解 $y$，原始问题的目标值永远被对偶问题的目标值所界定：

$$ c^T x \le b^T y $$

强对偶定理进一步指出，如果原始问题存在有限的最优解 $x^* $，那么对偶问题也必然存在有限的最优解 $ y^*$，且二者的最优目标函数值相等：

$$ c^T x^* = b^T y^* $$

弱对偶定理相当于宣称任何买方的最高出价都不会超过卖方的最低要价；强对偶定理则给出了一个惊人的结论，即在完美的线性系统市场中，买卖双方的底线最终一定相同。强对偶定理不仅给出了判定一个解是否为全局最优解的完美终点条件，也构成了现代内点法与对偶算法的基石。

Complementary Slackness

互补松弛定理刻画了原始最优解 $x^* $ 与对偶最优解 $y^* $ 之间的正交关系。数学形式表述为：

$$ y_i^* (b_i - A_i x^*) = 0 $$$$ x_j^* ( (A^T)_j y^* - c_j ) = 0 $$

该定理说明，如果某个原始不等式约束在最优解处没有取到等号（即资源有剩余，松弛量大于零），那么对应的对偶变量（影子价格）必须严格为零；反之，如果对偶变量大于零，对应的原始约束必须紧约束（资源耗尽）。这在代数上将原始和对偶的最优性条件紧紧绑定，使得我们可以直接通过一个问题的最优解推导出另一个问题的最优解，大幅简化了求解过程。

Alternative Theorems (Farkas Lemma and Gordan Lemma)

Farkas 引理是著名的择一定理，其代数表述为，以下两个线性方程或不等式系统，有且仅有一个存在解。系统一：

$$ A x = b, x \ge 0 $$

系统二：

$$ A^T y \ge 0, b^T y < 0 $$

几何直观：给定一个由矩阵 A 的列向量张成的多面锥，以及一个目标向量 b。那么向量 b 要么完全落入这个多面锥的内部（系统一有解）；要么它游离在锥外，此时我们一定能找到一个穿过原点的超平面，把向量 b 和多面锥严格地分隔在两侧（系统二有解）。

Farkas 引理是建立分离超平面理论与证明线性规划强对偶定理的最基础的纯代数工具，它将几何上的凸集分离性转化为了严格的矩阵方程可解性判据。

Dual Simplex Method and Primal-Dual Method

对偶单纯形法是直接在对偶空间执行搜索的算法。它要求初始单纯形表满足对偶可行性（即所有检验数均非正），但违反原始可行性（即存在负的基变量）。算法首先挑选一个取值为负的基变量出基以试图修复原始可行性，然后通过最小比值测试：

$$ \min { (\Delta_j) / (A_{i j}) : A_{i j} < 0 } $$

选择入基变量，以确保在转轴后对偶可行性不被破坏。如此迭代直到所有基变量均非负，此时即同时达到原始可行与对偶可行，即取得全局最优解。

原始-对偶方法则同时维护原始和对偶两个系统的变量。它利用当前对偶解构造一个受限原始问题（Restricted Primal），通过求解该受限问题来决定如何更新对偶解，使得对偶目标函数稳步改善。

对偶单纯形法在面对增加新约束条件或者修改右端项导致原始可行性丢失的场景时极为高效，因为它不需要像大 M 法那样重新从零开始寻优，而是直接从当前的最优边界出发向内修复。原始-对偶方法则是诸多近似算法与网络流问题（如最短路径、匹配问题）的底层框架。

Advanced Linear Programming and Large Scale Decomposition

Sensitivity Analysis

Geometric and Algebraic Analysis of Objective Coefficient Changes

在最优解的灵敏度分析中，设原问题的基变量为 $x_B $，非基变量为 $x_N $，最优基矩阵为 $B$。当目标函数中某个变量 $x_j $ 的利润系数 $c_j $ 发生扰动变为 $c_j + \Delta c_j $ 时，代数上的核心在于检验当前最优解的最优性条件（即检验数）是否被破坏。

非基变量的系数变化，其仅仅影响自身的检验数：

$$ \Delta_j' = (c_j + \Delta c_j) - c_B^T B^{-1} A_j = \Delta_j + \Delta c_j $$

为保持当前最优解不变，必须有 $\Delta_j' \le 0 $，即 $ \Delta c_j \le -\Delta_j$。

对于基变量 $x_k $ 的系数变化，由于其改变了基底收益向量 $c_B $，会导致所有非基变量的检验数发生连锁反应。新的基收益向量变为 $ c_B + \Delta c_k e_k$，所有非基变量必须满足：

$$ \Delta_j^{\prime} = c_j - \left(c_B + \Delta c_k e_k\right)^T B^{-1} A_j \le 0 $$

这会解出一个允许的扰动区间 $[\Delta c_{\min}, \Delta c_{\max}]$

在几何上，目标函数系数定义了等值超平面的法向量。改变系数，等价于在多面体空间中转动目标函数等值面。只要转动的幅度没有越过与之相邻的多面体边界（即斜率变化在某两条临界棱的斜率之间），当前的最高顶点依然是最高顶点，最优生产方案 $ x^*$ 就无需更改。此分析的作用在于评估市场价格波动时，当前生产计划的鲁棒性。

Impact Analysis of Right-Hand Side Variations

约束条件右端项向量 $b$ 代表系统拥有的资源上限。当 $b$ 变化为 $b + \Delta b $ 时，因为目标函数系数和约束矩阵 $A$ 未变，所有非基变量的检验数 $\Delta_j $ 保持不变，即最优性（对偶可行性）天然维持。

代数上的核心于是变为检验原始问题的可行性，即新的基变量取值必须保持非负：

$$ x_B' = B^{-1} (b + \Delta b) = B^{-1} b + B^{-1} \Delta b \ge 0 $$

通过解此不等式组，可以求出各个 $ \Delta b_i$ 的容许变化范围。

在几何上，改变右端项 $b_i $ 相当于将对应的约束超平面沿着其法向量方向进行平移，这会导致整个可行域多面体的膨胀或收缩。只要平移的幅度没有使得当前最优顶点所在的一组有效超平面交点越出可行域（即退化或被完全切除），构成最优解的基变量组合就不会改变。此分析的作用在于界定影子价格的有效区间，指出增加多少资源会真正遇到其他资源的瓶颈限制。

Testing and Adjustment for New Variables or Constraints

在实际业务中，系统常常会引入新的产品（新变量）或受到新的政策限制（新约束），我们需要算法在不重新计算的前提下快速调整。

当引入一个新的非基变量 $ x_\text{new}$，其伴随列向量为 $A_\text{new} $，利润系数为 $c_\text{new} $ 时。直接利用当前的最优基 $B$ 计算其检验数：

$$ \Delta_\text{new} = c_\text{new} - c_B^T B^{-1} A_\text{new} $$

如果 $ \Delta_\text{new} \le 0$，说明生产新产品无利可图，原最优解保持不变。如果 $ \Delta_\text{new} > 0$，则将该变量及其对应的列 $ B^{-1} A_\text{new}$ 加入到当前的单纯形表中，将其作为入基变量，继续执行常规的单纯形法迭代，直到达到新的最优解。

设新增约束为 $ a_\text{new}^T x \le b_\text{new}$。首先将当前的最优解 $ x^*$ 代入，检验其是否满足该限制。如果满足，则原解依然最优。 如果不满足，说明原顶点被新超平面切除了。此时将新约束加入单纯形表，引入一个非负松弛变量 $ x_s$，利用当前基变量的等式关系把新约束中的基变量替换掉，使其仅由非基变量表示。此时 $ x_s$ 将作为一个新的基变量，且其取值必为负数（因为原解违反约束）。此时单纯形表满足检验数全部非正（最优/对偶可行），但存在负基变量（原始不可行），算法强制使用对偶单纯形法，将 $ x_s$ 踢出基底，沿着新约束的边界滑动，修复可行性并寻找到新的最优解。

下面是一个 toy example。假设我们求解完毕一个生产问题，当前最优解为生产 2 单位桌子，3 单位椅子，即 $ x_1 = 2, x_2 = 3$，其他非基变量为 0，最优利润为 10。单纯形表的检验数行均已小于等于 0。

此时突发政策限制：环保要求两种产品的总产量不能超过 4，即引入新约束：

$$ x_1 + x_2 \le 4 $$

当前解被破坏，变为不可行。为了在表格中处理，我们加入松弛变量 $x_3 \ge 0 $ 变为等式：

$$ x_1 + x_2 + x_3 = 4 $$

在当前的代数系统中，我们需要把 $x_3 $ 作为新的基变量表达出来：

$$ x_3 = 4 - x_1 - x_2 $$

由于当前 $x_1=2, x_2=3 $，代入得到 $x_3 = -1 $。我们将这一行加入到单纯形表的底部。此时的单纯形表中，检验数依然保持最优（因为目标函数未变），但基变量 $x_3 = -1 < 0 $。 这正是对偶单纯形法的标准启动条件。算法指定取值为负的 $ x_3$ 出基，然后通过最小比值定理计算所有可能使得 $ x_3$ 变大的非基变量（即方程中系数为负的变量）作为入基变量。经过一次特定的转轴操作，在不破坏利润最大化方向的前提下，将迭代点拉回 $x_1 + x_2 = 4 $ 的新边界上，从而得到受环保约束下的新最优解，而无需从原点重新用大 M 法起步。

Polynomial-Time Algorithms and Interior-Point Methods

Khachiyan Ellipsoid Method

椭球法通过构造一个包含最优化问题可行域的椭球序列 $E_k$ 进行迭代。在每一步中，算法检查当前椭球的中心点 $x_k$ 是否满足所有约束。如果中心点违背了某个约束 $a_i^T x \le b_i$，则利用穿过该中心点且平行于约束边界的超平面将椭球切半，并构造一个新的、体积更小的椭球 $E_{k+1}$ 来将其中的可行半椭球完全包围。新椭球的体积严格以小于 1 的比例常数递减。

椭球法在几何上可以看作是高维多面体空间中的二分查找法。它通过不断收缩一个可以完全包裹目标区域的椭圆形容器，持续压缩搜索空间直到逼近最优解。这是历史上第一个从理论上严格证明线性规划问题可在多项式时间内求解的算法，单纯形法的复杂度是指数级。

Karush-Kuhn-Tucker (KKT) Conditions

KKT 条件是判断带约束非线性优化问题解是否为最优解的一阶必要条件。考虑如下标准形式的一般优化问题：

$$ \min f(x) \\ \text{s.t.} g_i (x) \le 0, \quad i = 1, ..., m , h_j (x) = 0, \quad j = 1, ..., p $$

如果在局部极小值点 $x^*$ 处满足特定的约束规范（如线性独立约束规范 LICQ），则必定存在拉格朗日乘子向量 $\lambda$ 和 $\mu$，使得以下四组条件严格成立：

平稳性 (Stationarity)：目标函数梯度与约束梯度的力矩平衡。

$$ \nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i (x^*) + \sum_{j=1}^p \mu_j \nabla h_j (x^*) = 0 $$

原始可行性 (Primal Feasibility)：解必须落在原规定的多面体或曲面边界内。

$$ g_i (x^*) \le 0 \\ h_j (x^*) = 0 $$

对偶可行性 (Dual Feasibility)：不等式约束的惩罚方向必须阻碍目标值进一步下降。

$$ \lambda_i \ge 0 $$

互补松弛性 (Complementary Slackness)：只有起作用的边界（紧约束）才能产生非零的支撑力。

$$ \lambda_i g_i (x^*) = 0 $$

在几何上，KKT 条件刻画了一种受力平衡状态。如果你站在可行域边界的最优点上，目标函数的负梯度方向（即让你收益继续变好的下坡方向）必然指向可行域的外部。此时，这个向外的力完全被那些卡住你的边界（紧约束）所提供的法向反作用力（即约束的梯度，乘以非负的权重 $\lambda_i$）所抵消。

KKT 条件将古典的拉格朗日乘子法从纯等式系统成功跨越到了不等式系统。它不仅是凸优化中判定全局最优解的充分必要条件，更是推导强对偶理论、构建支持向量机 (SVM) 分类面，以及设计所有现代原始-对偶内点法（内点法的核心即为对方程组中的互补松弛条件进行 $\mu$ 扰动）的数学基石。

Affine Scaling Method and Barrier Function Method

仿射缩放法：考虑标准形式线性规划 $\min c^T x$，满足约束 $A x = b$ 且 $x \ge 0$。给定严格满足 $x_k > 0$ 的当前内点，构造对角缩放矩阵 $X_k = \text{diag}(x_k)$。通过变量代换 $x = X_k \tilde{x}$，将当前迭代点映射为变换空间中的全 1 向量 $\tilde{x}_k = e$。

在此变换空间中，点到各个非负边界的距离被均匀拉齐，原问题等价于在等式约束 $A X_k \tilde{x} = b$ 下最小化 $(X_k c)^T \tilde{x}$。在该空间中沿着目标函数梯度的投影方向进行最速下降，投影矩阵为 $P = I - X_k A^T (A X_k^2 A^T)^{-1} A X_k$。映射回原空间后，实际的搜索方向 $d_k$ 为：

$$ d_k = - X_k^2 (c - A^T y) $$

其中 $y = (A X_k^2 A^T)^{-1} A X_k^2 c$ 为对偶变量的估计值。迭代更新公式为 $x_{k+1} = x_k + \alpha d_k$，其中步长 $\alpha$ 的选择需严格保证迭代点不越出边界，即 $x_{k+1} > 0$。

障碍函数法：通过在目标函数中引入一个当迭代点靠近可行域边界时趋于无穷大的惩罚项，将带不等式约束的优化转化为一系列仅带等式约束的子问题。对于标准形式线性规划，采用对数障碍函数，将其转化为求解如下惩罚问题：

$$ \min B(x, \mu) = c^T x - \mu \sum_{j=1}^n \log(x_j) \\ \text{s.t.} A x = b $$

其中 $\mu > 0$ 为控制惩罚强度的障碍参数。利用拉格朗日乘子法求解该问题，其最优性条件（即 KKT 条件）可导出如下非线性方程组：

$$ A x = b \\ A^T y + s = c \\ X S e = \mu e $$

其中 $X = \text{diag}(x)$，$S = \text{diag}(s)$ 分别为原始变量和对偶松弛变量构成的对角矩阵，$e$ 为全 1 向量。方程组的第三式正是被扰动的互补松弛条件。随着障碍参数 $\mu$ 连续趋于 0，该方程组的解轨迹严格定义了一条悬浮于可行域内部、连接多面体解析中心与最优极点的中心路径。

仿射缩放法在几何上相当于给空间进行透视变换，把当前点附近的狭窄角落重塑为宽敞的中心，使得算法可以自由地向最优解方向迈出巨大步长而不至于撞向边界。障碍函数法则像是在多面体可行域的内壁上施加了排斥力场，强制搜索轨迹始终保持在多面体安全的内部深处，避免在表面折线上指数级游走。

Path Following and Central Path

中心路径的严谨数学定义建立在对数障碍问题的 KKT 最优性条件之上。考虑带有惩罚参数 $\mu > 0$ 的原始对数障碍问题：

$$ \min c^T x - \mu \sum_{j=1}^n \log(x_j) $$

$$ \text{s.t.} A x = b $$

构造拉格朗日函数 $L(x, y) = c^T x - \mu \sum \log(x_j) - y^T (A x - b)$。根据一阶最优性条件，对 $x$ 求偏导并令其为零，可得：

$$ c - \mu X^{-1} e - A^T y = 0 $$

其中 $X = \text{diag}(x)$ 且 $e$ 为全 1 向量。若我们定义对偶松弛变量向量为 $s = \mu X^{-1} e$，将其等价变形为 $X S e = \mu e$（其中 $S = \text{diag}(s)$），那么上述条件可与原始-对偶可行性条件共同重写为如下的扰动 KKT 系统：

$$ A x = b , x > 0 $$

$$ A^T y + s = c , s > 0 $$

$$ X S e = \mu e $$

对于任意确定的障碍参数 $\mu > 0$，只要原问题与对偶问题的内部非空，该非线性方程组就存在唯一确定的解 $(x^*(\mu), y^*(\mu), s^*(\mu))$。随着 $\mu$ 在 $(0, +\infty)$ 内连续变化，这些解在多面体内部勾勒出一条连续平滑的曲线，即中心路径。

在中心路径上，原问题目标值与对偶问题目标值之间的对偶间隙可以通过互补松弛计算：

$$ c^T x - b^T y = x^T s = e^T X S e = n \mu $$

其中 $n$ 为变量的维度。这一数学性质极为关键，它表明在中心路径上，对偶间隙严格等于 $n \mu$。随着 $\mu$ 连续趋于 0，对偶间隙也以绝对线性的速率收敛于 0，严格保证了路径的极点必定是原问题的全局最优解。

几何直观：多面体的中心路径是一条悬浮在可行域深处、避开所有锋利棱角的平滑流线。当 $\mu \to +\infty$ 时，目标函数的权重被无穷大的惩罚项完全掩盖，路径的起点位于多面体的解析中心（即远离所有边界的绝对几何中心）；当 $\mu \to 0$ 时，惩罚项消失，路径的终点直指最优极点。路径追踪算法的作用在于，它不再基于多面体表面的局部梯度盲目前进，而是以这条全局最优的中心路径为导航参考线，使用牛顿法不断将迭代点拉回路径附近，稳妥且极为快速地顺流直下抵达最优解。

Potential Function Reduction Method

势函数缩减法：构造一个综合评估目标函数下降进度与点离边界安全距离的非线性势函数 $ \Phi(x, s)$。典型的原始-对偶势函数结构为：

$$ q \log(x^T s) - \sum \log(x_i s_i) $$

其中 $ q > n$ 为超参数。算法在每次迭代中寻找一个代数搜索方向，使得该势函数能够保证实现一个常数级别的下降量。

势函数可以被视作衡量当前系统势能的综合高度。公式中的第一项敦促算法尽快降低目标值间隙以逼近最优，第二项则警告算法必须时刻拉开与边界的距离以保持中心度。此方法在代数上为内点法的多项式时间复杂度提供了严密的分析框架，且在实现中赋予了算法选择巨大自由度。

Newton’s Method Applications

原始-对偶内点法直接从线性规划的 KKT 最优性条件出发，将其中的互补松弛条件替换为参数化的中心路径条件 $ X S e = \mu e$。算法将所有约束视为一个非线性方程组，并使用牛顿法对其进行一阶泰勒展开，求解如下线性方程组以获得迭代方向 $(\Delta x, \Delta y, \Delta s) $：

$$ A \Delta x = 0 \\ A^T \Delta y + \Delta s = 0 \\ S \Delta x + X \Delta s = - X S e + \sigma \mu e $$

其中 $ \sigma \in [0, 1]$ 为控制向心程度的中心化因子。

几何直观：在高维度的空间中精确且非线性地沿着弯曲的中心路径前进在计算上是极其困难的。牛顿法的应用在代数上将复杂的非线性寻优操作化解为求解一系列简单的线性矩阵方程组；在几何上，它不断使用二次曲面抛物面来局部拟合当前的非线性地形。通过将原始空间与对偶空间结合在一起对称地求解，该方法达成了极其惊人的迭代收敛效率，构成了当今所有大规模商业优化求解器底层的核心算法框架。

Large Scale Decomposition

Column Generation and Cutting Stock

列生成技术的本质是线性规划中单纯形法在变量维度极高场景下的动态实现机制。在大规模线性规划问题中，当变量总数（即约束矩阵的列数）远大于约束行数，且完整显式构造约束矩阵在计算存储或时间上不可行时，列生成算法基于Dantzig-Wolfe分解原理，不维护完整的约束矩阵，而是从一个包含少量可行变量（列）的初始可行基出发，在每次迭代中通过计算非基变量的检验数识别能够改善目标函数的变量，仅动态生成并加入这些具有负检验数（针对最小化问题）的列，直至不存在可改善目标的非基变量为止。

在经典的一维切割问题（Cutting Stock Problem）中，问题可被数学化描述为：给定长度为 $L$ 的标准原纸卷，以及 $m$ 种客户需求的短纸卷，其长度分别为 $l_1, l_2, \dots, l_m$，对应需求数量 $d_1, d_2, \dots, d_m$，目标是最小化消耗的原纸卷总数。此处，每一种合法的“切割模式”被定义为一个非负整数向量 $\mathbf{a}_j = (a_{1j}, a_{2j}, \dots, a_{m j})^T $，其中 $a_{i j}$ 表示第 $j$ 种模式下切割出的第 $i$ 种短纸卷的数量，且满足约束 $\sum_{i=1}^m a_{i j} l_i \le L$。

由于潜在的切割模式数量随需求种类 $m$ 呈指数级增长，直接枚举所有模式并构造完整线性规划模型不可行，因此列生成算法仅在主问题中保留少数初始可行切割模式，将主问题求解为线性规划松弛问题后得到对偶变量 $\mathbf{y} = (y_1, y_2, \dots, y_m)^T$，进而将寻找新的、能进一步节省原材的切割模式的任务转化为一个以对偶变量 $y_i$ 为价值系数的背包问题： $ \max \sum_{i=1}^m y_i a_i \\ \text{s.t.} \sum_{i=1}^m a_i l_i \le L, a_i \in \mathbb{N} $若该背包问题的最优目标值大于1，则对应切割模式的检验数为负，需将其加入主问题继续迭代；若最优目标值不大于1，则无更优模式，迭代终止。

MP, RMP and Pricing Problem

主问题 (Master Problem, MP) 是包含了所有潜在指数级变量的完整线性规划模型。由于直接求解 MP 是不可行的，算法构造了限制主问题 (Restricted Master Problem, RMP)。

限制主问题仅仅包含所有潜在变量的一个极小的子集。算法首先求解 RMP，得到当前受限状态下的最优原始解以及对应的对偶变量（影子价格）向量 $y$。

子问题（Pricing Problem / Oracle)，负责回答一个代数问题：在所有尚未被引入 RMP 的变量中，是否存在检验数为负（以最小化问题为例）的列？子问题的目标函数通常被设定为最小化非基变量的检验数：

$$ \min \Delta_j = c_j - y^T A_j $$

如果子问题求得的最优目标值 $\Delta_j < 0$，说明找到了一个有利可图的新列 $A_j$，将其加入 RMP 并重新求解；如果子问题的最优目标值 $\Delta_j \ge 0$，则数学上严格证明了当前 RMP 的最优解已经是全局完整 MP 的最优解，算法终止。这套机制在几何上相当于按需动态生成多面体的高维边界。

Dantzig-Wolfe Decomposition

Dantzig-Wolfe 分解法专门用于处理具有块对角结构并伴有少数耦合约束的大规模线性规划。假设系统包含若干个独立的子系统（块），但它们需要共享少数几种全局资源。

数学表示为：最小化 $c_1^T x_1 + c_2^T x_2$，满足全局耦合约束 $A_1 x_1 + A_2 x_2 = b$，且各个子系统满足局部约束 $x_1 \in P_1, x_2 \in P_2$。

利用 Minkowski-Weyl 定理，将独立的局部多面体 $P_1, P_2$ 用其极点（和极射线）的凸组合显式表示，代入全局耦合约束中。此时，原问题被彻底转化为一个以极点的权重为变量的主问题。由于极点数量庞大，算法在此层套用列生成技术：主问题分配全局资源并给出影子价格，各个子问题（相互独立，可并行求解）利用这些价格在其局部多面体 $P_i$ 内寻找最优极点生成新列。

经济直观：企业总部（主问题）并不微观干预分公司的内部运作，而是通过发布内部资源价格（对偶乘子）来引导分公司。各分公司（子问题）根据该价格制定局部最优的生产方案（极点）并上报总部，总部再根据所有上报方案调配最优的权重组合。

Benders Decomposition

如果说 Dantzig-Wolfe 分解针对的是“变量多、约束独立”的场景，那么 Benders 分解则是针对“包含复杂变量（如整数变量）或具有两阶段决策结构”的场景。它通过投影法，将复杂变量（主变量 $x$）和连续变量（子变量 $y$）解耦。

考虑下述问题：

$$ \min c^T x + d^T y \\ \text{s.t.} A x + B y \ge b \\ x \in X, y \ge 0 $$

算法将主变量 $x$ 暂时固定为 $\overline{x}$，此时关于 $y$ 的问题变成了一个简单的线性规划（子问题）。求解子问题的对偶问题，如果对偶问题有界，说明固定 $x$ 的方案是可行的，并返回一个极点乘子，为主问题生成一个最优性割 (“OPT"imality Cut)，迫使主问题逼近真实目标值；如果对偶问题无界，说明固定 $x$ 导致原约束矛盾，子问题返回一个极射线乘子，为主问题生成一个可行性割 (Feasibility Cut)，永远切除这个非法的 $x$。

主问题在其可行域内仅考虑 $x$ 并最小化目标函数的下界，通过不断收集子问题返回的割平面，主问题的可行域逐渐收缩，目标下界不断上升，直到与子问题求得的上界汇合。

Benders 分解在几何上是在主变量的低维空间中，用一组动态生成的超平面从下方“托起”整个目标函数的可行区域。它是解决混合整数规划 (MILP)、Min-max 鲁棒优化以及双层规划问题的最强大的精确算法框架之一。

Integer Programming and Combinatorial Optimization

Linear Integer Programming Basics

ILP and MILP

当线性规划问题中的部分决策变量被严格限制为必须取整数值时，构成混合整数规划 (MILP)。其标准代数形式为：

$$ \max c^T x + d^T y \\ \text{s.t.} A x + B y \le b \\ x \in \mathbb{Z}_+^n, y \in \mathbb{R}_+^p $$

若 $p=0$，即所有决策变量均被严格限制为整数时，问题退化为纯线性整数规划 (ILP)。

整数约束破坏了可行域的连续性与凸性，将其变为了多面体内部离散分布的格点集合。引入整数变量使得优化模型能够精确刻画不可分割的物理量（如机器台数、人员个数）以及逻辑层面的“是与否”互斥决策（利用 0-1 变量）。

Relaxed Problem and Totally Unimodular Matrix

通过直接去除原整数规划问题中的整数约束 $x \in \mathbb{Z}_+^n$，将其放宽为连续的实数约束 $x \in \mathbb{R}_+^n$，所得到的新线性规划问题称为原问题的连续松弛问题。

全幺模矩阵 (TUM) ：如果一个矩阵 A 的任意方阵子矩阵的行列式的值必然属于 ${-1, 0, 1}$，则称矩阵 A 为全幺模矩阵。

核心定理：如果约束矩阵 A 是全幺模矩阵，且右端项向量 b 的所有分量均为整数，那么多面体 $P = {x : A x \le b, x \ge 0}$ 的所有基本可行解的坐标必全是整数。

松弛问题为最大化整数规划提供了一个易于计算的理论上界。对于具有 TUM 结构的问题（如二分图匹配、最大流等网络流问题），我们可以完全无视其 NP 难的整数属性，直接采用多项式时间的单纯形法求解并获得最优整数解。

Exact Solution Algorithm Frameworks

Branch and Bound and Search Strategies

分支定界法是求解整数规划的隐式枚举树搜索精确算法。其步骤为：首先求解当前节点的松弛问题。如果得到的松弛最优解 $x^*$ 中某个本应为整数的变量 $x_i$ 有小数部分（设 $x^*=v$），则以该变量作为分支点。构造两个互斥的子约束加入到原问题中：

$$ x_i \le \lfloor v \rfloor \quad \text{与} \quad x_i \ge \lceil(v) $$

这两个子约束将原可行域一分为二，生成两个子节点。同时，算法维护一个全局的已知最好整数解作为下界（对于最大化问题）。当某个节点的松弛最优目标值小于等于该下界，或者该节点无解，又或者该节点求得了整数解时，触发定界操作，直接剪除该分支及其所有子代。

分支搜索策略：深度优先搜索 (DFS) 旨在快速发现可行的整数解，从而尽早建立高质量的全局下界用于后续大规模剪枝；最佳优先搜索 (Best-First) 则总是选择当前松弛目标值最大的节点进行分支，旨在以最少的探索节点数提供全局最优性证明。

分支操作相当于使用平行于坐标轴的超平面，将包含非整数最优解的连续可行域空间分成两部分，以此强调整数约束。

Cutting Plane Method and Separation Oracle

割平面法：求解松弛问题得到最优解 $x^*$ 后，寻找一个满足所有整数分量满足、但小数分量不满足的线性不等式：

$$ \alpha^T x \le \beta $$

将此不等式作为割平面加入到当前的线性规划模型中并重新求解。最经典的构造方法为 Gomory 分数割，对于单纯形表中产生小数最优值的某一行 $x_i + \sum a_{i j} x_j = b_i$，其割平面被严格构造为：

$$ \sum (a_{i j} - \lfloor a_{i j} \rfloor) x_j \ge b_i - \lfloor b_i \rfloor $$

分离 Oracle ：给定一个小数解 $x^*$，分离 Oracle 是一个特定的黑盒算法例程，它要么证明 $x^*$ 属于所有整数可行解的凸包内部，要么显式地输出一个能够将 $x^*$ 与该凸包严格分离的有效割平面。

几何直观：不同于分支定界将整个空间切开，割平面法像是用一把刻刀，把连续多面体上那些不包含任何整数点的尖角一片一片削去。随着割平面的不断加入，外围的连续多面体会不断收缩，其边界最终会完美地紧贴在内部整数点构成的最紧凑凸包表面上。

Dynamic Programming

基于 Bellman 最优性原理，将多阶段决策过程转化为一系列相互重叠的子问题。定义离散时间步 $t$，系统状态变量 $s_t$，决策变量 $x_t$，以及状态转移方程 $s_{t+1} = f(s_t, x_t)$。其核心是构造状态值函数 $V_t (s_t)$，并建立向后递推的 Bellman 方程：

$$ V_t (s_t) = \max_{x_t} { R(s_t, x_t) + V_{t+1}(f(s_t, x_t)) } $$

其中 $R(s_t, x_t)$ 为当前阶段采取特定决策的即期回报。

如果把所有可能的决策序列看作一张庞大的树状网络，动态规划通过记忆化状态值，将庞大的无向树折叠成有向无环图 (DAG),从而将原问题指数级的时间复杂度变成了多项式级，是求解背包问题、网络最短路以及各类组合优化序列问题的强力方法。

Greedy Strategy and Matroid Theory

Independence System and Rank Function

设 E 是一个有限的基础元素集合，而 $\mathcal{I}$ 是 E 的某些子集构成的族。如果二元组 $(E, \mathcal{I})$ 满足以下两个公理，则称其为一个独立系统： 第一，空集属于 $\mathcal{I}$，即 $\emptyset \in \mathcal{I}$。 第二，遗传性 (Hereditary property)，即如果 $A \in \mathcal{I}$ 并且 $B \subset A$，那么必然有 $B \in \mathcal{I}$。

在独立系统中，$\mathcal{I}$ 中的元素被称为独立集。对于 E 的任意子集 A，其秩函数 $r(A)$ 的数学定义为该子集中包含的最大独立集的基数：

$$ r(A) = \max { |X| : X \subset A, X \in \mathcal{I} } $$

独立系统是对线性代数中线性无关向量组，以及图论中无环边集（森林）的抽象概括。它提取了“局部不相关的组合依然不相关”这一逻辑。秩函数则度量了某个集合内部所包含的最高维度的有效信息量或结构容量，为后续探讨算法的近似性能提供了核心的代数工具。

Matroids and Dual Systems

拟阵：如果一个独立系统 $M = (E, \mathcal{I})$ 额外满足交换公理 (Exchange property)，则称其为一个拟阵。交换公理表述为：对于任意两个独立集 $A, B \in \mathcal{I}$，如果 $|A| > |B|$，那么必定存在一个元素 $x \in A \\ B$，使得：

$$ B \cup {x} \in \mathcal{I} $$

等价地，拟阵的特征性质也可以通过其秩函数的次模性 (Submodularity) 来定义，即对任意子集 A 和 B：

$$ r(A \cup B) + r(A \cap B) \le r(A) + r(B) $$

对偶独立系统：给定拟阵 $M = (E, \mathcal{I})$，其所有的极大独立集构成基族 $\mathcal{B}$。定义一个新的系统，其基族为原系统基的补集 $\mathcal{B}^* = {E \\ B : B \in \mathcal{B}}$，由该基族向下封闭生成的独立系统 $M^*$ 称为 M 的对偶拟阵。其对偶秩函数 $r^*$ 满足：

$$ r^*(A) = |A| + r(E \\ A) - r(E) $$

拟阵是组合优化中极其优美的结构，它描述了那些“元素间不存在长程复杂耦合”的完美系统。次模性反映了边际效益递减的经济学原理。对偶拟阵理论的作用极大，它允许我们将一个挑选元素构造结构的优化问题，转化为一个从全集中剔除多余元素的对偶问题（例如图的生成树与割集），从而直接复用现有的算法结论。

Best-In Algorithm and Approximation

贪心算法：给定独立系统 $(E, \mathcal{I})$ 和非负权重函数 $w: E \to \mathbb{R}_+$。首先将 E 中的元素按权重降序排列，使得 $w(e_1) \ge w(e_2) \ge ... \ge w(e_n)$。初始化独立集 $S = \emptyset$。接着从 $i = 1$ 到 n 遍历，如果 $S \cup {e_i} \in \mathcal{I}$，则将 $e_i$ 加入 S，否则跳过。最终输出极大独立集 S。

在一般的独立系统中，Best-In 算法无法保证得到绝对最优解。其近似界限由系统的秩商 (Rank Quotient) q 严格决定。秩商定义为：

$$ q = \min_{A \subset E} ( \min_{X} { |X| : X \text{是 A 中的极大独立集} } ) / ( \max_{Y} { |Y| : Y \text{是 A 中的极大独立集} } ) $$

可以证明，Best-In 算法求得的贪心解 $S_{\text{greedy}}$ 与全局最优解 $S_{\operatorname{OPT}}$ 的总权重始终满足：

$$ w(S_{\mathrm{greedy}}) \ge q\,w(S_{\mathrm{OPT}}) $$

Best-In 是最符合人类直觉的自下而上的“目光短浅”策略。在任意复杂的离散结构中，计算秩商就能直接宣判贪心算法的理论最劣性能底线。更为深刻的是，当且仅当系统是拟阵时，$q = 1$，这构成了著名的 Edmonds 定理：拟阵是使得贪心算法必定能够求得全局最大权独立集的充分必要结构。

Worst-Out Algorithm and Optimality

最劣剔除算法：将基础集合 E 中的元素按权重升序排列，使得 $w(e_1) \le w(e_2) \le ... \le w(e_n)$。初始化候选集 $S = E$。从 $i = 1$ 到 $n$ 遍历，如果从 S 中剔除 $e_i$ 后，剩余集合 $S \\ {e_i}$ 的秩等于 E 的总秩（即剔除该元素不破坏系统的最大跨度），则更新 $S = S \\ {e_i}$，否则保留 $e_i$。算法最终输出一个权值最大的基。

在拟阵结构中，最劣剔除算法的最优性理论分析依赖于对偶拟阵。对原拟阵 M 执行寻找最大权基的 Worst-Out 算法，在代数执行逻辑上，等价于对其对偶拟阵 $M^*$ 执行寻找最大权独立集的 Best-In 算法。

由于拟阵的对偶结构依然是拟阵，Worst-Out 在拟阵上的完美等价性不仅再次证明了其能达到全局最优，更揭示了组合优化中自下而上构造与自上而下破坏的对称性。

Approximation Algorithm Design and Analysis

Theoretical Foundations and Performance Evaluation

Approximation Ratio and Integrality Gap

近似比：对于一个最优化问题，设 $I$ 为问题的任意一个输入实例，$\operatorname{OPT}(I)$ 为该实例的全局最优目标函数值，而 $A(I)$ 为多项式时间近似算法 A 求解该实例得到的目标函数值。算法 A 的近似比 $\rho$ 定义为能够约束这两个值比值的最劣上界。为了统一表达形式，通常要求 $\rho \ge 1$：

$$ \max { (A(I)) / (\operatorname{OPT}(I)), (\operatorname{OPT}(I)) / (A(I)) } \le \rho $$

整数间隙：设一个整数规划问题的最优目标值为 $\operatorname{OPT}_\text{IP}$，其对应的线性规划连续松弛问题的最优目标值为 $\operatorname{OPT}_\text{LP}$。整数间隙定义为在所有可能的问题实例中，这两个目标值比值的最劣极限。对于最小化问题，其定义为：

$$ \text{Gap} = sup_I (\operatorname{OPT}_\text{IP}(I)) / (\operatorname{OPT}_\text{LP}(I)) $$

近似比度量了在最坏情况下，近似算法给出的解距离完美的全局最优解有多远，它为启发式算法提供了理论担保。而整数间隙则刻画了离散整数多面体与其连续松弛多面体边界之间的固有几何距离。

Polynomial-Time Approximation Schemes (PTAS, EPTAS, FPTAS, APX)

在计算复杂性理论中，根据逼近最优解的能力与时间开销的权衡，近似算法被划分为严格的代数层级框架：

PTAS (Polynomial-Time Approximation Scheme，多项式时间近似方案) ：对于任意给定的误差参数 $\epsilon > 0$，算法能够给出一个 $(1+\epsilon)$-近似解，并且该算法的运行时间是问题输入规模 $n$ 的多项式。其时间复杂度的指数可以依赖于误差参数，例如 $O(n^{1/\epsilon})$。

EPTAS (Efficient PTAS，高效多项式时间近似方案) ：在 PTAS 的基础上，进一步要求运行时间多项式的阶数绝对不能依赖于误差参数 $\epsilon$。其时间复杂度形式被严格限制为独立的分离形式 $O(f(1/\epsilon) n^c)$，其中 c 是绝对常数。

FPTAS (Fully PTAS，完全多项式时间近似方案) 的数学定义：逼近理论的最高层级，要求算法的运行时间不仅是输入规模 $n$ 的多项式，同时还必须是 $1/\epsilon$ 的多项式。其时间复杂度形式例如 $O((1/\epsilon)^2 n^3)$。

APX (Approximable，可近似类) 的数学定义：指代所有存在常数近似比（即 $\rho = c > 1$ 的绝对常数）的多项式时间算法的最优化问题集合。如果在 APX 中存在被称为 APX-hard 的组合优化问题，则除非 P=NP 成立，否则该问题绝对不存在 PTAS。

几何直观与作用：这一分类体系建立了衡量 NP 难问题可近似程度的绝对坐标系。PTAS 意味着我们在理论上可以无限逼近多面体的最优极点；FPTAS 则是近似算法领域的圣杯，它表明我们只需付出极其轻微的代数计算代价，就能换取几何空间的任意高精度逼近。相反，APX-hard 理论则划定了一道严格的数学鸿沟，它证明了在某些复杂的组合结构（如顶点覆盖问题）中，妄图无限逼近最优边界的行为在多项式时间内是根本不可能实现的。

LP-Based Approximation

Relax-Solve-Round Framework

松弛-求解-舍入框架：考虑一个最小化整数规划问题 $\min { c^T x : x \in \mathcal{X}, x \in \mathbb{Z}^n }$，其全局最优解的目标值为 $\operatorname{OPT}_\text{IP}$。首先，将其整数约束放宽为连续实数约束，构造线性规划松弛问题 $\min { c^T x : x \in \mathcal{X}, x \in \mathbb{R}^n }$。由于约束条件的放宽，松弛问题的最优目标值 $\operatorname{OPT}_\text{LP}$ 必然满足：

$$ \operatorname{OPT}_\text{LP} \le \operatorname{OPT}_\text{IP} $$

使用多项式时间算法求解松弛问题得到小数最优解 $x^*$ 后，设计一个算法将 $x^*$ 舍入映射为一个满足原整数约束的可行解 $x^H$。如果能严格证明对于任意实例都有 $c^T x^H \le \rho \operatorname{OPT}_\text{LP}$，那么由于 $\operatorname{OPT}_\text{LP} \le \operatorname{OPT}_\text{IP}$，该算法必然是一个近似比为 $\rho$ 的近似算法。

此框架将艰难的离散组合寻优转化为了两步走战略。第一步先在连续的多面体空间中找到绝对下界（最优小数极点），第二步基于这个极点的位置信息，有策略地将其投影或就近移动到周围的有效整数格点上。它是设计高性能近似算法的标准工业流水线。

Knapsack and Vertex Cover Rounding

设图 $G=(V, E)$，点权为 $w_v$。其 LP 松弛模型为最小化 $\sum w_v x_v$，且对于每一条边 $(u, v) \in E$，满足 $x_u + x_v \ge 1$，其中 $x_v \ge 0$。求得最优小数解 $x^*$ 后，采用如下确定性舍入规则构造整数解 $\hat{x}$：

$$ \hat{x}_v = 1 \quad \text{if} \quad x_v^* \ge 1/2 \quad \text{else} \quad 0 $$

由于对于任意边 $(u, v)$ 有 $x_u^* + x_v^* \ge 1$，故两者中必有一个大于等于 $1/2$，从而 $\hat{x}_u + \hat{x}_v \ge 1$，严格保证了整数解的可行性。其目标值满足：

$$ \sum w_v \hat{x}_v \le \sum w_v (2 x_v^*) = 2 \operatorname{OPT}_\text{LP} \le 2 \operatorname{OPT}_\text{IP} $$

背包问题的 LP 舍入则利用贪心松弛解：将物品按性价比降序填入，直到某物品无法完整装入而进行边界分割。取该分割解的纯整数部分与被分割物品本身的价值中较大的一个，即可严格证明得到一个 2-近似算法。

确定性舍入相当于在多面体空间中划定了一个硬性的几何阈值超平面（如 $x = 0.5$），将小数极点强行截断至最近的整数边界。这种方法直接利用了代数不等式的放大性质，给出了极其简洁优雅的 2-近似数学证明。

UPMS and Pseudo-forest Analysis

无关平行机器调度 (UPMS) 问题：需要将 $n$ 个工件分配给 $m$ 台不相关的机器，工件 $j$ 在机器 $i$ 上的处理时间为 $p_{i j}$，目标是最小化最大完工时间 C。其 LP 松弛问题包含指派约束 $\sum_i x_{i j} = 1$ 与负载约束 $\sum_j p_{i j} x_{i j} \le C$。

伪森林：在这个二分图结构的 LP 模型中，任意一个基本可行解所对应的非零变量所构成的支撑图，必然是一个伪森林 (Pseudo-forest)。即该二分图中每一个连通分支最多只包含一个环。

利用这一性质，我们可以将工件分为两类：树叶节点对应只被唯一指派到一台机器上的工件，它们天然是整数，直接保留；而处于环或路径上的工件，每台机器最多只会分担一个这样的小数工件。通过特定的二分匹配将其进行舍入，可以严格证明每台机器的负载最多增加一个工件的最大处理时间，从而得到一个 2-近似算法。

几何直观与作用：伪森林分析是极其强大的多面体结构剖析技术。它表明，即便我们在高维空间中进行连续松弛，极点解的结构依然极其稀疏且具有极强的图论拓扑规律。大部分变量天然就是整数，只有极少数位于环上的变量处于纠缠的小数状态，极大降低了舍入的难度与最劣误差。

Primal-Dual for Set Cover and UFL

原始对偶近似算法不直接求解耗时的线性规划松弛，而是同时维护原始问题的不可行整数解 $x$ 与对偶问题的可行解 $y$。利用弱对偶定理，通过不断提升对偶变量 $y$，直到某个对偶约束达到等式（变为紧约束），此时将对应的原始变量 $x$ 设为 1（如选中某个集合或开设某个设施）。

在集合覆盖问题 (Set Cover) 中，提升未覆盖元素 $e$ 的对偶变量 $y_e$，直到某个集合 S 的代价 $c_S$ 被填满，即 $\sum_{e \in S} y_e = c_S$。此时选中集合 S，并将其中包含的元素标记为已覆盖。如果所有元素最多属于 $f$ 个集合，该算法给出严格的 $f$-近似。

在无容量限制设施选址问题 (UFL) 中，算法将所有未连接客户端的需求作为对偶变量同时均匀提升。当一个客户端累积的对偶资金足以支付到某设施的连接成本时，便将多余资金贡献给该设施的开设成本；当某设施累积的贡献足以完全覆盖其开设成本时，将其开设。著名的 Jain-Vazirani 算法基于此机制结合特定的时序清洗步骤，给出了严格的 3-近似算法。

作用：原始对偶方法在经济学上相当于通过市场竞价机制自底向上地构建最优解。对偶变量就是客户的出价，约束的边界就是商品的成本天花板。它完全不需要在多面体内部进行任何浮点矩阵求解，而是纯粹在组合图论空间中模拟资金积累与支付的过程。这使得它比基于单纯形法或内点法的解法快上几个数量级，是组合优化中最深刻的纯组合近似技术。

Graph and Tree-Based Approximation Strategies

Steiner Tree Problem and Metric Steiner Tree

斯坦纳树问题：给定一个无向连通图 $G=(V, E)$，边权函数 $w: E \to \mathbb{R}_+$，以及一个必须被连通的终端节点子集 $T \subset V$。目标是寻找到一个包含所有终端节点 $T$ 的最小权重连通子图（必然是树）。集合 $V \\ T$ 中的节点被称为斯坦纳点，算法可以选择性地包含它们以降低总连通代价。

度量斯坦纳树：如果图 G 是完全图，且其边权严格满足三角不等式：对于任意节点 $u, v, k$，都有 $w(u, v) \le w(u, k) + w(k, v)$，则称该问题为度量斯坦纳树问题。

在几何上，这相当于用最便宜的造价把几个孤立的城市连入同一个公路网。如果直接连接城市太贵，我们可以在荒野中建立枢纽交汇点（斯坦纳点）来抄近路。度量化是一种极其强大的理论归约工具，通过计算图的最短路闭包，我们可以将任何一般的斯坦纳树问题转化为度量斯坦纳树，从而将研究重点聚焦于度量空间的纯几何性质上。

Metric TSP and Shortest Hamiltonian Path

度量旅行商问题 (Metric TSP)：在一个满足三角不等式的完全加权图中，寻找一条总权重最小的、且恰好访问每个顶点一次并最终回到起点的回路（即最小权 Hamilton 圈）。

最短 Hamilton 路问题：与 TSP 类似，但不要求最后从终点返回起点，即寻找一条具有最小权重的生成路径。

一般图的 TSP 问题在计算复杂性理论中是不可近似的（除非 P=NP）。但度量性质赋予了空间一个最基本的物理学法则：“绕路永远不会比直达更近”。这一几何属性构成了所有基于树的路由近似算法的绝对理论基石，使得我们可以利用最小生成树 (MST) 来严格界定最优巡回路线的理论下界。

MST-based Short-cutting Strategy

基于 MST 的截短/跳跃策略：设图的最小生成树为 T，最优 TSP 巡回路线为 OPT。首先，由于去掉 OPT 中的一条边即可得到一棵生成树，故必定有 $w(T) \le w(\operatorname{OPT})$。算法将 T 中的每一条边复制一份，构造出一个所有顶点度数均为偶数的多重图。在该多重图上寻找一条欧拉回路，随后沿着该回路遍历。当遇到曾经访问过的节点时，直接跳过该节点，沿着原图的边直达下一个未访问的节点，直至完成巡回。

想象你正沿着一棵树的树干和树枝边缘行走，当你走到尽头准备原路折返时，你发现旁边有另一根未探索的树枝。由于三角不等式的存在，你直接“凌空跳跃”过去（截短）的代价，绝对小于你老老实实原路退回再走过去的代价。因为复制整棵树的总权重为 $2 w(T)$，跳跃又只会使得路径变短，从而给出了一个极其优雅且严格的 2-近似算法。

Eulerian Circuit Construction and Fleury’s Algorithm

欧拉回路：一条包含图中所有边且每条边恰好出现一次的闭合游走。图存在欧拉回路的充分必要条件是图连通且所有顶点的度数均为偶数。

Fleury 算法：从任意顶点出发，每次贪心地选择一条与当前顶点相连的边进行遍历，并将其从图中删除。其强制规则是：除非别无选择，否则绝不走割边。

Christofides Algorithm

Christofides 算法（1.5-近似）：

• 第一步，计算原图的最小生成树 T。
• 第二步，提取 T 中所有度数为奇数的顶点集合 O。由图论握手定理可知，集合 O 的基数 $|O|$ 必然是偶数。
• 第三步，在由 O 导出的度量子图中，寻找一个最小权完美匹配 M。
• 第四步，将生成树 T 的边集与匹配 M 的边集进行多重图合并 $T \cup M$。此时图中所有顶点的度数均被强行修正为偶数。
• 第五步，提取欧拉回路并执行截短跳跃策略得到最终的 Hamilton 圈。

因为最优圈 $\operatorname{OPT}$ 在 O 上也构成了一条包含所有奇数点的路径，取其交替边即可将 $\operatorname{OPT}$ 拆分为两个完美匹配，故最小权完美匹配 M 的权重严格受界于 $w(M) \le 0.5 w(\operatorname{OPT})$。结合生成树的下界，算法总权重界定为：

$$ w(T \cup M) \le w(T) + w(M) \le 1.0 w(\operatorname{OPT}) + 0.5 w(\operatorname{OPT}) = 1.5 w(\operatorname{OPT}) $$

相比于简单粗暴地复制整棵树（耗资 1.0 OPT），Christofides 算法表现出了极高的精准度。它只针对那些奇数度节进行完美匹配。这一算法打破了长久以来的 2-近似屏障，其 1.5 的近似比在度量 TSP 领域保持了近半个世纪的最佳理论记录。

Fixed-endpoint Enumeration and Matching Adjustment Strategy

固定端点的匹配调整策略：考虑带有明确起点 s 和终点 t 的最短 Hamilton 路问题。一条合法的 s-t 路径要求 s 和 t 的度数必须为奇数，而所有内部节点的度数必须为偶数。若从最小生成树 T 出发，设 T 中的奇数度节点集为 O。为满足端点奇偶性约束，构造全新的目标匹配点集 $O'$，其为 O 与端点集的对称差：

$$ O' = O \Delta {s, t} = (O \cup {s, t}) \\ (O \cap {s, t}) $$

随后在 $O'$ 上寻找最小权完美匹配 M，并合并 $T \cup M$ 以修正全局奇偶性。

几何直观：如果将 TSP 回路视作一个闭合的橡胶圈，那么固定端点的路径就是一根两端暴露的绳子。匹配调整策略的代数对称差操作在拓扑结构上完美实现了这一目标：它故意避开或翻转两端点的修复逻辑，确保系统的内部节点全部被密封（偶数度），而两个指定的端点始终保持开放（奇数度）。这展示了 Christofides 框架在面对复杂拓扑边界条件时极强的代数拓展能力。

Bin Packing Approximation Theory

Absolute and Asymptotic Approximation Ratio

装箱问题是一个经典 NP-hard 问题。其目标是将一组大小给定的物品分配到数量不限、容量相同的箱子中，要求每个箱子内物品的总大小不超过箱子的容量，并且最小化所使用的箱子总数。

绝对近似比 (Absolute Approximation Ratio)：对于所有的输入实例 I，算法 A 使用的箱子数 $A(I)$ 与最优解 $\operatorname{OPT}(I)$ 严格满足：

$$ A(I) \le \rho \operatorname{OPT}(I) $$

渐近近似比 (Asymptotic Approximation Ratio) 的数学定义：对于装箱问题，由于离散碎片的组合特性，绝对界限往往过于苛刻。渐近近似比关注的是当最优箱子数趋于无穷大时的算法性能。如果在存在某个常数 c 的情况下满足：

$$ A(I) \le \rho^{\infty} \operatorname{OPT}(I) + c $$

则称 $\rho^{\infty}$ 为渐近近似比。

在装箱问题中，由于物理空间的不可分割性，即使是最完美的算法在边缘处理时也难免会浪费 1 到 2 个箱子的常数级空间。渐近近似比过滤掉了这些微小的常数加性扰动，真实且公允地刻画了算法在大规模工业实例（如集装箱装载、云计算资源分配）中的压缩效率。

Simple Heuristics (NF, FF, BF, WF, FFD)

简单在线与离线启发式算法：

• Next Fit (NF)：仅维护一个当前打开的箱子。遍历物品，若能放入则放入；若不能，则永久关闭该箱子并开启一个新箱子。其渐近近似比为 2。
• First Fit (FF)：维护所有已打开的箱子序列。遍历物品，将其放入第一个能容纳它的箱子中。仅当所有箱子都装不下时才开新箱。渐近近似比为 1.7。
• Best Fit (BF)：遍历所有箱子，将物品放入能够容纳它且剩余空间最小的箱子中（即最紧密拟合）。渐近近似比为 1.7。
• Worst Fit (WF)：将物品放入当前剩余空间最大的箱子中，旨在平衡负载，但在装箱最小化目标下表现通常最劣。
• First Fit Decreasing (FFD)：一种离线算法。首先将所有物品按体积大小降序排列，随后执行 FF 算法。其渐近近似比为 11/9（约 1.22）。

Amortization and Weight Function Proof Techniques

均摊分析与权重函数：在证明装箱算法（如 FFD）的近似比时，单纯基于体积的界定是极度松弛的（例如，5 个体积为 0.51 的物品由于冲突必须占用 5 个箱子，但其真实总体积仅为 2.55）。 权重函数技术通过构造一个非线性的映射函数 $W(x)$，对体积为 $x$ 的物品进行重新“经济定价”。证明的核心在于两步：首先，证明算法 A 开启的箱子数受限于总权重，即 $A(I) \le \sum W(x_i)$；其次，证明在任何合法的单箱最优装载配置中，其内部物品的总权重永远有一个硬性上界 $\alpha$，从而推出 $\sum W(x_i) \le \alpha \operatorname{OPT}(I)$。

权重函数相当于在代数上向那些“极其难装的尴尬尺寸”（例如大于 0.5 但略小于 1 的物品）征收了高昂的“空间惩罚税”。它量化了不同尺寸物品在组合几何空间中的相互排斥效应，是突破体积下界瓶颈、完成严密最劣性能分析的核心证明工具。

Harmonic Grouping and APTAS

由 Fernandez de la Vega 和 Lueker 提出的 APTAS 框架：对于任意给定的误差参数 $\epsilon > 0$，首先将体积小于 $\epsilon$ 的物品归为“小物品”暂不考虑。 调和分组技术：将剩余的“大物品”按大小排序，并均分为 K 组。对于每一组内的物品，将其体积强制向上舍入为其所在组的最大体积。此时，连续的物品体积被离散化为了仅有 K 种常数个不同尺寸的代理物品。 由于尺寸种类是常数，代理实例可以通过整数规划或动态规划在多项式时间内求得绝对最优解。最后，将小物品通过贪心策略填入剩余缝隙中。

其近似界限被严格证明为：

$$ A(I) \le (1 + \epsilon) \operatorname{OPT}(I) + O(1/\epsilon^2) $$

连续的几何尺寸是导致组合爆炸的罪魁祸首。调和分组相当于对物品进行了一次略显悲观但极度降维的“阶梯化”截断。通过轻微牺牲常数级的箱子空间（即公式中的加性常数），算法将 NP 难的无限状态空间直接坍缩为了可精确计算的有限状态空间，在理论上实现了对最优解的任意精度逼近。

Configuration LP and Karmarkar-Karp Algorithm

构型线性规划的数学模型：由 Gilmore 和 Gomory 提出。设 $T$ 为所有合法的单箱装载构型集合（即每种构型 $t$ 描述了一个箱子内部可以同时容纳各种不同尺寸物品的具体数量向量）。设决策变量 $x_t \ge 0$ 表示采用构型 $t$ 的箱子数量。 LP 松弛模型为：最小化 $\sum_{t \in T} x_t$，约束条件为所有构型提供的物品数量必须覆盖原始需求。

Karmarkar-Karp 算法：由于构型数量 T 呈指数级，算法采用延迟列生成技术 (Column Generation)，将寻找负检验数构型的子问题转化为一个背包问题，从而在多项式时间内解出 Configuration LP 的小数最优解。随后，结合一种极其精密的残差舍入技术，其最终使用的箱子数被证明为：

$$ A(I) \le \operatorname{OPT}(I) + O(\log^2 (\operatorname{OPT})) $$

Configuration LP 颠覆了“将物品分配给箱子”的传统视角，而是切换到了“为系统挑选预制模板”的宏观视角。这一公式中惊人的多项式对数级加性误差揭示了一个深邃的几何事实：装箱问题的构型多面体，其连续小数边界与离散整数顶点之间的缝隙（整数间隙 Integrality Gap）是极其微小的。Karmarkar-Karp 算法是装箱领域理论天花板级别的算法。

Online Algorithms

Models & Strategies

Competitive Ratio

在线算法的性能评估主要通过与离线最优解（OPT）比较来进行。假设 $A$ 是一个在线算法，对于任意输入序列 $\sigma$，记 $A(\sigma)$ 为算法 $A$ 产生的代价，$\operatorname{OPT}(\sigma)$ 为离线最优算法在知晓全局信息下的代价。如果存在常数 $c \ge 1$ 和 $\alpha$，使得对所有可能的输入序列 $\sigma$ 都满足：

$$ A(\sigma) \le c \cdot \operatorname{OPT}(\sigma) + \alpha $$

则称算法 $A$ 是 $c$-竞争的（$c$-competitive）。当 $\alpha = 0$ 时，称为严格 $c$-竞争。竞争比 $c$ 衡量了信息不完备对算法造成的理论最坏惩罚。

Online vs Offline

离线问题的本质是在已知完整输入序列 $\sigma = (r_1, r_2, ..., r_n)$ 的前提下，寻找全局最优策略 $x^*$ 以最小化目标函数 $\min_{x \in X} f(x, \sigma)$。 而在在线问题中，决策变量 $x_t$ 必须在仅知晓局部历史信息 $(r_1, r_2, ..., r_t)$ 的时刻 $t$ 立即、不可撤销地做出。目标转变为在不确定的演化过程中控制累积代价：

$$ \min \sum_{t=1}^n f_t (x_t, r_t) $$

这种时间维度上的信息不对称性，构成了在线算法竞争比的理论下界。

Doubling & Bidding

在面对未知目标值 $U$ 的在线搜索或竞拍问题时，倍增策略（Doubling Strategy）是控制最坏情况代价的核心数学工具。假设算法以序列 $B_i = 2^i$ $(i=0, 1, 2, ...)$ 递增搜索或竞拍阈值。当某次探测满足 $B_k \ge U$ 时算法停止。 该策略的累积代价为几何级数求和：

$$ \sum_{i=0}^k 2^i = 2^{k+1} - 1 $$

由于停止的前一步未能覆盖目标，必有 $2^{k-1} < U$，从而可推导出 $2^{k+1} < 4U$。因此，倍增策略在对 $U$ 毫无先验知识的情况下，将总代价严格界定在最优代价的 4 倍以内。

Ski Rental

滑雪板租赁问题是在线决策中止损机制的经典数学模型。设每日租赁费为 $r=1$，一次性购买费为 $B$。令滑雪总天数为未知的 $d$。 离线最优（OPT）代价：若 $d \ge B$，则第 1 天购买，代价为 $B$；若 $d < B$，则全程租赁，代价为 $d$。 在线算法的平衡策略设定为：前 $B-1$ 天选择租赁，若第 $B$ 天仍需滑雪则果断购买。

• 当 $d < B$ 时，在线代价为 $d$，最优代价为 $d$，比值为 1。
• 当 $d \ge B$ 时，在线代价为 $(B-1) + B = 2B - 1$，最优代价为 $B$。 因此，该策略在最坏情况下的竞争比严格收敛于： $$ \lim_{B \to \infty} (2B - 1) / B = 2 $$

Classic Problems

Paging & Caching

分页或缓存替换问题探讨在多级存储体系中如何高效管理有限的存储资源。假设系统拥有一个容量为 $k$ 的快速缓存（Cache），以及一个包含 $N$ 个页面的慢速主存，其中 $|N| > k$。系统面临一个未知的页面请求序列 $\sigma = (r_1, r_2, ..., r_n)$。 当请求的页面 $r_t$ 在缓存中时（命中，Cache Hit），代价为 0；当 $r_t$ 不在缓存中时（缺失，Page Fault），系统必须从主存将其调入缓存，代价为 1。如果此时缓存已满，在线算法必须在不可预知未来请求的前提下，选择一个缓存中的页面进行驱逐（Eviction）。问题的目标是最小化处理整个序列的总页面缺失次数。

对于任何确定性缓存算法（如先进先出 FIFO、最近最少使用 LRU），其竞争比严格为 $k$。理论上的下界定理证明，对于任意给定的确定性在线缓存算法，恶意对抗者（Adversary）始终可以构造出一个请求序列，使得在线算法每次请求都发生缺失，而离线最优策略（如 Belady 的 MIN 算法）每 $k$ 次请求才缺失一次，从而形成 $k$ 的理论惩罚下界。

为了突破这一确定性瓶颈，理论界引入了随机化机制。标记算法（Marking Algorithms）将请求序列划分为多个阶段，并在阶段初将所有页面标记为“未标记”。当发生缺失时，算法从“未标记”的页面中均匀随机地选择一个进行驱逐，并将新请求的页面设为“已标记”。通过势函数分析，标记算法的期望竞争比被证明为第 $k$ 个调和数：

$$ H_k = \sum_{i=1}^k 1 / i \approx \ln k $$

这一从线性 $O(k)$ 到对数级 $O(\log k)$ 的性能飞跃，展示了随机化在对抗恶劣输入模式时打破确定性下界的数学优势。

k-Server Problem

k-server 问题是在线度量空间调度领域的基石模型。设 $(M, d)$ 为一个度量空间，其中 $d(x, y)$ 为满足非负性、对称性和三角不等式的距离函数。系统中有 $k$ 个移动服务节点（Servers）初始分布在 $M$ 的某些点上。 给定一个随时间逐渐揭示的请求序列 $\sigma = (r_1, r_2, ..., r_n)$，其中每个请求 $r_t \in M$。对于每个请求，系统必须不可撤销地调度至少一个服务器移动到点 $r_t$ 进行响应。问题的优化目标是最小化所有 $k$ 个服务器移动的总距离之和。该模型可以广泛映射并泛化到磁盘调度、物流配送等高维动态决策场景。

工作函数算法（Work Function Algorithm, WFA）是解决该问题的核心理论框架，其基于深度的动态规划思想。设构型 $C$ 为 $k$ 个服务器在度量空间中的一个多重集位置分布。定义工作函数 $W_t(C)$ 为：处理完前 $t$ 个请求后，使这 $k$ 个服务器最终停留在构型 $C$ 所需的离线最优总距离代价。

在时刻 $t$，假设上一步的系统构型为 $C_{t-1}$，WFA 选择移动到一个必须包含请求位置 $r_t$ 的新构型 $C_t$，其决策准则是最小化以下复合目标式：

$$ W_t (C_t) + d(C_{t-1}, C_t) $$

该公式蕴含了深刻的平衡机制：$W_t (C_t)$ 项倾向于将系统拉向历史上的离线最优状态，而 $d(C_{t-1}, C_t)$ 项则作为贪心惩罚，限制了服务器为了追求历史最优而产生过度的盲目移动代价。

经过严密推导，WFA 被证明在任何度量空间中都具有 $(2k-1)$ 的严格竞争比。然而，该领域著名的 k-server 猜想（k-server conjecture）提出，对于任何度量空间，都必然存在竞争比严格为 $k$ 的确定性在线算法。这一猜想至今仍然是理论计算机科学中的核心开放性问题。

Online Bin Packing

设有序列物品体积 $w_t \in (0, 1]$ 逐一到达，目标是用最少的单位容量箱子将其完全装载。经典的 First Fit (FF) 算法具有 1.7 的渐近竞争比界限。 调和算法（Harmonic Algorithm）通过对体积进行离散化区间映射来优化性能。将区间 $(0, 1]$ 划分为 $M$ 个子区间 $I_j = (1/(j+1), 1/j]$，并为不同区间的物品分配专属的箱子类型，每个该类型的箱子固定装载 $j$ 个物品。当 $M \to \infty$ 时，其极限竞争比 $T_\infty$ 由以下级数给出：

$$ T_\infty = \sum_{i=1}^\infty 1 / (t_i - 1) \approx 1.691 $$

其中序列 $t_i$ 由非线性递推式 $t_1=2, t_{i+1} = t_i (t_i - 1) + 1$ 定义，为在线装箱问题提供了重要的理论上界。

Game Theory & Mechanism Design

Strategic Games & Equilibrium

Nash Equilibrium

策略型博弈可以形式化地表示为一个元组 $\Gamma = (N, (S_i)_{i \in N}, (u_i)_{i \in N})$，其中 $N = {1, 2, ..., n}$ 为参与者集合，$S_i$ 为参与者 $i$ 的纯策略空间，$u_i: S_1 \times ... \times S_n \to \mathbb{R}$ 为其效用函数。 在策略组合 $s = (s_1, ..., s_n)$ 中，若对任意参与者 $i$ 及其任意可选策略 $s_i' \in S_i$，均满足：

$$ u_i (s_i^*, s_{-i}^*) \ge u_i (s_i', s_{-i}^*) $$

则称策略组合 $s^*$ 为纯策略纳什均衡 (Pure Strategy Nash Equilibrium)。该公式严谨地表明，在给定其他参与者策略 $s_{-i}^*$ 不变的条件下，没有任何单方能够通过单方面偏离当前策略来提升自身效用。

PoA & PoS

为了量化自私行为对系统全局效率的损害，理论计算机科学引入了无政府代价 (Price of Anarchy, PoA) 与稳定代价 (Price of Stability, PoS)。设 $E$ 为所有纳什均衡点的集合，$C(s)$ 为策略组合 $s$ 下的系统总社会成本，$\operatorname{OPT} = \min_{s} C(s)$ 为理想状态下的社会最优成本。

• 无政府代价 (PoA)： 衡量最坏情况下的均衡效率，定义为： $$ \text{PoA} = (\max_{s \in E} C(s)) / \operatorname{OPT} $$ 经典的布雷斯悖论 (Braess’s Paradox) 在交通流分配模型中证明了增加一条零成本道路反而可能导致 PoA 大于 1，从而增加所有人的通行时间。
• 稳定代价 (PoS)： 衡量最好情况下的均衡效率，定义为： $$ \text{PoS} = (\min_{s \in E} C(s)) / \operatorname{OPT} $$ 它代表了存在一个中心化机构进行初步引导时，系统能维持稳定所需的最低效率损耗。

Location & Packing Games

在设施选址博弈 (Facility Location Game) 中，参与者选择设施的位置以最小化自身到设施的距离代价。而在装箱博弈 (Bin Packing Game) 中，物品作为理性的参与者，自主选择进入哪个箱子，其目标通常是最小化分摊到的箱子成本。 假设箱子 $j$ 的成本为 $c_j$，放入其中的物品集合为 $B_j$，若采用均摊成本共享机制，则物品 $i \in B_j$ 的个体成本为 $(c_j) / (|B_j|)$。这类博弈模型深刻揭示了分布式系统中局部自私决策与全局资源优化之间的数学张力。

Mechanism Design & Fair Division

Vickrey Auction

机制设计被誉为“逆向博弈论”。二价拍卖 (Vickrey 拍卖) 是解决单物品拍卖中信息不对称问题的理论基石。假设参与者 $i$ 对物品的真实估值为 $v_i$，其提交的报价为 $b_i$。 规则设定为：报价最高者 $i^* = \text{argmax}_i b_i$ 赢得物品，但只需支付第二高的报价 $p = \max_{j \ne i^*} b_j$。 在此机制下，参与者 $i$ 的准线性效用为： $ u_i = \begin{cases} v_i - p &\text{若} i = i^*, 0 &\text{否则} \end{cases}$ 通过数学分类讨论可以严格证明，无论其他人的报价如何，诚实报价 ($b_i = v_i$) 始终是每个参与者的占优策略 (Dominant Strategy)，这一性质被称为占优策略激励相容 (DSIC)。

Stable Matching

稳定匹配问题探讨如何在两个不相交的集合（如学生与学校、求职者与公司）之间建立一一映射。设两集合为 $M$ 和 $W$，每个人对另一集合的成员有严格的偏好排序 $\succ$。 如果存在匹配 $\mu$，使得存在对 $(m, w) \notin \mu$，满足 $w \succ_m \mu(m)$ 且 $m \succ_w \mu(w)$，则称 $(m, w)$ 为一个阻断对 (Blocking Pair)。不存在阻断对的匹配即为稳定匹配。 Gale-Shapley 延迟接受算法通过迭代的“提议-拒绝”机制，在 $O(n^2)$ 步内必然收敛到一个稳定匹配。理论进一步证明，该算法产生的匹配对提议方集合始终是理论上最优的。

Cake Cutting

切蛋糕问题是研究异质可分资源公平分配的连续模型。设资源为区间 $X = [0, 1]$，参与者 $i$ 的估值测度为 $V_i$，满足 $V_i(X) = 1$ 且具备可加性。两个核心的公平性数学标准为：

• 比例公平 (Proportionality)： $V_i(A_i) \ge 1/n$，即每个人认为自己至少获得了总价值的 $1/n$。Fink 协议通过递归的“切分与选择”在有限步内实现此标准。
• 无嫉妒性 (Envy-Freeness, EF)： 对于任意 $i, j$，满足： $$ V_i (A_i) \ge V_i (A_j) $$ 即没有任何人认为别人的份额比自己的好。经典的 Selfridge-Conway 算法通过引入“修剪”操作，给出了 $n=3$ 时无嫉妒分配的有限步代数解法。

Reference

金鱼马前辈的知乎