基于线性规划的无线网络中功率控制与速率优化的最大化和速率问题

字数 6639 2025-12-18 12:09:13

基于线性规划的无线网络中功率控制与速率优化的最大化和速率问题

题目描述

在一个无线网络（如蜂窝网络或Ad Hoc网络）中，有 \(N\) 个发射-接收对（可以理解为 \(N\) 条通信链路）。每条链路 \(i\) 有一个发射功率 \(p_i\)（变量），并且受到其他链路信号的干扰。在物理干扰模型下，链路 \(i\) 的信干噪比（SINR）为：

\[\text{SINR}_i = \frac{G_{ii} p_i}{\sum_{j \neq i} G_{ij} p_j + n_i} \]

其中：

\(G_{ij} \ge 0\) 是从发射机 \(j\) 到接收机 \(i\) 的信道增益（假设已知且固定），
\(n_i > 0\) 是接收机 \(i\) 处的背景噪声功率。

根据香农公式，链路 \(i\) 的可达数据传输速率为：

\[r_i = B \log_2(1 + \text{SINR}_i) \]

其中 \(B\) 是信道带宽（为简化，假设所有链路共用同一频带且 \(B=1\) Hz，故后续忽略 \(B\)）。

目标：在每条链路的发射功率 \(p_i\) 有上限 \(P^{\max}_i\) 的约束下，通过联合优化所有链路的发射功率 \(p_1, p_2, \dots, p_N\)，最大化网络的总和速率 \(\sum_{i=1}^N r_i\)。

问题形式化：

\[\begin{aligned} \max_{p_1,\dots,p_N} \quad & \sum_{i=1}^N \log_2\left(1 + \frac{G_{ii} p_i}{\sum_{j \neq i} G_{ij} p_j + n_i}\right) \\ \text{s.t.} \quad & 0 \le p_i \le P^{\max}_i, \quad i=1,\dots,N. \end{aligned} \]

这是一个非凸优化问题（因为目标函数是 \(\log(1+\text{SINR})\) 的和，而 SINR 是功率的分数线性函数），直接求解全局最优解是困难的。然而，我们可以通过变量替换和凸变换，将其等价转化为一个几何规划（Geometric Program, GP），而 GP 可以通过对数变换转化为凸优化问题（线性约束的凸问题），进而用线性规划的内点法等求解。下面我们分步骤讲解这个转化与求解过程。

解题步骤

步骤1：引入辅助变量，将分式形式转换为乘积形式

令 \(s_i = \text{SINR}_i\)，则

\[s_i = \frac{G_{ii} p_i}{\sum_{j \neq i} G_{ij} p_j + n_i}. \]

原目标变为：

\[\max \sum_{i=1}^N \log_2(1+s_i). \]

但这里 \(s_i\) 与 \(p_i\) 通过上述等式关联。我们可以将等式写为：

\[\frac{G_{ii} p_i}{s_i} = \sum_{j \neq i} G_{ij} p_j + n_i. \]

注意这个等式对于 \(s_i > 0\) 是等价的。于是，原问题可以重新表述为：

\[\begin{aligned} \max_{p, s} \quad & \sum_{i=1}^N \log_2(1+s_i) \\ \text{s.t.} \quad & \frac{G_{ii} p_i}{s_i} \ge \sum_{j \neq i} G_{ij} p_j + n_i, \quad i=1,\dots,N, \\ & 0 \le p_i \le P^{\max}_i, \quad s_i > 0. \end{aligned} \]

这里我们将等式放宽为不等式 \(\ge\)，但对于最大化 \(\log(1+s_i)\) 而言，在最优解处这个不等式会取等号（否则可以增大 \(s_i\) 以提高目标值），所以是等价的。

步骤2：转换为几何规划（GP）标准形式

几何规划的标准形式是：

\[\begin{aligned} \min \quad & f_0(x) \\ \text{s.t.} \quad & f_k(x) \le 1, \quad k=1,\dots,K, \\ & x_i > 0, \end{aligned} \]

其中 \(f_0, f_k\) 是正项式（posynomial），即形如 \(\sum_{j} c_j \prod_{i=1}^n x_i^{a_{ij}}\) 且系数 \(c_j > 0\) 的函数。

我们的约束 \(\frac{G_{ii} p_i}{s_i} \ge \sum_{j \neq i} G_{ij} p_j + n_i\) 可以改写为：

\[\frac{\sum_{j \neq i} G_{ij} p_j + n_i}{G_{ii} p_i} \cdot s_i \le 1. \]

因为 \(G_{ii} > 0, p_i > 0\)（若 \(p_i=0\) 则 \(s_i=0\)，但 \(s_i=0\) 时 \(\log(1+s_i)=0\)，通常不考虑零功率，因为目标为零，实际中我们避开零点），所以可安全假设 \(p_i > 0\)。于是左边是一个正项式（因为分子是正项式，乘以 \(s_i\) 后仍是正项式）。

目标函数 \(\sum_i \log_2(1+s_i)\) 是 \(s_i\) 的凹函数，但我们需要最小化一个正项式。为此，我们引入另一个常见技巧：最大化和速率等价于最小化其负值，但 \(\log\) 不是正项式。我们可以通过指数变量变换将其转化为凸问题。

步骤3：对数变换将几何规划转化为凸优化问题

令：

\[q_i = \ln p_i, \quad t_i = \ln s_i. \]

则 \(p_i = e^{q_i}, s_i = e^{t_i}\)。

代入不等式约束 \(\frac{\sum_{j \neq i} G_{ij} p_j + n_i}{G_{ii} p_i} \cdot s_i \le 1\)：

\[\frac{\sum_{j \neq i} G_{ij} e^{q_j} + n_i}{G_{ii} e^{q_i}} \cdot e^{t_i} \le 1. \]

两边取自然对数：

\[\ln\left( \sum_{j \neq i} G_{ij} e^{q_j} + n_i \right) - \ln(G_{ii}) - q_i + t_i \le 0. \]

记 \(f_i(q) = \ln\left( \sum_{j \neq i} G_{ij} e^{q_j} + n_i \right)\)，这是一个关于 \(q\) 的对数-和-指数（log-sum-exp）函数，它是凸函数。所以约束变为：

\[f_i(q) - q_i + t_i \le \ln(G_{ii}). \]

这是一个凸约束（因为 \(f_i(q)\) 凸， \(-q_i + t_i\) 线性）。

目标函数：\(\sum_i \log_2(1+e^{t_i}) = \frac{1}{\ln 2} \sum_i \ln(1+e^{t_i})\)。函数 \(\ln(1+e^{t_i})\) 是凸函数（它是 log-sum-exp 的特殊情况），但我们需要最大化一个凸函数，这是非凸问题。注意，我们之前的方向错了——我们实际上应该将原问题转化为最大化一个凹函数。

步骤4：利用“最大化和速率等价于最大化几何平均 SINR”的近似转换

直接最大化 \(\sum_i \log(1+s_i)\) 是非凸的，但我们可以利用加权和速率最大化的经典方法：通过引入权重 \(w_i \ge 0\)，我们可以将问题重新表达为加权和速率最大化，然后通过迭代更新权重来逼近原问题最优解。这是基于 Lagrangian 对偶 或 加权 MMSE 方法 的思想。但为了保持在线性规划框架内，我们可以采用另一种近似：用 高 SINR 近似 \(\log(1+s_i) \approx \log(s_i)\)，则目标变为 \(\sum_i \log(s_i)\)，这等价于最大化 \(\prod_i s_i\)，即几何平均 SINR。

在高 SINR 下，问题变为：

\[\begin{aligned} \max \quad & \sum_{i=1}^N \ln(s_i) \\ \text{s.t.} \quad & \frac{G_{ii} p_i}{s_i} \ge \sum_{j \neq i} G_{ij} p_j + n_i, \\ & 0 \le p_i \le P^{\max}_i, \quad s_i > 0. \end{aligned} \]

取对数：令 \(y_i = \ln s_i\)，则目标为 \(\sum_i y_i\) 线性！约束取对数后：

\[\ln\left( \sum_{j \neq i} G_{ij} e^{q_j} + n_i \right) - \ln(G_{ii}) - q_i + y_i \le 0. \]

这仍然是凸约束（因为左边是凸函数）。于是我们得到一个凸优化问题：

\[\begin{aligned} \max_{q, y} \quad & \sum_i y_i \\ \text{s.t.} \quad & \ln\left( \sum_{j \neq i} G_{ij} e^{q_j} + n_i \right) - q_i + y_i \le \ln(G_{ii}), \quad \forall i, \\ & q_i \le \ln P^{\max}_i, \quad q_i \text{ 无下界但实际 } p_i \ge 0 \Rightarrow q_i \in \mathbb{R}. \end{aligned} \]

步骤5：线性规划近似——逐次线性化

上面的问题目标线性，但约束非线性（凸）。我们可以用逐次线性化（例如 Frank-Wolfe 或序列线性规划 SLP）求解：在当前点 \((q^{(k)}, y^{(k)})\) 处，对凸函数 \(\ln\left( \sum_{j \neq i} G_{ij} e^{q_j} + n_i \right)\) 进行一阶近似（即用其切线代替），得到一个线性规划（LP），求解这个 LP 得到搜索方向，再沿方向更新。

具体地，在第 \(k\) 次迭代，约束的线性近似为：

\[\ln\left( \sum_{j \neq i} G_{ij} e^{q^{(k)}_j} + n_i \right) + \frac{\sum_{j \neq i} G_{ij} e^{q^{(k)}_j} (q_j - q^{(k)}_j)}{\sum_{j \neq i} G_{ij} e^{q^{(k)}_j} + n_i} - q_i + y_i \le \ln(G_{ii}). \]

这是关于变量 \(q, y\) 的线性不等式。于是我们得到 LP：

\[\begin{aligned} \max_{q, y} \quad & \sum_i y_i \\ \text{s.t.} \quad & \frac{\sum_{j \neq i} G_{ij} e^{q^{(k)}_j} (q_j - q^{(k)}_j)}{\sum_{j \neq i} G_{ij} e^{q^{(k)}_j} + n_i} - q_i + y_i \le \ln(G_{ii}) - \ln\left( \sum_{j \neq i} G_{ij} e^{q^{(k)}_j} + n_i \right), \quad \forall i, \\ & q_i \le \ln P^{\max}_i, \quad \forall i, \\ & q_i \ge L \; (\text{一个很小的下界，如 } \ln(10^{-10})), \quad y_i \in \mathbb{R}. \end{aligned} \]

求解这个 LP 得到 \((q^*, y^*)\)，然后更新 \(q^{(k+1)} = q^{(k)} + \alpha_k (q^* - q^{(k)})\)，其中 \(\alpha_k \in (0,1]\) 是步长（可通过线搜索确定）。重复直至收敛。

步骤6：从解恢复功率和评估真实和速率

最终迭代收敛后，得到最优 \(q_i^*\)，则最优功率为 \(p_i^* = e^{q_i^*}\)。然后代入原始 SINR 公式计算实际的和速率 \(\sum_i \log_2(1+\text{SINR}_i)\)。

算法总结

初始化：设定初始功率 \(p_i^{(0)}\)（例如 \(p_i^{(0)} = P^{\max}_i\)），令 \(q_i^{(0)} = \ln p_i^{(0)}\)，设定迭代次数 \(k=0\)，收敛阈值 \(\epsilon\)。
循环直到 \(\|q^{(k)} - q^{(k-1)}\| < \epsilon\)：
a. 计算当前点 \(q^{(k)}\) 处的线性化系数：

\[ A_{ij} = \frac{G_{ij} e^{q^{(k)}_j}}{\sum_{\ell \neq i} G_{i\ell} e^{q^{(k)}_\ell} + n_i}, \quad b_i = \ln(G_{ii}) - \ln\left( \sum_{j \neq i} G_{ij} e^{q^{(k)}_j} + n_i \right). \]

b. 求解线性规划：

\[ \begin{aligned} \max_{q, y} \quad & \sum_i y_i \\ \text{s.t.} \quad & \sum_{j \neq i} A_{ij} (q_j - q^{(k)}_j) - q_i + y_i \le b_i, \quad \forall i, \\ & q_i \le \ln P^{\max}_i, \quad q_i \ge L, \quad y_i \in \mathbb{R}. \end{aligned} \]

c. 得到解 \((q^*, y^*)\)，更新 \(q^{(k+1)} = q^{(k)} + \alpha_k (q^* - q^{(k)})\)（例如 \(\alpha_k=0.5\) 或通过线搜索）。
d. \(k \leftarrow k+1\)。
3. 输出：最优功率 \(p_i^* = e^{q_i^{(k)}}\)，计算实际和速率。

关键点说明

此方法将原非凸问题通过高 SINR 近似和逐次线性化，转化为一系列线性规划子问题，从而可以用单纯形法或内点法高效求解每个子问题。
高 SINR 近似在干扰较大的场景可能误差较大，此时可用更精确的 加权 MMSE 方法（其每次迭代也涉及一个凸优化，可类似线性化），但计算更复杂。
这个示例展示了线性规划在无线资源分配中作为迭代算法子步骤的典型应用，体现了线性规划在解决复杂非凸问题中的工具作用。

基于线性规划的无线网络中功率控制与速率优化的最大化和速率问题题目描述在一个无线网络（如蜂窝网络或Ad Hoc网络）中，有 \(N\) 个发射-接收对（可以理解为 \(N\) 条通信链路）。每条链路 \(i\) 有一个发射功率 \(p_ i\)（变量），并且受到其他链路信号的干扰。在物理干扰模型下，链路 \(i\) 的信干噪比（SINR）为： \[ \text{SINR} i = \frac{G {ii} p_ i}{\sum_ {j \neq i} G_ {ij} p_ j + n_ i} \] 其中： \(G_ {ij} \ge 0\) 是从发射机 \(j\) 到接收机 \(i\) 的信道增益（假设已知且固定）， \(n_ i > 0\) 是接收机 \(i\) 处的背景噪声功率。根据香农公式，链路 \(i\) 的可达数据传输速率为： \[ r_ i = B \log_ 2(1 + \text{SINR}_ i) \] 其中 \(B\) 是信道带宽（为简化，假设所有链路共用同一频带且 \(B=1\) Hz，故后续忽略 \(B\)）。目标：在每条链路的发射功率 \(p_ i\) 有上限 \(P^{\max} i\) 的约束下，通过联合优化所有链路的发射功率 \(p_ 1, p_ 2, \dots, p_ N\)，最大化网络的总和速率 \(\sum {i=1}^N r_ i\)。问题形式化： \[ \begin{aligned} \max_ {p_ 1,\dots,p_ N} \quad & \sum_ {i=1}^N \log_ 2\left(1 + \frac{G_ {ii} p_ i}{\sum_ {j \neq i} G_ {ij} p_ j + n_ i}\right) \\ \text{s.t.} \quad & 0 \le p_ i \le P^{\max}_ i, \quad i=1,\dots,N. \end{aligned} \] 这是一个非凸优化问题（因为目标函数是 \(\log(1+\text{SINR})\) 的和，而 SINR 是功率的分数线性函数），直接求解全局最优解是困难的。然而，我们可以通过变量替换和凸变换，将其等价转化为一个几何规划（Geometric Program, GP），而 GP 可以通过对数变换转化为凸优化问题（线性约束的凸问题），进而用线性规划的内点法等求解。下面我们分步骤讲解这个转化与求解过程。解题步骤步骤1：引入辅助变量，将分式形式转换为乘积形式令 \(s_ i = \text{SINR} i\)，则 \[ s_ i = \frac{G {ii} p_ i}{\sum_ {j \neq i} G_ {ij} p_ j + n_ i}. \] 原目标变为： \[ \max \sum_ {i=1}^N \log_ 2(1+s_ i). \] 但这里 \(s_ i\) 与 \(p_ i\) 通过上述等式关联。我们可以将等式写为： \[ \frac{G_ {ii} p_ i}{s_ i} = \sum_ {j \neq i} G_ {ij} p_ j + n_ i. \] 注意这个等式对于 \(s_ i > 0\) 是等价的。于是，原问题可以重新表述为： \[ \begin{aligned} \max_ {p, s} \quad & \sum_ {i=1}^N \log_ 2(1+s_ i) \\ \text{s.t.} \quad & \frac{G_ {ii} p_ i}{s_ i} \ge \sum_ {j \neq i} G_ {ij} p_ j + n_ i, \quad i=1,\dots,N, \\ & 0 \le p_ i \le P^{\max}_ i, \quad s_ i > 0. \end{aligned} \] 这里我们将等式放宽为不等式 \(\ge\)，但对于最大化 \(\log(1+s_ i)\) 而言，在最优解处这个不等式会取等号（否则可以增大 \(s_ i\) 以提高目标值），所以是等价的。步骤2：转换为几何规划（GP）标准形式几何规划的标准形式是： \[ \begin{aligned} \min \quad & f_ 0(x) \\ \text{s.t.} \quad & f_ k(x) \le 1, \quad k=1,\dots,K, \\ & x_ i > 0, \end{aligned} \] 其中 \(f_ 0, f_ k\) 是正项式（posynomial），即形如 \(\sum_ {j} c_ j \prod_ {i=1}^n x_ i^{a_ {ij}}\) 且系数 \(c_ j > 0\) 的函数。我们的约束 \(\frac{G_ {ii} p_ i}{s_ i} \ge \sum_ {j \neq i} G_ {ij} p_ j + n_ i\) 可以改写为： \[ \frac{\sum_ {j \neq i} G_ {ij} p_ j + n_ i}{G_ {ii} p_ i} \cdot s_ i \le 1. \] 因为 \(G_ {ii} > 0, p_ i > 0\)（若 \(p_ i=0\) 则 \(s_ i=0\)，但 \(s_ i=0\) 时 \(\log(1+s_ i)=0\)，通常不考虑零功率，因为目标为零，实际中我们避开零点），所以可安全假设 \(p_ i > 0\)。于是左边是一个正项式（因为分子是正项式，乘以 \(s_ i\) 后仍是正项式）。目标函数 \(\sum_ i \log_ 2(1+s_ i)\) 是 \(s_ i\) 的凹函数，但我们需要最小化一个正项式。为此，我们引入另一个常见技巧：最大化和速率等价于最小化其负值，但 \(\log\) 不是正项式。我们可以通过指数变量变换将其转化为凸问题。步骤3：对数变换将几何规划转化为凸优化问题令： \[ q_ i = \ln p_ i, \quad t_ i = \ln s_ i. \] 则 \(p_ i = e^{q_ i}, s_ i = e^{t_ i}\)。代入不等式约束 \(\frac{\sum_ {j \neq i} G_ {ij} p_ j + n_ i}{G_ {ii} p_ i} \cdot s_ i \le 1\)： \[ \frac{\sum_ {j \neq i} G_ {ij} e^{q_ j} + n_ i}{G_ {ii} e^{q_ i}} \cdot e^{t_ i} \le 1. \] 两边取自然对数： \[ \ln\left( \sum_ {j \neq i} G_ {ij} e^{q_ j} + n_ i \right) - \ln(G_ {ii}) - q_ i + t_ i \le 0. \] 记 \(f_ i(q) = \ln\left( \sum_ {j \neq i} G_ {ij} e^{q_ j} + n_ i \right)\)，这是一个关于 \(q\) 的对数-和-指数（log-sum-exp）函数，它是凸函数。所以约束变为： \[ f_ i(q) - q_ i + t_ i \le \ln(G_ {ii}). \] 这是一个凸约束（因为 \(f_ i(q)\) 凸， \(-q_ i + t_ i\) 线性）。目标函数：\(\sum_ i \log_ 2(1+e^{t_ i}) = \frac{1}{\ln 2} \sum_ i \ln(1+e^{t_ i})\)。函数 \(\ln(1+e^{t_ i})\) 是凸函数（它是 log-sum-exp 的特殊情况），但我们需要最大化一个凸函数，这是非凸问题。注意，我们之前的方向错了——我们实际上应该将原问题转化为最大化一个凹函数。步骤4：利用“最大化和速率等价于最大化几何平均 SINR”的近似转换直接最大化 \(\sum_ i \log(1+s_ i)\) 是非凸的，但我们可以利用加权和速率最大化的经典方法：通过引入权重 \(w_ i \ge 0\)，我们可以将问题重新表达为加权和速率最大化，然后通过迭代更新权重来逼近原问题最优解。这是基于 Lagrangian 对偶或加权 MMSE 方法的思想。但为了保持在线性规划框架内，我们可以采用另一种近似：用高 SINR 近似 \(\log(1+s_ i) \approx \log(s_ i)\)，则目标变为 \(\sum_ i \log(s_ i)\)，这等价于最大化 \(\prod_ i s_ i\)，即几何平均 SINR。在高 SINR 下，问题变为： \[ \begin{aligned} \max \quad & \sum_ {i=1}^N \ln(s_ i) \\ \text{s.t.} \quad & \frac{G_ {ii} p_ i}{s_ i} \ge \sum_ {j \neq i} G_ {ij} p_ j + n_ i, \\ & 0 \le p_ i \le P^{\max} i, \quad s_ i > 0. \end{aligned} \] 取对数：令 \(y_ i = \ln s_ i\)，则目标为 \(\sum_ i y_ i\) 线性！约束取对数后： \[ \ln\left( \sum {j \neq i} G_ {ij} e^{q_ j} + n_ i \right) - \ln(G_ {ii}) - q_ i + y_ i \le 0. \] 这仍然是凸约束（因为左边是凸函数）。于是我们得到一个凸优化问题： \[ \begin{aligned} \max_ {q, y} \quad & \sum_ i y_ i \\ \text{s.t.} \quad & \ln\left( \sum_ {j \neq i} G_ {ij} e^{q_ j} + n_ i \right) - q_ i + y_ i \le \ln(G_ {ii}), \quad \forall i, \\ & q_ i \le \ln P^{\max}_ i, \quad q_ i \text{ 无下界但实际 } p_ i \ge 0 \Rightarrow q_ i \in \mathbb{R}. \end{aligned} \] 步骤5：线性规划近似——逐次线性化上面的问题目标线性，但约束非线性（凸）。我们可以用逐次线性化（例如 Frank-Wolfe 或序列线性规划 SLP）求解：在当前点 \((q^{(k)}, y^{(k)})\) 处，对凸函数 \(\ln\left( \sum_ {j \neq i} G_ {ij} e^{q_ j} + n_ i \right)\) 进行一阶近似（即用其切线代替），得到一个线性规划（LP），求解这个 LP 得到搜索方向，再沿方向更新。具体地，在第 \(k\) 次迭代，约束的线性近似为： \[ \ln\left( \sum_ {j \neq i} G_ {ij} e^{q^{(k)} j} + n_ i \right) + \frac{\sum {j \neq i} G_ {ij} e^{q^{(k)} j} (q_ j - q^{(k)} j)}{\sum {j \neq i} G {ij} e^{q^{(k)} j} + n_ i} - q_ i + y_ i \le \ln(G {ii}). \] 这是关于变量 \(q, y\) 的线性不等式。于是我们得到 LP： \[ \begin{aligned} \max_ {q, y} \quad & \sum_ i y_ i \\ \text{s.t.} \quad & \frac{\sum_ {j \neq i} G_ {ij} e^{q^{(k)} j} (q_ j - q^{(k)} j)}{\sum {j \neq i} G {ij} e^{q^{(k)} j} + n_ i} - q_ i + y_ i \le \ln(G {ii}) - \ln\left( \sum_ {j \neq i} G_ {ij} e^{q^{(k)}_ j} + n_ i \right), \quad \forall i, \\ & q_ i \le \ln P^{\max}_ i, \quad \forall i, \\ & q_ i \ge L \; (\text{一个很小的下界，如 } \ln(10^{-10})), \quad y_ i \in \mathbb{R}. \end{aligned} \] 求解这个 LP 得到 \((q^ , y^ )\)，然后更新 \(q^{(k+1)} = q^{(k)} + \alpha_ k (q^* - q^{(k)})\)，其中 \(\alpha_ k \in (0,1 ]\) 是步长（可通过线搜索确定）。重复直至收敛。步骤6：从解恢复功率和评估真实和速率最终迭代收敛后，得到最优 \(q_ i^ \)，则最优功率为 \(p_ i^ = e^{q_ i^* }\)。然后代入原始 SINR 公式计算实际的和速率 \(\sum_ i \log_ 2(1+\text{SINR}_ i)\)。算法总结初始化：设定初始功率 \(p_ i^{(0)}\)（例如 \(p_ i^{(0)} = P^{\max}_ i\)），令 \(q_ i^{(0)} = \ln p_ i^{(0)}\)，设定迭代次数 \(k=0\)，收敛阈值 \(\epsilon\)。循环直到 \(\|q^{(k)} - q^{(k-1)}\| < \epsilon\)： a. 计算当前点 \(q^{(k)}\) 处的线性化系数： \[ A_ {ij} = \frac{G_ {ij} e^{q^{(k)} j}}{\sum {\ell \neq i} G_ {i\ell} e^{q^{(k)} \ell} + n_ i}, \quad b_ i = \ln(G {ii}) - \ln\left( \sum_ {j \neq i} G_ {ij} e^{q^{(k)} j} + n_ i \right). \] b. 求解线性规划： \[ \begin{aligned} \max {q, y} \quad & \sum_ i y_ i \\ \text{s.t.} \quad & \sum_ {j \neq i} A_ {ij} (q_ j - q^{(k)}_ j) - q_ i + y_ i \le b_ i, \quad \forall i, \\ & q_ i \le \ln P^{\max}_ i, \quad q_ i \ge L, \quad y_ i \in \mathbb{R}. \end{aligned} \] c. 得到解 \((q^ , y^ )\)，更新 \(q^{(k+1)} = q^{(k)} + \alpha_ k (q^* - q^{(k)})\)（例如 \(\alpha_ k=0.5\) 或通过线搜索）。 d. \(k \leftarrow k+1\)。输出：最优功率 \(p_ i^* = e^{q_ i^{(k)}}\)，计算实际和速率。关键点说明此方法将原非凸问题通过高 SINR 近似和逐次线性化，转化为一系列线性规划子问题，从而可以用单纯形法或内点法高效求解每个子问题。高 SINR 近似在干扰较大的场景可能误差较大，此时可用更精确的加权 MMSE 方法（其每次迭代也涉及一个凸优化，可类似线性化），但计算更复杂。这个示例展示了线性规划在无线资源分配中作为迭代算法子步骤的典型应用，体现了线性规划在解决复杂非凸问题中的工具作用。