前言
记录遇到的通信中的数学优化方法。本文所介绍的是分式规划（Fractional Programming，FP）在以和速率最大化为目标的波束赋形问题求解中的应用。其关键思想有二：
- 利用 Lagrange 对偶将 SINR 项提取至 log 函数外面；
- FP 中的 二次变换（Quadratic Transform）。
FP 在通信中的应用有很多，如功率控制、波束赋形以及蜂窝小区间的用户调度等，且包含多种 FP 技术。但目前只接触到了其中的二次变换方法，后面将继续学习并记录。下面两篇论文总结了通信中的 FP 技术：
一、背景介绍
该文章考虑下行链路可重构全息表面（Reconfigurable Holographic Surface，RHS）辅助的多用户通信系统，提出基于 RHS 的混合波束赋形方案。在基带完成数字波束赋形（Digital Beamforming），在 RHS 上进行全息波束赋形（Holographic Beamforming），用户端进行接收合并（Combining）。对于波束赋形的设计，该文章建立以和速率最大化为目标的优化模型，并将该问题拆分为三个子问题：
数字波束赋形：ZF 预编码 + 注水功率分配。
全息波束赋形：分式规划。通过线性近似将非凸问题转化为凸优化问题，再利用 Language 乘子法迭代求解。
模拟接收合并：坐标上升法。
最后通过三个子问题的交替迭代求解，直至问题收敛，得到次优解。
本文仅记录第 2 个子问题的 FP 方法。
二、FP 之二次变换理论
给定一个约束集 $\mathcal{X}$ 以及函数 $A(\mathbf{x})和B(\mathbf{x}):\mathbb{R}^n\rightarrow \mathbb{R}_+$，有优化问题
$$
\begin{array}{ll}
\underset{\mathbf{x}}{\operatorname{maximize}} & \frac{A(\mathbf{x})}{B(\mathbf{x})} \
\text { subject to } & \mathbf{x} \in \mathcal{X}
\end{array}
$$
那么该问题就等效于
$$
\begin{array}{ll}
\underset{\mathbf{x}, y}{\operatorname{maximize}} \quad 2 y \sqrt{A(\mathbf{x})}-y^{2} B(\mathbf{x}) \
\text { subject to }\quad \mathrm{x} \in \mathcal{X}
\end{array}
$$
其中，$y=\frac{\sqrt{A(\mathbf{x})}}{B(\mathbf{x})}$。
三、原目标优化模型
原和速率最大化问题：
$$
\begin{aligned}
\max {\left{\mathbf{W}, \mathbf{V}, \mathrm{M}{m, n}\right}} & \sum_{l=1}^{L} R_{l} \
\text { s.t. } &\left|\mathbf{W}{l}(j)\right|^{2}=1, \
& \operatorname{Tr}\left(\mathbf{M V} \mathbf{V}^{H} \mathbf{M}^{H}\right) \leq P{T}, \
& 0 \leq \mathbf{M}{m, n} \leq 1, \forall m, n,
\end{aligned}
$$
其中，$P_T$ 是基站的总功率约束，$R_l$ 是用户 $l$ 的速率，共 $L$ 个用户。$\mathbf{V}$ 是数字预编码矩阵，$M{m,n}$ 是全息波束赋形矩阵中的元素，用于控制全息图案的振幅，$\mathbf{W}$ 是模拟接收合并矩阵，因此有恒模约束 $\left|\mathbf{W}{l}(j)\right|^{2}=1$。用户 $l$ 速率的具体表达式为：
$$
R{l}=\log {2}\left(1+\frac{\left|\mathbf{W}{l}^{H} \mathbf{H}{l} \mathbf{M V}{l}\right|^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\mathbf{W}{l}^{H} \mathbf{H}{l} \mathbf{M} \mathbf{V}{l^{\prime}}\right|^{2}}\right)
$$
对于原文中的问题拆解，当给定数字预编码矩阵 $\mathbf{V}$ 和模拟接收合并矩阵 $\mathbf{W}$ 时，该子问题可以表示如下：
$$
\max {\left{\mathrm{M}{m, n}\right}} \sum{l=1}^{L} R_{l}, \quad \text { s.t. } \quad 0 \leq \mathrm{M}_{m, n} \leq 1, \forall m, n
$$
该问题为非凸问题。
四、问题转化
4.1 线性近似
为了将待优化变量 ${M_{m,n}}$ 单独分离出来，将该子问题中的矩阵用线性求和的方式表示
$$
\begin{array}{ll}
\max_\limits{\left{\mathrm{M}{m, n}\right}} & \sum{l=1}^{L} \log {2}\left(1+\frac{\left|\sum{m, n} \mathrm{M}{m, n} b{m, n}^{l, l}\right|^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}\right) \
\text { s.t. } & 0 \leq \mathrm{M}{m, n} \leq 1, \forall m, n,
\end{array}
$$
其中，项 $\left|\sum{m, n} \mathrm{M}{m, n} b{m, n}^{l, l}\right|$ 可以线性近似为 $\sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l}$ ，这里的目的是为了去掉绝对值以便于后面的分式规划转换。具体推导请参照文章《Reconfigurable Holographic Surface Enabled Multi-User Wireless Communications: Amplitude-Controlled Holographic Beamforming》中的 Appendix B，此处不再赘述。线性近似后表达式为
$$
\begin{array}{ll}
\max_\limits{\left{\mathrm{M}{m, n}\right}} & \sum{l=1}^{L} \log {2}\left(1+\frac{\left(\sum{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right)^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}\right) \
\text { s.t. } & 0 \leq \mathrm{M}_{m, n} \leq 1, \forall m, n,
\end{array}\quad(1)
$$
4.2 FP 应用
先给出最终转化后的凸优化问题
$$
\begin{aligned}
\max {\left{\mathrm{M}{m, n}, \gamma_{l}, \delta_{l}\right}}& \sum_{l=1}^{L} A_{l}\
\text { s.t. } & 0 \leq \mathrm{M}{m, n} \leq 1, \forall m, n
\end{aligned}\quad(2)
$$
其中，$\gamma_l$ 和 $\delta_l$ 是引入的两个辅助变量，$A_l$ 的具体表达式为
$$
\begin{array}{ll}
A{l}\left(\mathrm{M}{m, n}, \gamma_l, \delta_l\right)=\frac{1}{\log 2}\left[\log \left(1+\gamma{l}\right)-\gamma_{l}+2 \delta_{l} \sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right. \
\left.\sqrt{1+\gamma_{l}}-\delta_{l}^{2}\left(J \sigma^{2}+\sum_{l^{\prime}=1}^{L}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}\right)\right]
\end{array}
$$
其具体的转化步骤如下：
对于每个用户的 $R_l$ ，其等价于
$$
\begin{aligned}
R_l(\mathrm{M}{m,n},\gamma_l)=\max_\limits{\left{\gamma_l\right}}\quad & \frac{1}{\log 2}\log\left(1+\gamma_l\right) \
\text { s.t. } \quad&\gamma_l=\frac{\left(\sum{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right)^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}
\end{aligned}\quad(3)
$$
这一步是为了将 SINR 项从 log 函数中拆解出来。然后通过引入 Lagrange 乘子 $\lambda_l$ ，可以写出该问题的 Lagrange 对偶问题，即
$$
L_(\gamma_l,\lambda_l)=\frac{1}{\log 2}\log \left(1+\gamma_l\right)-\lambda_l\left(\gamma_l-\frac{\left(\sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right)^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}\right)\quad(4)
$$
对于该对偶问题，在最优解处 $\partial L/\partial \gamma_l=0$ ，可以得到
$$
\lambda_l=\frac{1}{\log 2}·\frac{1}{1+\gamma_l}
$$
将 $(3)$ 中的约束代入上式，得到该 Lagrange 函数关于 $\boldsymbol{\lambda}$ 的最优解
$$
\begin{aligned}
\lambda_l^*=&\frac{1}{\log 2}·\frac{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}+\left(\sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right)^{2}}\
=&\frac{1}{\log 2}·\frac{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}{J \sigma^{2}+\sum_{l^{\prime}=1}^L\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}
\end{aligned}
$$
将 $\lambda^*$ 代入式 $(4)$ ，即可得到包含分式规划标准形式的 $R_l(\mathrm{M}{m,n},\gamma_l)$ ，即
$$
\begin{aligned}
R{l}\left(\mathrm{M}{m, n}, \gamma{l}\right)&=\max {\left{\gamma{l}\right}} \frac{1}{\log 2}\left[\log \left(1+\gamma_{l}\right)-\gamma_{l}\right] \
&+\frac{1}{\log 2} \cdot \frac{\left(\sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l} \cdot \sqrt{1+\gamma_{l}}\right)^{2}}{J \sigma^{2}+\sum_{l^{\prime}=1}^{L} \mid \sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l,\left.l^{\prime}\right|^{2}}}
\end{aligned}
$$
接着利用第二节中的 FP 二次转化理论，很容易即可将 $R_{l}\left(\mathrm{M}{m, n}, \gamma{l}\right)$ 转化为 $A_{l}\left(\mathrm{M}_{m, n}, \gamma_l, \delta_l\right)$ 。因此，原非凸的子优化问题 $(1)$ 也就转化为 凸优化问题 $(2)$ 。
利用 Lagrange 乘数法对该凸优化问题进行迭代求解：
由于问题 $(2)$ 存在多个辅助变量，因此可以通过分别令 $\partial A_{l} / \partial\gamma_{l}=0$ 和 $\partial A_{l} /\partial \delta_{l}=0$ 求得对应 Lagrange 函数关于 $\gamma_l$ 和 $\delta_l$ 的最优解 $\gamma_l^*$ 和 $\delta_l^*$ ，即
$$
\gamma_{l}^{}=\frac{\left(\sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right)^{2}}{J \sigma^{2}+\sum_{l^{\prime} \neq l}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}
$$
和
$$
\delta_{l}^{}=\frac{\left(\sum_{m, n} \mathrm{M}{m, n} c{m, n}^{l}\right) \sqrt{1+\gamma_{l}}}{J \sigma^{2}+\sum_{l^{\prime}=1}^{L}\left|\sum_{m, n} \mathrm{M}{m, n} b{m, n}^{l, l^{\prime}}\right|^{2}}
$$
接着引入松弛变量 $\lambda_{m,n}$ 将问题 $(2)$ 的不等式约束条件转化为等式约束条件并加入目标函数，得到新的 Lagrange 函数
$$
L(\mathrm{M}{m,n},\boldsymbol{\lambda})=\sum{l=1}^{L} A_{l}-\sum_{m, n} \lambda_{m, n}\left(\mathrm{M}{m, n}^{2}-\mathrm{M}{m, n}\right)
$$
最后令 $\partial L / \partial \mathrm{M}{m, n}=0$ 即可得到 ${\mathrm{M}{m,n}^*}$ 。此外，由于函数 $L(\mathrm{M}{m,n},\boldsymbol{\lambda})$ 对 $\lambda{m,n}$ 求导无法求解，因此 $\lambda_{m,n}$ 的更新可以利用次梯度法。对问题 $(2)$ 的求解是一系列交替迭代过程，具体如下：
参考文章
- Deng R, Di B, Zhang H, et al. Reconfigurable Holographic Surface Enabled Multi-User Wireless Communications: Amplitude-Controlled Holographic Beamforming[J]. IEEE Transactions on Wireless Communications, 2022.
- Shen K, Yu W. Load and interference aware joint cell association and user scheduling in uplink cellular networks[C]//2016 IEEE 17th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC). IEEE, 2016: 1-5.