更多精彩内容请关注微信公众号 ‘优化与算法 ’
前言
在数学优化中，分数规划是线性分式规划的推广。分数规划中的目标函数是两个函数的比值，这两个函数通常是非线性的。要优化的比值通常描述系统的某种效率。
1. Concave-convex FP问题
1.1 基本形式
一维问题。符号说明：用R表示实数集，用R+表示非负实数集，再用R++表示严格正实数集，用C表示复数集，用S++表示对称正定矩阵集。(mathcal{X}subseteqmathbb{R}^{d}(dinmathbb{N})) ，A为非负函数(A(mathbf{x}):mathbb{R}^{d}rightarrowmathbb{R}_{+}) ，B为正函数(B(mathbf{x}):mathbb{R}^{d}rightarrowmathbb{R}_{++})
[begin{array}{l} mathop {{rm{maximize}}}limits_{bf{x}} frac{{A({bf{x}})}}{{B({bf{x}})}}\ {rm{subject to }}{bf{x}} in {cal X} end{array}]
二次变换等效形式如下。这种构造有几个性质：分子与分母解耦、最优解与原问题等效、目标函数与原问题等效（比前一个性质更强，适用于多比率问题）、目标函数concave.
[mathop {{rm{maximize}}}limits_{{bf{x}},{mkern 1mu} y} quad ;2ysqrt {A({bf{x}})} - {y^2}B({bf{x}})\ {rm{subject to }}{bf{x}} in {cal X},;{kern 1pt} y in mathbb{R}. ]
当满足以下条件时，此FP问题为concave-convex ：（1）分子(A_{m}(mathbf{x})) 都是concave；（2）分母(B_{m}(mathbf{x})) 都convex；（3）约束集(mathcal{X}) 是由有限个不等式约束表示的标准形式的非空凸集。
一维FP concave-convex问题算法
步骤1：找到(mathbf{x}) 可行解，并将原问题做二次变换等效。
步骤2：由(y_{m}^{star}=frac{sqrt{A_{m}(mathbf{x})}}{B_{m}(mathbf{x})},;forall m=1,ldots,M.) 更新所有(y_{m}) ，
步骤3：将(y_{m}) 代入等效问题，求解关于(mathbf{x}) 的concave问题，更新(mathbf{x}) 。
步骤4：重复步骤2和3，直至收敛。（本算法确保可收敛到一个stationary point）
传统的Dinkelbach’s变换可以比所提出的二次变换更快地收敛，但前者的使用仅限于单个比率问题，而后者能够处理多个比率问题。
1.2 比率和问题 sum-of-ratios
原问题：
[underset{mathbf{x}}{{text{maximize}}}quad sum_{m=1}^{M}frac{A_{m}(mathbf{x})}{B_{m}(mathbf{x})}\ {text{subject to}}quad mathbf{x}inmathcal{X}]
等效问题：
[underset{mathbf{x},,mathbf{y}}{{text{maximize}}}quad sum_{m=1}^{M}left(2y_{m}sqrt{A_{m}(mathbf{x})}-y_{m}^{2}B_{m}(mathbf{x})right)\ {text{subject to}}quad mathbf{x}inmathcal{X},;y_{m}inmathbb{R}. ]
若满足concave-convex条件，使用算法1求解。
1.3 Max-min Ratio
原问题：
[underset{mathbf{x}}{{text{maximize}}}quad min_{m}leftlbrace frac{A_{m}(mathbf{x})}{B_{m}(mathbf{x})}rightrbrace \ text{subject to}quad mathbf{x}inmathcal{X} ]
等效问题：
[underset{mathbf{x},,mathbf{y},,z}{{text{maximize}}}quad z\ {text{subject to}}quad mathbf{x}inmathcal{X},;y_{m}inmathbb{R},;zinmathbb{R}\ quad 2y_{m}sqrt{A_{m}(mathbf{x})}-y_{m}^{2}B_{m}(mathbf{x})geq z,;forall m. ]
若满足concave-convex条件，使用算法1求解。
1.4 多维问题
MIMO系统中，分子是向量，分母是矩阵的多维复数情况下考虑FP。(mathbf{a}_{m}(mathbf{x}):mathbb{C}^{d_{1}}rightarrowmathbb{C}^{d_{2}}) ,(mathbf{B}_{m}(mathbf{x}):mathbb{C}^{d_{1}}rightarrowmathbb{S}_{++}^{d_{2}times d_{2}}) ,(mathbf{a}_{m}^{dagger}) 为(mathbf{a}_{m}(mathbf{x})) 共轭转置（矩阵同理），(mathbf{B}_{m}^{-1}) 为矩阵的逆。
原问题：
[begin{array}{l} mathop {{rm{maximize}}}limits_{bf{x}} sumlimits_{m = 1}^M {{bf{a}}_m^ + } ({bf{x}}){bf{B}}_m^{ - 1}({bf{x}}){{bf{a}}_m}({bf{x}})\ quad {rm{subject}}quad {rm{to}}quad {bf{x}} in X end{array}]
等效问题：
[mathop {max }limits_{{bf{x}},{kern 1pt} {bf{y}}} sumlimits_{m = 1}^M {left( {2{mathop{rm Re}nolimits} { {bf{y}}_m^ {dagger} {{bf{a}}_m}({bf{x}})} - {bf{y}}_m^ {dagger} {{bf{B}}_m}({bf{x}}){{bf{y}}_m}} right)} \ {rm{subject to }}{bf{x}} in {cal X},;{{bf{y}}_m} in {mathbb{C}^{{d_2}}} ]
若满足concave-convex条件，该问题也可使用算法1求解，步骤2替换为(mathbf{y}_{m}^{star}=(mathbf{B}_{m}(mathbf{x}))^{-1}mathbf{a}_{m}(mathbf{x})) 即可。
2. FP的拉格朗日对偶变换
当FP不满足concave-convex条件时，比如约束集(mathcal{X}) 非凸，即(mathbf{x}) 含有离散变量时，可用拉格朗日对偶变换（Lagrangian
2.1 一维问题
原问题：
[begin{aligned}underset{mathbf{x}}{text{maximize}}quad & sum_{m=1}^{M}w_{m}logleft(1+frac{A_{m}(mathbf{x})}{B_{m}(mathbf{x})}right)\ text{subject to}quad & mathbf{x}inmathcal{X} end{aligned} ]
等效问题：加入了辅助变量(gamma_{m})
[begin{aligned}underset{mathbf{x},,boldsymbol{gamma}}{{text{maximize}}}quad & f_{r}(mathbf{x},boldsymbol{gamma})\ {text{subject to}}quad & mathbf{x}inmathcal{X} end{aligned} ]
[begin{aligned}f_{r}(mathbf{x},boldsymbol{gamma})=sum_{m=1}^{M}w_{m}log,(1+gamma_{m})-sum_{m=1}^{M}w_{m}gamma_{m}+underbrace{sum_{m=1}^{M}frac{w_{m}(1+gamma_{m})A_{m}(mathbf{x})}{A_{m}(mathbf{x})+B_{m}(mathbf{x})}}_{text{Sum-of-ratio term}}end{aligned} ]
求解思路：对于固定的(mathbf{x}) ，通过(partial f_{r}/partialgamma_{i}=0) 可以求出(gamma_{i}^{star}) 。然后对后面的分数项，做二次变换等效，引入辅助变量(y_{m}) ，得到另一个目标函数(f_{q}(mathbf{x},boldsymbol{gamma},mathbf{y})) ，通过(partial f_{q}/partial y_{i}=0) 可以求出(y_{i}^{star}) 。这样就只剩下变量组(mathbf{x}) ，此时目标函数不含有分数项，可能可以得到一些闭式解，或者(mathbf{x}) 中的部分变量有闭式解，其他变量（如离散项）仍需要再找解法。
具体而言（从所给例子中得到），结合(4)，得到：
[partial f_{r}/partialgamma_{m}=0quadrightarrowquadgamma_{m}^{star}=A_{m}(mathbf{x})/B_{m}(mathbf{x}) ]
[f_{q}(mathbf{x},boldsymbol{gamma},mathbf{y})=underbrace{sum_{m=1}^{M}w_{m}log,(1+gamma_{m})-sum_{m=1}^{M}w_{m}gamma_{m}}_{f_{r}{的前两项}}+sum_{m=1}^{M}2y_{m}sqrt{underbrace{w_{m}(1+gamma_{m})A_{m}(mathbf{x})}_{text{分式项的分子A'}}}-y_{m}^{2}underbrace{left(A_{m}(mathbf{x})+B_{m}(mathbf{x})right)}_{text{分式项的分母B'}} ]
[partial f_{q}/partial y_{i}=0quadrightarrowquad y_{m}^{star}=frac{sqrt{A'}}{B'}=frac{sqrt{w_{m}(1+gamma_{m})A_{m}(mathbf{x})}}{A_{m}(mathbf{x})+B_{m}(mathbf{x})} ]
2.2多维问题
原问题：
[begin{aligned}underset{mathbf{x}}{{text{maximize}}} & quadsum_{m=1}^{M}w_{m}logleft(1+boldsymbol{alpha}_{m}^{dagger}(mathbf{x})mathbf{B}_{m}^{-1}(mathbf{x})boldsymbol{alpha}_{m}(mathbf{x})right)\ {text{subject to}} & quadmathbf{x}inmathcal{X} end{aligned} ]
等效问题：
[begin{aligned}underset{mathbf{x},,boldsymbol{gamma}}{{text{maximize}}}quad & f_{r}(mathbf{x},boldsymbol{gamma})\ {text{subject to}}quad & mathbf{x}inmathcal{X} end{aligned} ]
[f_{r}(mathbf{x},boldsymbol{gamma})=sum_{m=1}^{M}w_{m}log,(1+gamma_{m})-sum_{m=1}^{M}w_{m}gamma_{m}+sum_{m=1}^{M}w_{m}(1+gamma_{m})boldsymbol{alpha}_{m}^{dagger}(mathbf{x})(boldsymbol{alpha}_{m}(mathbf{x})boldsymbol{alpha}_{m}^{dagger}(mathbf{x})+mathbf{B}_{m}(mathbf{x}))^{-1}boldsymbol{alpha}_{m}(mathbf{x}) ]
求解思路：同上。
具体而言（从所给例子中得到）：
[partial f_{r}/partialgamma_{m}=0quadrightarrowquadgamma_{m}^{star}=boldsymbol{alpha}_{m}^{dagger}(mathbf{x})mathbf{B}_{m}^{-1}(mathbf{x})boldsymbol{alpha}_{m}(mathbf{x}) ]
注意，(f_{r}) 中的“分子”是(w_{m}(1+gamma_{m})boldsymbol{alpha}_{m}^{dagger}(mathbf{x})boldsymbol{alpha}_{m}(mathbf{x})) ，对应的(boldsymbol{alpha'}_{m}(mathbf{x})=sqrt{w_{m}(1+gamma_{m})}boldsymbol{alpha}_{m}(mathbf{x})) （记得常数项要开根号），而“分母”是(mathbf{B'}_{m}(mathbf{x})=boldsymbol{alpha}_{m}(mathbf{x})boldsymbol{alpha}_{m}^{dagger}(mathbf{x})+mathbf{B}_{m}(mathbf{x})) ，根据(8)，得到：
[f_{q}(mathbf{x},boldsymbol{gamma},mathbf{y})=underbrace{sum_{m=1}^{M}w_{m}log,(1+gamma_{m})-sum_{m=1}^{M}w_{m}gamma_{m}}_{f_{r}{的前两项}}+sum_{m=1}^{M}left(2{text{Re}}leftlbrace mathbf{y}_{m}^{dagger}mathbf{boldsymbol{alpha}'}_{m}(mathbf{x})rightrbrace -mathbf{y}_{m}^{dagger}mathbf{B'}_{m}(mathbf{x})mathbf{y}_{m}right) ]
[mathbf{y}_{m}^{star}=(mathbf{B'}_{m}(mathbf{x}))^{-1}mathbf{boldsymbol{alpha}'}_{m}(mathbf{x}) ]
3. 具体例子
3.1-3.3都只需要用第一章concave-convex方法求解，3.4-3.6需要用到第二章的拉格朗日对偶变换，而且具体解(mathbf{x}) 时需要对离散变量单独开发算法。
3.1 多小区SISO能量分配
第一个例子是具有一组单天线基站（BSs）(mathcal{B}) 的下行链路SISO蜂窝网络的经典功率控制问题，每个基站服务于单天线用户。设(h_{i,j}in) C是从BS(sigma^{2}) 为加性高斯白噪声（AWGN）功率电平。为每个BS i引入可变(p_{i}) 作为其发射功率电平，受Pmax功率预算的约束。第i个用户的速率
[R_{i}=logleft(1+frac{|h_{i,i}|^{2}p_{i}}{sum_{jne i}|h_{i,j}|^{2}p_{j}+sigma^{2}}right) ]
优化问题如下。
[begin{aligned}underset{mathbf{p}}{text{maximize}}quad & f_{o}(mathbf{p})=sum_{iinmathcal{B}}w_{i}R_{i}\ text{subject to}quad & 0leq p_{i}leq P_{max},;forall iinmathcal{B}. end{aligned} ]
先说明，对于两种等效方法，都可以使用简单的初始值，比如能量平均分配。此问题可以拓展到多载波(R_{i}=sum_{t=1}^{T}frac{1}{T}logleft(1+frac{|h_{i,i}^{t}|^{2}p_{i}^{t}}{sum_{jne i}|h_{i,j}^{t}|^{2}p_{j}^{t}+sigma^{2}}right))
3.1.1 Direct FP
对log里面的分数项做处理，得到直接FP形式如下。直接使用算法1，可以得到(y_{i}^{star}=frac{sqrt{A_{m}(mathbf{x})}}{B_{m}(mathbf{x})}=frac{sqrt{|h_{i,i}|^{2}p_{i}}}{sum_{jne i}|h_{i,j}|^{2}p_{j}+sigma^{2}}) ，代入后用数值方法求解p（剩下的是凸问题），然后迭代。
[f_{q}^{text{DIR}}(mathbf{p},mathbf{y})=sum_{iinmathcal{B}}w_{i}logBigg(1+2y_{i}sqrt{|h_{i,i}|^{2}p_{i}}-y_{i}^{2}Bigg(sum_{jne i}|h_{i,j}|^{2}p_{j}+sigma^{2}Bigg)Bigg) ]
进一步地，只要目标函数（或叫做效用函数）(U_{i}) 是关于(R_{i}) 的nondecreasing concave函数，都可以对(R_{i}) 里面的分数项使用二次变换等效。
3.1.2 拉格朗日对偶变换求闭式解
应用第二部分的拉格朗日对偶变换方法，首先得到下式，
[f_{r}^{{text{CF}}}(mathbf{p},boldsymbol{gamma})=sum_{iinmathcal{B}}w_{i}logleft(1+gamma_{i}right)-sum_{iinmathcal{B}}w_{i}gamma_{i}+sum_{iinmathcal{B}}frac{w_{i}(1+gamma_{i})|h_{i,i}|^{2}p_{i}}{sum_{jinmathcal{B}}|h_{i,j}|^{2}p_{j}+sigma^{2}} ]
上式引入辅助变量的最优解为(gamma_{i}^{star}=frac{A_{m}(mathbf{x})}{B_{m}(mathbf{x})}=frac{|h_{i,i}|^{2}p_{i}}{sum_{jne i}|h_{i,j}|^{2}p_{j}+sigma^{2}}) ，再对最后一项分数项做二次变换，(f_{r}) 的前两项记为(text{const}(boldsymbol{gamma}))
[f_{q}^{text{CF}}(mathbf{p},boldsymbol{gamma},mathbf{y})=sum_{iinmathcal{B}}2y_{i}sqrt{w_{i}(1+gamma_{i})|h_{i,i}|^{2}p_{i}}-sum_{iinmathcal{B}}y_{i}^{2}Bigg(sum_{jinmathcal{B}}|h_{i,j}|^{2}p_{j}+sigma^{2}Bigg)+text{const}(boldsymbol{gamma}) ]
上式引入辅助变量的最优解为(y_{i}^{star}=frac{sqrt{A_{m}(mathbf{x})}}{B_{m}(mathbf{x})}=frac{sqrt{w_{i}(1+gamma_{i})|h_{i,i}|^{2}p_{i}}}{sum_{jinmathcal{B}}|h_{i,j}|^{2}p_{j}+sigma^{2}},;forall iinmathcal{B}.) ，然后(f_{q}) 对(p) 求导，再结合约束条件中(p<P_{max}) ，即可解得
[p_{i}^{star}=minBigglbrace P_{max},frac{y_{i}^{2}w_{i}(1+gamma_{i})|h_{i,i}|^{2}}{big(sum_{jinmathcal{B}}y_{j}^{2}|h_{j,i}|^{2}big)^{2}}Biggrbrace,;forall iinmathcal{B} ]
最后，(gamma_{i}^{star},y_{i}^{star},p_{i}^{star}) 依次迭代，可收敛到最优值。
自行推导(p_{i}^{star}) ：首先可以得到(f_{q}) 中关于(p_{i}) 的一项为：
[f_{q,i}=2y_{i}sqrt{w_{i}(1+gamma_{i})|h_{i,i}|^{2}}sqrt{p_{i}}-sum_{jinmathcal{B}}y_{j}^{2}|h_{j,i}|^{2}cdot p_{i} ]
注意(f_{q}) 后面一项要拆分再合并才得到(f_{q,i}) 的后面一项。此时(f_{q,i}=c_{1}sqrt{p_{i}}/2-c_{2}cdot p_{i}) ，令(partial f_{q,i}/partial p_{i}=c_{1}/sqrt{p_{i}}/2-c_{2}=0) ，则(p_{i}=(c_{1}/c_{2}/4)^{2}) ，就是上式。
3.1.3 结果比较
图中的SCALE是一个modified version of geometric programming (GP)[32].
[32] J. Papandriopoulos and J. S. Evans, “SCALE: A low-complexity
考虑具有一组BS (mathcal{B}) 的下行链路MIMO蜂窝网络。假设每个BS具有M个天线，并且每个用户终端具有N个天线；则经由空间复用每个小区最多支持M个下行链路数据流。设(mathbf{H}_{im,j}inmathbb{C}^{Ntimes M}) 是从({[}BS j{]}) 到 ({[}BS i]) 的第m个数据流中调度的用户的下行链路信道。设σ2是AWGN功率电平。引入变量(mathbf{v}_{im}inmathbb{C}^{M}) 作为其第m个数据流在BS
[R_{im}(mathbf{V})=logBigg(1+mathbf{v}_{im}^{dagger}mathbf{H}_{im,i}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{(j,n)ne(i,m)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)^{-1}mathbf{H}_{im,i}mathbf{v}_{im}Bigg) ]
令(mathbf{V}) 代表所有的({mathbf{v}_{im}}) ，加入权重之后，优化问题如下
[begin{aligned}underset{mathbf{V}}{text{maximize}}quad & sum_{i,m}w_{im}R_{im}(mathbf{V})\ text{subject to}quad & sum_{m=1}^{M}Vertmathbf{v}_{im}Vert_{2}^{2}leq P_{max},;forall iinmathcal{B} end{aligned} ]
3.2.1 Direct FP
使用1.4节中的方法，做二次变换，得到
[f_{q}^{text{DIR}}(mathbf{V},mathbf{Y})=sum_{(i,m)}w_{im}logBigg(1+2text{Re}leftlbrace mathbf{y}_{im}^{dagger}mathbf{H}_{im,i}mathbf{v}_{im}rightrbrace -mathbf{y}_{im}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{(j,n)ne(i,m)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)mathbf{y}_{im}Bigg) ]
根据(mathbf{y}_{m}^{star}=(mathbf{B}_{m}(mathbf{x}))^{-1}mathbf{a}_{m}(mathbf{x})) ，得到下式。然后数值法求解二次变换后的等效问题（关于V是凸问题），迭代求解。
[mathbf{y}_{im}^{star}=Bigg(sigma^{2}mathbf{I}+sum_{(j,n)ne(i,m)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)^{-1}mathbf{H}_{im,i}mathbf{v}_{im} ]
3.2.2 拉格朗日对偶变换求闭式解
与3.1.2类似，只不过是矩阵形式的。首先通过拉格朗日对偶得到(f_{r}) ，再对内部的分式做二次变换得到(f_{q}) .
[f_{r}^{text{CF}}(mathbf{V},boldsymbol{gamma})=sum_{(i,m)}w_{im}Bigg(log(1+gamma_{im})-gamma_{im}+(1+gamma_{im})mathbf{v}_{im}^{dagger}mathbf{H}_{im,i}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{(j,n)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)^{-1}mathbf{H}_{im,i}mathbf{v}_{im}Bigg) ]
[gamma_{im}^{star}=mathbf{v}_{im}^{dagger}mathbf{H}_{im,i}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{(j,n)ne(i,m)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)^{-1}mathbf{H}_{im,i}mathbf{v}_{im} ]
[f_{q}^{text{CF}}(mathbf{V},boldsymbol{gamma},mathbf{Y})=sum_{(i,m)}Bigg(2sqrt{w_{im}(1+gamma_{im})};text{Re}lbracemathbf{v}_{im}^{dagger}mathbf{H}_{im,i}^{dagger}mathbf{y}_{im}rbrace-mathbf{y}_{im}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{(j,n)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)mathbf{y}_{im}Bigg)+text{const}(boldsymbol{gamma}) ]
[mathbf{y}_{im}^{star}=Bigg(sigma^{2}mathbf{I}+sum_{(j,n)}mathbf{H}_{im,j}mathbf{v}_{jn}mathbf{v}_{jn}^{dagger}mathbf{H}_{im,j}^{dagger}Bigg)^{-1}cdotsqrt{w_{im}(1+gamma_{im})}mathbf{H}_{im,i}mathbf{v}_{im} ]
[mathbf{v}_{im}^{star}=Bigg(eta_{i}mathbf{I}+sum_{(j,n)}mathbf{H}_{jn,i}^{dagger}mathbf{y}_{jn}mathbf{y}_{jn}^{dagger}mathbf{H}_{jn,i}Bigg)^{-1}cdotsqrt{w_{im}(1+gamma_{im})}mathbf{H}_{im,i}^{dagger}mathbf{y}_{im} ]
注意(mathbf{v}_{im}^{star}) 中还有一个变量(eta_{i}) ，(eta_{i}) 是为功率约束引入的对偶变量，由（互补松弛）最优确定。文章说这个值可以由二分搜索等方法得到，应该是把(eta_{i}) 代入上式，
[eta_{i}^{star}=minleftlbrace eta_{i}geq0:sum_{m=1}^{M}Vertmathbf{v}_{im}(eta_{i})Vert_{2}^{2}leq P_{max}rightrbrace ]
需要注意的是，此方法和WMMSE等效算法得到的结果是一致的。与前面类似，Direct FP可以得到更好的性能，而Closed-form
自行推导(mathbf{v}_{im}^{star}) ：与3.1.2类似，注意矩阵求导(partialmathbf{b}^{T}mathbf{X}^{T}mathbf{Xc}/partialmathbf{X}=mathbf{X}(mathbf{b}mathbf{c}^{T}+mathbf{c}mathbf{b}^{T})) ，则(partialmathbf{b}^{T}mathbf{X}^{T}mathbf{Xb}/partialmathbf{X}=2mathbf{b}mathbf{b}^{T}mathbf{X}) .(eta_{i}) 是在求解(mathbf{v}_{im}^{star}) 时，把约束考虑进来之后，构造出来的拉格朗日对偶问题引入的辅助变量。(sum_{m=1}^{M}Vertmathbf{v}_{im}Vert_{2}^{2}leq P_{max}) ，可写为(sum_{m=1}^{M}mathbf{v}_{im}^{dagger}mathbf{v}_{im}-P_{max}leq0) ，即(mathrm{tr}{mathbf{V}_{i}^{dagger}mathbf{V}_{i}}-P_{max}leq0) ，
[f_{q,v}^{text{CF}}(mathbf{V},boldsymbol{gamma},mathbf{Y})=f_{q}^{text{CF}}(mathbf{V},boldsymbol{gamma},mathbf{Y})-sum_{i}eta_{i}left(mathrm{tr}{mathbf{V}_{i}^{dagger}mathbf{V}_{i}}-P_{max}right) ]
添加的对偶项求导后为(2eta_{i}mathbf{V}_{i}) .
3.3 能效最大化
跨多个干扰链路的能效最大化是一个更具挑战性的问题。考虑一个空间复用多天线广播信道模型，其中一个发送器配备有M个天线，以向其M个接收器发送单独的数据。假设每个接收机具有N个天线并且支持一个数据流。设(mathbf{H}_{m}inmathbb{C}^{Ntimes M}) 是发送方和第M个接收方之间的信道；设(mathbf{v}_{m}inmathbb{C}^{M}) 是用于传输到第m个接收器的波束形成器。(P_{on}) 是电路的固定功耗。在这种情况下，能源效率最大化问题如下
[begin{aligned}underset{mathbf{V}}{text{maximize}}quad & frac{sum_{m=1}^{M}R_{m}(mathbf{V})}{sum_{m=1}^{M}Vertmathbf{v}_{m}Vert_{2}^{2}+P_{text{on}}}\ text{subject to}quad & sum_{m=1}^{M}Vertmathbf{v}_{m}Vert_{2}^{2}leq P_{max} end{aligned} ]
[R_{m}(mathbf{V})=logBigg(1+mathbf{v}_{m}^{dagger}mathbf{H}_{m}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{nne m}mathbf{H}_{m}mathbf{v}_{n}mathbf{v}_{n}^{dagger}mathbf{H}_{m}^{dagger}Bigg)^{-1}cdotmathbf{H}_{m}mathbf{v}_{m}Bigg) ]
这个问题里，目标函数是一个分式，而(R_{m}) 内部又是一个分式，直接使用两次二次变换等效，使用Direct FP方法求解。仿真表明，在单链路问题下，可以收敛到和Dinkelbach等效方法一致的结果，多链路时Dinkelbach方法不适用。
3.4 多小区SISO上行调度和能量分配
考虑无线蜂窝网络的上行链路，B是部署在网络中的基站（BSs）集合，(mathcal{K}_{i}) 是与BS i关联的用户集合，每个BS(mathcal{K}_{i}) 中的关联用户构成一个小区。在每个时隙中，用户被调度为基于小区的上行链路传输。为了用户调度和功率控制的目的，引入变量(s_{i}inmathcal{K}_{i}) 表示在BS(k) 被调度为上行链路传输，则引入变量(p_{k}) 表示其发射功率电平。设(h_{i,k}inmathbb{C}) 是从用户k到BS(s_{i}) 的理解，SISO场景，基站i一个时刻只能与一个设备通信，(s_{i}) 就是这个设备的编号？比如基站1对设备5，基站2对设备6，那么(s_{1}=5,s_{2}=6)
[begin{aligned}underset{mathbf{s},,mathbf{p}}{text{maximize}}quad & f_{o}(mathbf{s},mathbf{p})=sum_{iin,mathcal{B}}w_{s_{i}}logleft(1+frac{|h_{i,s_{i}}|^{2}p_{s_{i}}}{sum_{jne i}|h_{i,s_{j}}|^{2}p_{s_{j}}+sigma^{2}}right)\ text{subject to}quad & 0leq p_{k}leq P_{max},quad s_{i}inmathcal{K}_{i}cuplbracevarnothingrbrace end{aligned} ]
一种经典的等效方法是
[f_{o}(mathbf{p})=sum_{iin,mathcal{B}}sum_{kin{mathcal{K}}_{i}}w_{k}logbigg(1+frac{|h_{i,k}|^{2}p_{k}}{sum_{k^{prime}ne k}|h_{i,k^{prime}}|^{2}p_{k^{prime}}+sigma^{2}}bigg) ]
主要问题是，由于目标函数的高度非凸性，功率控制算法的驻点对初始条件高度敏感。因此，这类方法存在严重的过早停止问题。如果某个环节在迭代优化的早期阶段被停用，那么它就永远无法在以后的迭代中被重新激活，因为它的局部梯度会强烈阻碍它这样做。使用GP的方法[30]可以改善这点，但只能在高SINR下工作，但是在小区干扰场景中，SINR往往较低。
[f_{r}(mathbf{s},mathbf{p},boldsymbol{gamma})=sum_{iin,mathcal{B}}w_{s_{i}}logleft(1+gamma_{i}right)-sum_{iin,mathcal{B}}w_{s_{i}}gamma_{i}+sum_{iin,mathcal{B}}frac{w_{s_{i}}(gamma_{i}+1)|h_{i,s_{i}}|^{2}p_{s_{i}}}{sum_{j}|h_{i,s_{j}}|^{2}p_{s_{j}}+sigma^{2}} ]
与前面的步骤一样，(gamma_{i}^{star}=frac{|h_{i,s_{i}}|^{2}p_{s_{i}}}{sum_{jne i}|h_{i,s_{j}}|^{2}p_{s_{j}}+sigma^{2}}) ，再对(f_{r}) 分数项做二次变换(f_{q}) ，(y_{i}^{star}=frac{sqrt{w_{s_{i}}(1+gamma_{i})|h_{i,s_{i}}|^{2}p_{s_{i}}}}{sum_{jin,mathcal{B}}|h_{i,s_{j}}|^{2}p_{s_{j}}+sigma^{2}}) ，也可求得(p_{k}^{star}=minleftlbrace P_{max},frac{w_{k}(1+gamma_{i})left|h_{i,k}right|^{2}y_{i}^{2}}{left(sum_{jin,mathcal{B}}left|h_{j,k}right|^{2}y_{j}^{2}right)^{2}}rightrbrace ,;forall kinmathcal{K}_{i}) .
[f_{q}(mathbf{s},mathbf{p},boldsymbol{gamma},mathbf{y})=sum_{iin,mathcal{B}}w_{s_{i}}log,(1+gamma_{i})-sum_{iin,mathcal{B}}w_{s_{i}}gamma_{i}+sum_{iin,mathcal{B}}Bigg(2y_{i}sqrt{w_{s_{i}}(gamma_{i}+1)left|h_{i,s_{i}}right|^{2}p_{s_{i}}}-y_{i}^{2}Bigg(sum_{jin,mathcal{B}}left|h_{i,s_{j}}right|^{2}p_{s_{j}}+sigma^{2}Bigg)Bigg) ]
重写成如下形式，可以看到问题被解耦，具体地说，“每个小区中的调度和功率优化，即（(s_{i}) ，(p_{i}) ），可以在每个小区中独立地完成。即当γ和y固定时，si的优化不依赖于其他sj变量。”（不是很理解，(y) 和(gamma) 的取值不是还和(s_{j}) 有关么？也不算完全解耦，只是这个式子里确实只关注(s_{i}) 就行，而且计算(p_{k}^{star}) 的时候也不用关注(s_{i}) 是哪个。）下式也可以看做一个总的效用函数，(G_{i}(k)({其中计算时}kinmathcal{K}_{i})) 是在BS(D_{j}(k)({其中计算时}knotinmathcal{K}_{j})) 则是通过调度用户k干扰相邻小区j的惩罚。即遍历计算每个用户(k) 的总效用，选最大就完成了(s_{i}) 的优化，不需要对所有((s_{1},s_{2},...)) 调度组合做搜索，复杂度大大降低。在实际应用中，可以使用两阶段调度策略来降低该算法的实现复杂度。我们首先根据潜在用户的权重粗略地选择其子集，然后应用算法对调度决策进行细化。
[f_{q}(mathbf{s},mathbf{p},boldsymbol{gamma},mathbf{y})=sum_{iin,mathcal{B}}Bigg(underbrace{w_{s_{i}}log,(1+gamma_{i})-w_{s_{i}}gamma_{i}-y_{i}^{2}sigma^{2}+2y_{i}sqrt{w_{s_{i}}(gamma_{i}+1)left|h_{i,s_{i}}right|^{2}p_{s_{i}}}}_{G_{i}(s_{i})}-sum_{jin,mathcal{B}}underbrace{y_{j}^{2}left|h_{j,s_{i}}right|^{2}p_{s_{i}}}_{D_{j}(s_{i})}Bigg) ]
[s_{i}^{star}=begin{cases} varnothing, & text{if};max_{kin,mathcal{K}_{i}}Bigglbrace G_{i}(k)-sum_{jne i}D_{j}(k)Biggrbraceleq0\ argmax_{kin,mathcal{K}_{i}} & Bigglbrace G_{i}(k)-sum_{jne i}D_{j}(k)Biggrbrace,;text{otherwise} end{cases} ]
结果：曲线有交叉，怎么就说明FP好了呢？ 主要看低速率的。比如横着看，CDF=0.1时，即对最差的10%用户，FP方法对应的data
假设每个用户配备有N个天线，并且每个BS配备有M个天线。因此，空间复用可以支持每个小区多达M个数据流（但是一些数据流可能具有零吞吐量）。设s_{im}是在BS(mathbf{v}_{k}inmathbb{C}^{N}) 是用户k的发送波束形成器。设(mathbf{H}_{i,k}inmathbb{C}^{Mtimes N}) 是从用户k到BS
[begin{aligned}underset{mathbf{s},,mathbf{V}}{text{maximize}}quad & f_{o}(mathbf{s},mathbf{V} text{subject to}quad & Vertmathbf{v}_{im}Vert_{2}^{2}leq P_{max}\ quad & s_{im}inmathcal{K}_{i}cuplbracevarnothingrbrace end{aligned} ]
[f_{o}(mathbf{s},mathbf{V})=sum_{(i,m)}w_{s_{im}}logleft(1+mathbf{v}_{s_{im}}^{dagger}mathbf{H}_{i,s_{im}}^{dagger}Bigg(sigma^{2}mathbf{I}+sum_{(j,n)ne(i,m)}mathbf{H}_{i,s_{jn}}mathbf{v}_{s_{jn}}mathbf{v}_{s_{jn}}^{dagger}mathbf{H}_{i,s_{jn}}^{dagger}Bigg)^{-1}mathbf{H}_{i,s_{im}}mathbf{v}_{s_{im}}right) ]
问题比较直观，也和3.2与3.4那样先做两次变换，其中
[gamma _{im}^ star = {bf{v}}_{{s_{im}}}^dagger {bf{H}}_{i,{s_{im}}}^dagger {left( {{sigma ^2}{bf{I}} + sumlimits_{(j,n) ne (i,m)} {{{bf{H}}_{i,{s_{jn}}}}} {{bf{v}}_{{s_{jn}}}}{bf{v}}_{{s_{jn}}}^dagger {bf{H}}_{i,{s_{jn}}}^dagger } right)^{ - 1}}{{bf{H}}_{i,{s_{im}}}}{{bf{v}}_{{s_{im}}}} ]
[{bf{y}}_{im}^ star = {({sigma ^2}{bf{I}} + sumlimits_{(j,n)} {{{bf{H}}_{i,{s_{jn}}}}} {{bf{v}}_{{s_{jn}}}}{bf{v}}_{{s_{jn}}}^dagger {bf{H}}_{i,{s_{jn}}}^dagger )^{ - 1}} cdot sqrt {{w_{{s_{im}}}}(1 + {gamma _{im}})} {{bf{H}}_{i,{s_{im}}}}{{bf{v}}_{{s_{im}}}} ]
[{f_r}({bf{s}},{bf{V}},{bf{gamma }}) = sumlimits_{(i,m)} {{w_{{s_{im}}}}} (log (1 + {gamma _{im}}) - {gamma _{im}} + (1 + {gamma _{im}}){bf{v}}_{{s_{im}}}^dag {bf{H}}_{i,{s_{im}}}^dag {({sigma ^2}{bf{I}} + sumlimits_{(j,n)} {{{bf{H}}_{i,{s_{jn}}}}} {{bf{v}}_{{s_{jn}}}}{bf{v}}_{{s_{jn}}}^dag {bf{H}}_{i,{s_{jn}}}^dag )^{ - 1}}{{bf{H}}_{i,{s_{im}}}}{{bf{v}}_{{s_{im}}}}) ]
[{f_q}({bf{s}},{bf{V}},{bf{gamma }},{bf{Y}}) = sumlimits_{(i,m)} {{w_{{s_{im}}}}} log (1 + {gamma _{im}}) - sumlimits_{(i,m)} {{w_{{s_{im}}}}} {gamma _{im}} + sumlimits_{(i,m)} ( 2sqrt {{w_{{s_{im}}}}(1 + {gamma _{im}})} ;{rm{Re}}left{ {{bf{v}}_{{s_{im}}}^dag {bf{H}}_{i,{s_{im}}}^dag {{bf{y}}_{im}}} right} - {bf{y}}_{im}^dag ({sigma ^2}{bf{I}} + sumlimits_{(j,n)} {{{bf{H}}_{i,{s_{jn}}}}} {{bf{v}}_{{s_{jn}}}}{bf{v}}_{{s_{jn}}}^dag {bf{H}}_{i,{s_{jn}}}^dag ){{bf{y}}_{im}}) ]
接下来的问题又是(mathbf{s}) 和(mathbf{V}) 的优化问题。将加权二部匹配的思想引入到这两个变量的联合优化中。首先，由(f_{q}) 可以看出，特定数据流((i,m)) 的(s_{im}) 和(mathbf{v}_{im}) 与其他流的s和v优化是独立的（类似SISO问题中的“解耦”）。如果某个用户(k) 在数据流((i,m)) 中被调度，即(s_{im}=k) ，则用户(k) 关于((i,m)) 的最优发射波束形成器可通过(partial f_{q}/partialmathbf{v}_{s_{im}}=0) 求得，表示为(tau_{k,im}) ，
[boldsymbol{tau}_{k,im}=Bigg(sum_{(j,n)}mathbf{H}_{j,k}^{dagger}mathbf{y}_{jn}mathbf{y}_{jn}^{dagger}mathbf{H}_{j,k}+eta_{k,im}^{star}mathbf{I}Bigg)^{-1}cdotsqrt{w_{k}(1+gamma_{im})}mathbf{H}_{i,k}^{dagger}mathbf{y}_{im} ]
与3.2中的问题类似，由于约束的引入，多了个(eta_{k,im}^{star}) ，通过二分搜索求解(eta_{k,im}^{star}=minlbraceeta_{k,im}geq0:Vertboldsymbol{tau}_{k,im}(eta_{k,im})Vert_{2}^{2}leq P_{max}rbrace)
类似3.4节，根据(f_{q}) 先定义一个将用户(k) 分配给数据流((i,m)) 的效用函数:
[xi_{k,im}=w_{k}log,(1+gamma_{im})-w_{k}gamma_{im}+2sqrt{w_{k}(1+gamma_{im})};text{Re}leftlbrace boldsymbol{tau}_{k,im}^{dagger}mathbf{H}_{i,k}^{dagger}mathbf{y}_{im}rightrbrace -sigma^{2}Vert{mathbf{y}}_{im}Vert_{2}^{2}-sum_{(j,n)}mathbf{y}_{jn}^{dagger}mathbf{H}_{j,k}boldsymbol{tau}_{k,im}boldsymbol{tau}_{k,im}^{dagger}mathbf{H}_{j,k}^{dagger}mathbf{y}_{jn} ]
然后，fq最大化问题简化为以下加权二分匹配问题（背包问题），其中二进制变量(x_{k,im}) 表示用户(k) 是否调度在数据流(i,m)中。每个用户只能用一个流，每个流只能调度一个用户。通过使用例如匈牙利算法[6]和拍卖算法[7]的具有多项式时间计算复杂度的现有算法，计算复杂度为(O((K+M)^ 3)) 。此外，由于在实践中，匹配权重ξk，im总是以有限精度进行评估，因此在这种有限精度的情况下，可以使用[34]中的算法将匹配的复杂度降低到(O((K+M)^ 2)) .
[begin{aligned}underset{mathbf{x}}{text{maximize}}quad & sum_{kin,mathcal{K}_{i}}sum_{m=1}^{N}xi_{k,im}x_{k,im}\ text{subject to}quad & sum_{kin,mathcal{K}_{i}}x_{k,im}leq1,;forall m\ quad & sum_{m=1}^{N}x_{k,im}leq1,;forall k\ quad & x_{k,im}inleftlbrace 0,1rightrbrace , end{aligned} ]
如果考虑预编码权值是离散的，考虑码本
[{mathcal{V}}=leftlbrace boldsymbol{phi}_{1},boldsymbol{phi}_{2},cdots,boldsymbol{phi}_{|{mathcal{V}}|}rightrbrace ]
其中(boldsymbol{phi}_{n}inmathbb{C}^{N}) 为一个特定预编码。此时，用户(k) 关于((i,m)) 的最优预编码改为（可通过搜索得到，复杂度(O(|V|)))
[boldsymbol{tau}_{k,im}=argmax_{{mathbf{v}}in{mathcal{V}}}left{ 2sqrt{w_{k}(1+gamma_{im})};text{Re}leftlbrace {mathbf{v}}^{dagger}mathbf{H}_{i,k}^{dagger}mathbf{y}_{im}rightrbrace -sum_{(j,n)}mathbf{y}_{jn}^{dagger}mathbf{H}_{j,k}{mathbf{v}}{mathbf{v}}^{dagger}mathbf{H}_{j,k}^{dagger}mathbf{y}_{jn}right} ]
再用背包问题求解，也是一样的。如果先按老方法优化，然后找一个距离最近的波束，即(boldsymbol{tau}_{k,im}=argmin_{boldsymbol{phi}in,{mathcal{V}}}Vertboldsymbol{phi}-tilde{{mathbf{v}}}_{im}Vert_{2}) ，这样能降低复杂度到(O(log|V|)) ，虽然看上去是启发式的搜索，但论文里证明了能到最优。
再然后就是和WMMSE方法的比较，对信道差的用户提供的速率比WMMSE好，总效用函数高10%。在K>>M的情况下，WMMSE有更高的communication complexity。在K>>M和N的情况下，FP方法的计算复杂度也要更低（特别是使用更高效的背包问题求解方法后）。
更多精彩内容请关注订阅号优化与算法 和加入QQ讨论群1032493483获取更多资料
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/2.jpg&w=218&h=124&zc=1)
