好的，我已经记录了你已学习过的题目列表。接下来，我将为你讲解一个线性规划领域中尚未提及的经典且重要的算法。这个算法是许多图论和组合优化问题求解的核心。
基于线性规划的图最小费用循环流问题的原始-对偶路径跟踪算法求解示例
题目描述
我们考虑一个有向图 \(G = (V, E)\) 上的最小费用循环流问题。图的每条边 \((i, j) \in E\) 都有一个容量上限 \(u_{ij} \ge 0\)，一个费用 \(c_{ij} \in \mathbb{R}\)。与标准的最小费用流问题不同，这里没有供应或需求。我们的目标是找到一个可行循环流 \(x = \{ x_{ij} \}\)，即在每个顶点处流入等于流出（流量平衡），且流量不超过容量限制。同时，我们需要最小化总费用 \(\sum_{(i,j)\in E} c_{ij} x_{ij}\)。
该问题可以建模为一个线性规划问题。原始-对偶路径跟踪算法是求解线性规划的一种多项式时间内点法，它通过求解一系列松弛的 KKT（Karush-Kuhn-Tucker）条件，从内部逐步逼近最优解。我们将使用这个算法来解决最小费用循环流问题。
循序渐进解题过程
步骤1：建立线性规划模型
- 决策变量：对每条边 \((i, j) \in E\)，定义流量变量 \(x_{ij}\)。
- 目标函数：最小化总运输费用。\(\min \sum_{(i,j)\in E} c_{ij} x_{ij}\)。
- 约束条件：
- 流量平衡约束（循环条件）：对于所有顶点 \(i \in V\)，流出的总流量等于流入的总流量。
\[ \sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = 0, \quad \forall i \in V \]
* **容量约束**：每条边上的流量非负且不超过其容量。
\[ 0 \le x_{ij} \le u_{ij}, \quad \forall (i,j) \in E \]
这个模型是一个标准的线性规划。
步骤2：引入对偶变量和构造对偶问题
为了应用原始-对偶路径跟踪算法，我们需要理解问题的对偶。
- 引入对偶变量：
- 对于每个流量平衡约束（对应于顶点 \(i\)），引入一个无约束的势变量 \(\pi_i\)。
- 对于每个容量上界约束 \(x_{ij} \le u_{ij}\)，引入一个非负的对偶松弛变量 \(s_{ij} \ge 0\)。对于下界约束 \(x_{ij} \ge 0\)，其对应的对偶变量隐含在互补松弛条件中。
- 构造拉格朗日函数：
\[ L(x, \pi, s) = \sum_{(i,j)} c_{ij} x_{ij} + \sum_i \pi_i \left( \sum_{j: (j,i)} x_{ji} - \sum_{j: (i,j)} x_{ij} \right) + \sum_{(i,j)} s_{ij} (x_{ij} - u_{ij}) \]
- 推导对偶问题：整理拉格朗日函数，得到关于 \(x\) 的部分：
\[ L(x, \pi, s) = \sum_{(i,j)} \left[ c_{ij} - (\pi_i - \pi_j) + s_{ij} \right] x_{ij} - \sum_{(i,j)} s_{ij} u_{ij} + \text{(常数项)} \]
为了使拉格朗日函数在 $ x $ 上有下界（从而对偶函数有意义），$ x_{ij} $ 的系数必须为非负（因为 $ x_{ij} \ge 0 $）。这导出了对偶可行性条件：$ c_{ij} - (\pi_i - \pi_j) + s_{ij} \ge 0 $。同时，$ s_{ij} \ge 0 $。
最大化对偶函数，我们得到对偶问题：
\[ \max_{\pi, s} \quad & -\sum_{(i,j)} s_{ij} u_{ij} \\ \text{s.t.} \quad & c_{ij} - (\pi_i - \pi_j) + s_{ij} \ge 0, \quad \forall (i,j) \in E \\ & s_{ij} \ge 0, \quad \forall (i,j) \in E \\ & \pi_i \text{ 无约束}, \quad \forall i \in V \]
可以定义 **缩减费用** $ \bar{c}_{ij} = c_{ij} - (\pi_i - \pi_j) $。那么对偶约束变为 $ \bar{c}_{ij} + s_{ij} \ge 0 $。由于 $ s_{ij} \ge 0 $，这意味着 $ s_{ij} = \max(0, -\bar{c}_{ij}) $ 是最优的松弛方式，从而使目标函数最小化（因为目标是最小化 $ \sum s_{ij} u_{ij} $ 的负值）。因此，对偶问题的目标等价于 $ \min \sum_{(i,j)} u_{ij} \max(0, -\bar{c}_{ij}) $。
步骤3：应用原始-对偶路径跟踪算法框架
该算法的核心思想是求解原问题和对偶问题的中心路径。中心路径由参数 \(\mu > 0\) 定义，是以下扰动 KKT 系统的解：
- 原始可行性：\(Ax = 0\) (流量平衡)，\(0 \le x \le u\)。
- 对偶可行性：\(\bar{c}_{ij} + s_{ij} \ge 0\)。
- 互补松弛条件（被扰动）：
- \(x_{ij} s_{ij} = \mu\) （对于上界约束的互补松弛）
- \(x_{ij} (-\bar{c}_{ij}) = 0?\) 这里需要小心。更标准的写法是引入 \(z_{ij}\) 作为 \(x_{ij} \ge 0\) 的对偶变量，并令 \(x_{ij} z_{ij} = \mu\)。但结合 \(\bar{c}_{ij} + s_{ij} - z_{ij} = 0\)（这是由拉格朗日函数对 \(x_{ij}\) 求导为0得到的稳定条件），我们可以得到一个统一的中心路径条件。
一个更常见的简化是，考虑将下界 \(0\) 和上界 \(u_{ij}\) 都视为一般约束。定义松弛变量 \(l_{ij} = x_{ij} - 0 \ge 0\) 和 \(w_{ij} = u_{ij} - x_{ij} \ge 0\)，并引入对应的对偶变量 \(z_{ij} \ge 0\) 和 \(s_{ij} \ge 0\)。中心路径条件为： - \(x_{ij} z_{ij} = \mu\)
- \(w_{ij} s_{ij} = \mu\)
并且有稳定条件：\(c_{ij} - (\pi_i - \pi_j) - z_{ij} + s_{ij} = 0\)，即 \(\bar{c}_{ij} = z_{ij} - s_{ij}\)。
步骤4：算法迭代步骤（牛顿法方向搜索）
算法从一个严格内点（即 \(x_{ij} > 0\), \(w_{ij} = u_{ij} - x_{ij} > 0\), \(z_{ij} > 0\), \(s_{ij} > 0\)）开始，并维持互补松弛乘积 \(XZe = \mu e\) 和 \(WSe = \mu e\)（其中 \(X, Z, W, S\) 是由 \(x_{ij}, z_{ij}, w_{ij}, s_{ij}\) 构成的对角矩阵，\(e\) 是全1向量）。
- 确定中心参数：设定 \(\mu = \sigma \cdot \eta\)，其中 \(\eta = (x^T z + w^T s) / (2|E|)\) 是当前互补松弛乘积的平均值，\(\sigma \in (0, 1)\) 是中心参数（如 0.1 到 0.5），用于控制向最优解推进的速度。
- 求解牛顿方向：我们对中心路径方程在当前点进行一阶泰勒展开（线性化），求解得到一个搜索方向 \((\Delta x, \Delta \pi, \Delta z, \Delta s)\)。
- 线性化后的方程包括：
- 原始可行性：\(A \Delta x = 0\) （流量平衡扰动为0）。
- 对偶可行性/稳定条件：\(\Delta z_{ij} - \Delta s_{ij} - (\Delta \pi_i - \Delta \pi_j) = -\bar{c}_{ij}\)。
- 中心路径线性化：\(Z \Delta x + X \Delta z = \mu e - XZe\)，\(-S \Delta x + W \Delta s = \mu e - WSe\)。
- 线性化后的方程包括：
- 求解线性系统：上述方程可以化简。从后两个方程解出 \(\Delta z\) 和 \(\Delta s\)：
\[ \Delta z = X^{-1}(\mu e - XZe - Z \Delta x) = \mu X^{-1}e - z - X^{-1}Z \Delta x \]
\[ \Delta s = W^{-1}(\mu e - WSe + S \Delta x) = \mu W^{-1}e - s + W^{-1}S \Delta x \]
代入对偶可行性方程：$ \Delta z - \Delta s - B^T \Delta \pi = -\bar{c} $，其中 $ B $ 是顶点-边关联矩阵（表示流量平衡约束 $ A $）。
经过代入和整理，我们得到一个只关于 $ \Delta x $ 和 $ \Delta \pi $ 的方程：
\[ -(X^{-1}Z + W^{-1}S) \Delta x - B^T \Delta \pi = -\bar{c} - (\mu X^{-1}e - z) + (\mu W^{-1}e - s) \]
定义 $ D = (X^{-1}Z + W^{-1}S)^{-1} $ 为一个正对角矩阵。我们可以先将方程写成：
\[ -D^{-1} \Delta x - B^T \Delta \pi = r_d \]
其中 $ r_d $ 是右边常数项。
再结合原始可行性方程 $ B \Delta x = 0 $，我们得到一个大系统：
\[ \begin{bmatrix} -D^{-1} & -B^T \\ B & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \pi \end{bmatrix} = \begin{bmatrix} r_d \\ 0 \end{bmatrix} \]
利用舒尔补（Schur Complement），可以消去 $ \Delta x $：由第一个方程得 $ \Delta x = -D (B^T \Delta \pi + r_d) $。代入第二个方程 $ B \Delta x = 0 $ 得：
\[ -B D B^T \Delta \pi = B D r_d \]
这是一个以 $ \Delta \pi $ 为变量的线性系统，其系数矩阵 $ B D B^T $ 是一个拉普拉斯式矩阵，对称正定（在连通图上）。解出 $ \Delta \pi $ 后，回代得到 $ \Delta x $，进而得到 $ \Delta z $ 和 $ \Delta s $。
- 确定步长：计算最大步长 \(\alpha_p\) 和 \(\alpha_d\)，使得新点 \((x+\alpha_p \Delta x, z+\alpha_d \Delta z, s+\alpha_d \Delta s)\) 仍然保持严格正性（\(x, z, w, s > 0\)）。通常取一个小于1的安全系数（如 0.995）。
- 更新迭代点：\(x := x + \alpha_p \Delta x\)，\(\pi := \pi + \alpha_d \Delta \pi\)，\(z := z + \alpha_d \Delta z\)，\(s := s + \alpha_d \Delta s\)。
- 检查终止条件：当原始不可行性 \(||Ax||\)（应为0）、对偶不可行性 \(||\bar{c} + s - z||\) 和互补松弛间隙 \(\eta\) 都小于预设精度 \(\epsilon\) 时，算法终止。
步骤5：算法总结与特点
- 初始化：需要找到一个严格内点的初始解。对于最小费用循环流，一个简单的初始内点解是取 \(x_{ij} = u_{ij}/2\)（如果 \(u_{ij} > 0\)），然后为满足流量平衡，可能需要进行微小调整或引入人工变量（使用大M法或两阶段内点法）。初始对偶变量可以设 \(\pi = 0\)，\(z_{ij} = s_{ij} = M\)（一个较大的正数），以满足 \(\bar{c}_{ij} = z_{ij} - s_{ij}\)。
- 多项式时间复杂性：原始-对偶路径跟踪算法是多项式时间算法。对于线性规划，迭代次数通常为 \(O(\sqrt{n} \log(1/\epsilon))\) 量级，其中 \(n\) 是变量数。每次迭代的主要计算成本在于求解那个拉普拉斯系统 \((B D B^T) \Delta \pi = b\)，这可以使用稀疏 Cholesky 分解或共轭梯度法等高效求解。
- 输出：算法结束时，我们得到一个近似最优的原始解 \(x^*\)（循环流）和对偶解 \(\pi^*\)（顶点势）。势 \(\pi^*\) 可以用来计算最优的缩减费用 \(\bar{c}_{ij}^*\)，并验证最优性条件（例如，对于 \(0 < x_{ij}^* < u_{ij}\) 的边，应有 \(\bar{c}_{ij}^* = 0\)；对于 \(x_{ij}^* = 0\) 的边，应有 \(\bar{c}_{ij}^* \ge 0\)；对于 \(x_{ij}^* = u_{ij}\) 的边，应有 \(\bar{c}_{ij}^* \le 0\)）。
这个算法是现代内点法求解线性规划，特别是网络流问题的强大工具之一，因为它能有效利用问题的网络结构，实现高效求解。