基于线性规划的图带宽分配问题的最大效用公平性优化求解示例
1. 问题描述
假设有一个通信网络，其拓扑结构可以用一个有向图 \(G = (V, E)\) 表示。其中，\(V\) 是网络节点（如路由器、交换机）的集合，\(E\) 是连接这些节点的通信链路的集合。每条有向边 \(e \in E\) 都有一个固定的传输容量（带宽）\(c_e > 0\)。
现在，网络中存在一个用户请求的集合 \(K\)。每个用户请求 \(k \in K\) 代表从一个源节点 \(s_k\) 到一个目标节点 \(t_k\) 的数据流需求。这个数据流是可分割的（即可以走多条路径），其总传输速率（即分配到该请求上的总带宽）为 \(x_k \geq 0\)。用户请求 \(k\) 获得速率 \(x_k\) 后，会产生一个效用（Utility），记为 \(U_k(x_k)\)。我们假设效用函数 \(U_k(\cdot)\) 是凹的、连续可微且严格递增的函数，这反映了“随着分配的带宽增加，用户满意度（效用）增加，但增加的速度会减慢”这一普遍规律，例如 \(U_k(x) = \log(1 + x)\) 或 \(U_k(x) = w_k \cdot \log(x)\)，其中 \(w_k > 0\) 是表示请求优先级的权重。
我们的目标是为所有用户请求分配带宽，使得在满足每条链路容量限制的前提下，最大化所有用户效用的总和，同时实现某种形式的公平性。这是一个网络效用最大化（Network Utility Maximization, NUM） 问题。
数学模型如下：
目标：最大化总网络效用
\[\max \sum_{k \in K} U_k(x_k) \]
约束条件：
- 链路容量约束：对于每条链路 \(e \in E\)，所有经过它的用户请求分配在该链路上的带宽之和不能超过该链路的容量。
\[ \sum_{k \in K} f_e^k \leq c_e, \quad \forall e \in E \]
其中，$f_e^k \geq 0$ 表示为用户请求 $k$ 分配在链路 $e$ 上的带宽。注意，$x_k = \sum_{e \in \delta^+(s_k)} f_e^k$，但更一般地，它必须满足**流守恒**约束。
- 流守恒与多路径路由约束：对于每个用户请求 \(k\) 和每个节点 \(v \in V \setminus \{s_k, t_k\}\)，流入该节点的流量等于流出该节点的流量。
\[ \sum_{e \in \delta^-(v)} f_e^k = \sum_{e \in \delta^+(v)} f_e^k, \quad \forall k \in K, \forall v \in V \setminus \{s_k, t_k\} \]
其中，$\delta^-(v)$ 表示指向节点 $v$ 的入边集合，$\delta^+(v)$ 表示从节点 $v$ 出发的出边集合。
对于源点 $s_k$，净流出量为 $x_k$：
\[ \sum_{e \in \delta^+(s_k)} f_e^k - \sum_{e \in \delta^-(s_k)} f_e^k = x_k, \quad \forall k \in K \]
对于汇点 $t_k$，净流入量为 $x_k$：
\[ \sum_{e \in \delta^-(t_k)} f_e^k - \sum_{e \in \delta^+(t_k)} f_e^k = x_k, \quad \forall k \in K \]
- 非负约束：
\[ x_k \geq 0, \quad f_e^k \geq 0, \quad \forall k \in K, e \in E \]
2. 解题思路
- 问题性质分析：我们的目标函数是凹函数（多个凹函数的和仍是凹函数），所有约束条件都是线性的。因此，这是一个凸优化问题（具体来说，是一个约束为线性的凹函数最大化问题）。在凸优化中，局部最优解就是全局最优解，并且通常可以通过求解其对偶问题来获得高效的分布式算法。
- 对偶分解：这是求解大规模网络效用最大化问题的核心思想。我们通过引入拉格朗日乘子，将复杂的、耦合的原始问题分解为一系列简单的、可并行求解的子问题。
- 求解流程：
- 构建拉格朗日函数：对耦合约束（链路容量约束）引入拉格朗日乘子（也称为“链路价格”或“对偶变量”）\(\lambda_e \geq 0\)。
- 形成对偶函数：拉格朗日函数可以分解为关于每个用户请求 \(k\) 的子问题之和。每个子问题只涉及该请求的变量 \((x_k, \{f_e^k\})\)，可以在给定链路价格 \(\lambda_e\) 的情况下独立求解。这通常是一个以价格 \(\lambda_e\) 为链路费用的“最小费用流”问题或其变体。
- 求解对偶问题：对偶问题是关于 \(\lambda\) 的最小化问题。由于对偶函数总是凹的，对偶问题是一个凸优化问题。我们可以用梯度投影法等迭代方法来更新链路价格 \(\lambda\)。价格的更新规则具有直观的经济学解释：如果一条链路上的总流量超过了其容量（约束被违反），就提高该链路的“价格”，以减少对其的需求；反之则降低价格。
- 原始变量恢复：在一定条件下（例如效用函数严格凹），对偶问题的最优解可以让我们恢复出原始问题的最优解 \((x_k^*, \{f_e^{k*}\})\)。
3. 循序渐进讲解
步骤1：写出完整的原始问题 (Primal Problem, PP)
为了方便，我们将流守恒约束写得更紧凑一些。定义矩阵 \(A^k\) 为用户请求 \(k\) 的节点-边关联矩阵，其行对应节点 \(v \in V\)，列对应边 \(e \in E\)。\(A^k_{v,e} = 1\) 如果边 \(e\) 从节点 \(v\) 出发，\(A^k_{v,e} = -1\) 如果边 \(e\) 指向节点 \(v\)，否则为0。再定义向量 \(b^k\)，其中 \(b^k_{s_k} = 1, b^k_{t_k} = -1\)，其他分量为0。
那么，流守恒约束可以写为：\(A^k f^k = x_k b^k\)，其中 \(f^k = (f_e^k)_{e \in E}\) 是请求 \(k\) 的链路流量向量。
原始问题 (PP) 为：
\[\begin{aligned} \max_{x_k, f^k} & \quad \sum_{k \in K} U_k(x_k) \\ \text{s.t.} & \quad \sum_{k \in K} f_e^k \leq c_e, \quad \forall e \in E \quad \text{(容量约束，耦合约束)} \\ & \quad A^k f^k = x_k b^k, \quad \forall k \in K \quad \text{(流守恒约束，可分解)} \\ & \quad x_k \geq 0, \quad f^k \geq 0, \quad \forall k \in K \end{aligned} \]
步骤2：构造拉格朗日函数
为每个链路容量约束引入拉格朗日乘子（对偶变量，也称为“价格”）\(\lambda_e \geq 0\)。令向量 \(\lambda = (\lambda_e)_{e \in E}\)。
拉格朗日函数 \(L(x, f, \lambda)\) 为原始目标函数加上违反容量约束的惩罚项：
\[L(x, f, \lambda) = \sum_{k \in K} U_k(x_k) - \sum_{e \in E} \lambda_e \left( \sum_{k \in K} f_e^k - c_e \right) \]
可以重排为：
\[L(x, f, \lambda) = \sum_{k \in K} \left[ U_k(x_k) - \sum_{e \in E} \lambda_e f_e^k \right] + \sum_{e \in E} \lambda_e c_e \]
步骤3：构建对偶函数
对偶函数 \(g(\lambda)\) 定义为，在给定价格 \(\lambda\) 下，拉格朗日函数关于原始变量的上确界（因为我们是最大化问题）：
\[g(\lambda) = \sup_{x_k \geq 0, f^k \geq 0, A^k f^k = x_k b^k} L(x, f, \lambda) \]
代入 \(L\) 的表达式：
\[g(\lambda) = \sum_{e \in E} \lambda_e c_e + \sum_{k \in K} \sup_{\substack{x_k \geq 0, f^k \geq 0 \\ A^k f^k = x_k b^k}} \left[ U_k(x_k) - \sum_{e \in E} \lambda_e f_e^k \right] \]
关键的一步来了：对偶函数可以按用户 \(k\) 分解！每个 \(k\) 对应的上确界问题是一个独立的子问题：
子问题 \(SP_k(\lambda)\) （对于给定的链路价格向量 \(\lambda\)）：
\[\sup_{\substack{x_k \geq 0, f^k \geq 0 \\ A^k f^k = x_k b^k}} \left[ U_k(x_k) - \sum_{e \in E} \lambda_e f_e^k \right] \]
这个子问题的直观意义是：用户 \(k\) 希望在给定的链路“价格”（或“成本”）体系 \(\lambda\) 下，最大化自己的“净效用”——即从总数据率 \(x_k\) 中获得的效用 \(U_k(x_k)\)，减去使用网络链路所需支付的总“费用” \(\sum_{e \in E} \lambda_e f_e^k\)，同时要满足从 \(s_k\) 到 \(t_k\) 的流量为 \(x_k\) 的流守恒约束。
步骤4：求解子问题
子问题 \(SP_k(\lambda)\) 对于每个 \(k\) 是独立的。给定 \(\lambda\)，它是一个带线性等式约束的凹函数最大化问题。其经济解释是：用户 \(k\) 需要决定其总传输速率 \(x_k\)，以及如何分配流量 \(f^k\) 来路由这 \(x_k\) 单位的流量，以最大化净效用。
我们可以将其视为一个两层决策：
- 外层：确定总速率 \(x_k\)。对于任意一个给定的 \(x_k\)，内层问题是在给定 \(x_k\) 和价格 \(\lambda\) 下，找到从 \(s_k\) 到 \(t_k\) 的、流量为 \(x_k\) 的“最小费用流”，其费用就是 \(\sum_{e \in E} \lambda_e f_e^k\)。我们记这个最小费用为 \(C_k(x_k, \lambda)\)。
- 内层：最小费用路由。对于固定的 \(x_k\)，内层问题是标准的线性规划——最小费用流问题：
\[ C_k(x_k, \lambda) = \min_{f^k \geq 0} \left\{ \sum_{e \in E} \lambda_e f_e^k : A^k f^k = x_k b^k \right\} \]
这个问题的解很容易刻画：最优路由方案是**将所有 $x_k$ 单位的流量都沿着从 $s_k$ 到 $t_k$ 的、在价格 $\lambda$ 下的最短路径（费用最小路径）** 发送。如果有多条最短路径，可以在它们之间任意分割流量。设最短路径的费用（每单位流量）为 $d_k(\lambda)$。那么，最小总费用 $C_k(x_k, \lambda) = d_k(\lambda) \cdot x_k$。
于是，子问题 \(SP_k(\lambda)\) 简化为一个关于单变量 \(x_k\) 的优化问题：
\[\sup_{x_k \geq 0} \left[ U_k(x_k) - d_k(\lambda) \cdot x_k \right] \]
由于 \(U_k\) 是凹函数，\(-d_k(\lambda)x_k\) 是线性的，所以括号内整体是 \(x_k\) 的凹函数。其最优解 \(x_k^*(\lambda)\) 由一阶最优性条件给出：
\[\frac{dU_k(x_k)}{dx_k} = d_k(\lambda) \]
即，最优速率 \(x_k^*(\lambda)\) 是使得边际效用等于路径价格 \(d_k(\lambda)\) 的那个点。如果效用函数是 \(U_k(x) = w_k \log x\)，则 \(U'_k(x) = w_k / x\)，解得 \(x_k^*(\lambda) = w_k / d_k(\lambda)\)。这具有清晰的解释：优先级 \(w_k\) 越高，获得的带宽越多；路径费用 \(d_k(\lambda)\) 越高（网络越拥塞），获得的带宽越少。
步骤5：形成对偶问题与价格更新
对偶问题 (Dual Problem, DP) 是极小化对偶函数：
\[\min_{\lambda \geq 0} g(\lambda) \]
由于 \(g(\lambda)\) 关于 \(\lambda\) 是凸的（实际上是由一系列线性函数的上确界构成），这是一个凸优化问题。我们可以用梯度法或次梯度法求解。
注意到，给定 \(\lambda\)，我们求解了所有子问题，得到了最优的 \(x_k^*(\lambda)\) 和相应的最优路由 \(f^{k*}(\lambda)\)。那么，\(g(\lambda)\) 在 \(\lambda\) 处的一个次梯度是：
\[h_e(\lambda) = c_e - \sum_{k \in K} f_e^{k*}(\lambda), \quad \forall e \in E \]
这个次梯度的分量 \(h_e(\lambda)\) 正是链路 \(e\) 上的剩余容量（或容量违反量的负数）。于是，标准的梯度投影法（这里实际上是次梯度投影法）更新规则为：
\[\lambda_e^{(t+1)} = \left[ \lambda_e^{(t)} - \alpha^{(t)} \cdot \left( c_e - \sum_{k \in K} f_e^{k*}(\lambda^{(t)}) \right) \right]^+ \]
其中，\([z]^+ = \max(0, z)\) 是向非负象限的投影，\(\alpha^{(t)} > 0\) 是第 \(t\) 次迭代的步长。
这个更新规则有非常优美的网络解释：
- \(\lambda_e\) 是链路 \(e\) 的“拥塞价格”。
- \(\sum_{k} f_e^{k*}\) 是当前迭代中链路 \(e\) 上的总负载。
- 如果负载超过容量 (\(c_e - \sum f_e^{k*} < 0\))，价格 \(\lambda_e\) 上升，这会增加用户 \(k\) 使用该链路的成本 \(d_k(\lambda)\)，从而促使用户 \(k\) 减少速率 \(x_k^*\) 或选择其他更便宜的路径。
- 如果负载小于容量 (\(c_e - \sum f_e^{k*} > 0\))，价格 \(\lambda_e\) 下降，吸引更多流量。
- 这个过程持续迭代，直到供需达到平衡。在数学上，当迭代收敛时，我们就得到了原始问题的最优解（在 \(U_k\) 严格凹等条件下）。
步骤6：算法流程总结
- 初始化：设置初始链路价格 \(\lambda_e^{(0)} \geq 0\) (例如全0或全1)，迭代次数 \(t=0\)。设定步长序列 \(\alpha^{(t)}\) (如 \(\alpha^{(t)} = a/(b+t)\) 以保证收敛)。
- 循环直到收敛：
a. 用户端分布式优化：每个用户请求 \(k\) 广播当前的价格向量 \(\lambda^{(t)}\)。
b. 最短路径计算：每个用户 \(k\) 根据价格 \(\lambda^{(t)}\) 计算从 \(s_k\) 到 \(t_k\) 的最短路径费用 \(d_k(\lambda^{(t)})\) 和对应的最短路径集。
c. 速率调整：每个用户 \(k\) 根据公式 \(U'_k(x_k) = d_k(\lambda^{(t)})\) 计算其最优速率 \(x_k^{(t)}\) 和对应的路由方案 \(f^{k,(t)}\) (将所有流量 \(x_k^{(t)}\) 分配到最短路径上)。
d. 网络端价格更新：每条链路 \(e\) 测量其总流量负载 \(y_e^{(t)} = \sum_k f_e^{k,(t)}\)。
e. 价格调整：每条链路 \(e\) 根据规则 \(\lambda_e^{(t+1)} = [\lambda_e^{(t)} - \alpha^{(t)} (c_e - y_e^{(t)})]^+\) 独立更新其价格。
f. \(t := t+1\)。 - 输出：当价格和流量的变化很小时停止，输出最终的速率分配 \(x_k^*\) 和路由方案 \(f^{k*}\)。
4. 小结与意义
- 问题本质：我们将一个复杂的、耦合的网络效用最大化问题，通过对偶分解，转化为一组可以在用户端独立求解的“效用最大化-最小费用流”子问题，以及一个在网络链路上独立更新的“价格调节”对偶问题。
- 公平性体现：公平性是通过效用函数 \(U_k(x_k)\) 的形式来保证的。例如，使用 \(U_k(x) = \log x\) 会导向比例公平（Proportional Fairness）；使用 \(U_k(x) = w_k \log x\) 是加权比例公平；使用 \(U_k(x) = x^{1-\alpha}/(1-\alpha) (\alpha \neq 1)\) 则导向 \(\alpha\)-公平族。因此，最大化凹效用总和本身就内嵌了公平性的准则。
- 分布式实现：上述算法是分布式的。用户只需要知道自己的效用函数和网络价格，并求解本地优化问题。网络链路只需要知道本地负载来更新价格。这非常适合大规模网络的自主管理。
- 实际应用：这是互联网TCP拥塞控制（如FAST TCP, BBR等）、无线网络资源分配等领域的理论基础。它将经济学中的价格机制引入网络资源分配，实现了拥塞控制、路由选择和速率分配的三者联合最优。
这个例子展示了线性/凸优化理论，特别是对偶分解方法，在解决复杂网络资源分配问题时的强大能力和深刻洞见。