前言

在上一篇博客中， 我们介绍了这篇文章 Weighted Sum-Rate Optimization for Intelligent Reflecting Surface Enhanced Wireless Networks 的系统建模和使用分式规划方法对问题的简化。 上一篇的遗留问题是， 具体如何对 IRS 矩阵进行优化。 作者提出了多种算法， 在本篇中会一一介绍， 比如以之命名本篇的ADMM。

最近点投影

通过分式规划， IRS波束成形问题最终可以变成求解如下的子问题：

$$\begin{array}{rl}(\mathrm{P}4a)\underset{\mathbf{\theta }}{\max }& f_{4a}(\mathbf{\theta })\\ \text{ s.t. }& {\left|{\theta }_n\right|}^2\in \mathcal{F},\forall n=1,\cdots ,N,\end{array}$$

• 理想场景： 智能反射面单元对入射信号可以进行幅度和相位的完美调整， 因此唯一的限制就是能量守恒约束， 即：
  $${\mathcal{F}}_1=\left\{{{\theta }_n||{\theta }_n|}^2\le 1\right\}$$
• 连续相移： 这也是最常见的假设。 认为IRS单元只起到一个相移的作用， 且假设相位可取连续的任意值。 因此， 对应为：
  $${\mathcal{F}}_2=\left\{{\theta }_n\mid {\theta }_n=e^{j{\phi }_n},{\phi }_n\in [0,2\pi )\right\}$$
• 离散相移： 顾名思义， 相较于 ${\mathcal{F}}_2$， 只有有限个相位可以选取， 即：
  $${\mathcal{F}}_3=\left\{{\theta }_n\mid {\theta }_n=e^{j{\phi }_n},{\phi }_n\in \left\{0,\frac{2\pi }{\tau },\cdots ,\frac{2\pi (\tau -1)}{\tau }\right\}\right\}$$

其中，
$$f_{4a}(\mathbf{\theta })=-{\mathbf{\theta }}^{\mathrm{H}}\mathbf{U}\mathbf{\theta }+2\mathrm{Re}\left\{{\mathbf{\theta }}^{\mathrm{H}}\mathbf{\nu }\right\}$$

这里 $\mathbf{U}$ 是半正定已知矩阵， $\mathbf{v}$是已知向量。 显然可知， $f_{4a}$ 是一个关于 $\theta$ 的凹函数。那么如果当 $\mathcal{F}$为凸集时 （$\mathcal{F}$ 的定义见上方）， 则可以通过 SDR 方法， 直接进行求解。 然而 SDR 方法有个较大的问题在于， 复杂度过高， 且存在一定的性能损失。 因此作者旨在提出更先进的算法。 由于 ${\left|{\theta }_n\right|}^2\in {\mathcal{F}}_1$ 是凸集， 而 ${\left|{\theta }_n\right|}^2\in {\mathcal{F}}_2$ 和 ${\left|{\theta }_n\right|}^2\in {\mathcal{F}}_3$ 并不是， 因此作者的思想是， 先以 ${\left|{\theta }_n\right|}^2\in {\mathcal{F}}_1$ 求解问题， 然后将该解投影到 ${\mathcal{F}}_2$ 和 ${\mathcal{F}}_3$上来取得一个次优解。 因此， 这个算法也被命名为 Nearest Point Projection (NPP)。

循着这个逻辑， 限制条件先成为下面这个凸集的形式，即：
$${\left|{\theta }_n\right|}^2\le 1,\forall n=1,\cdots ,N$$
可以等价地写为：
$${\mathbf{\theta }}^{\mathrm{H}}{\mathbf{e}}_n{\mathbf{e}}_n^{\mathrm{H}}\mathbf{\theta }\le 1,\forall n=1,\cdots ,N\text{\hspace{1em}(1)}$$
其中 $e_n$ 是 elementary vector， 即只有第 $n$ 个元素为1， 其余为0。 那么通过拉格朗日乘子法，把限制条件写入到目标函数中去， 得到拉格朗日函数为：
$$\mathcal{G}(\mathbf{\theta },\mathbf{\lambda })=f_{4a}(\mathbf{\theta })-\sum _{n=1}^N{\lambda }_n\left({\mathbf{\theta }}^{\mathrm{H}}{\mathbf{e}}_n{\mathbf{e}}_n^{\mathrm{H}}\mathbf{\theta }-1\right)$$
其中 $\lambda \ge 0$ 确保 $\mathcal{G}$ 是 $f_{4a}$的上界 （${\mathbf{\theta }}^{\mathrm{H}}{\mathbf{e}}_n{\mathbf{e}}_n^{\mathrm{H}}\mathbf{\theta }-1\le 0$）。那么 通过 拉格朗日对偶法 Lagrange dual decomposition(LDD)， 转换为求解对偶问题如下：
( P 4 b ) min ⁡ λ L ( λ ) = max ⁡ θ { G ( θ , λ ) }  s.t.  λ n ≥ 0 , ∀ n = 1 , ⋯   , N , \begin{aligned} (\mathrm{P} 4 b) \quad\min _{\boldsymbol{\lambda}} & \quad\mathcal{L}(\boldsymbol{\lambda})=\max _{\boldsymbol{\theta}}\{\mathcal{G}(\boldsymbol{\theta}, \boldsymbol{\lambda})\} \\ \text { s.t. } & \lambda_{n} \geq 0, \quad \forall n=1, \cdots, N, \end{aligned} (P4b)λmin​ s.t. ​L(λ)=θmax​{ G(θ,λ)}λn​≥0,∀n=1,⋯,N,​
由于 $f_{4a}$ 本身是凸函数且满足 Slater 条件， 因此对偶问题的解也即原问题的解 (对偶间隙为0）。 （这一块的知识可以参见这篇博客 【凸优化】关于 KKT 条件 及其最优性）同时， $\theta$ 的解可以直接得出， 仍是对其求导取0， 得到：
$${\mathbf{\theta }}^{\circ }={\left(\sum _{n=1}^N{\lambda }_n{\mathbf{e}}_n{\mathbf{e}}_n^{\mathrm{H}}+\mathbf{U}\right)}^{-1}\mathbf{v}$$
根据KKT条件， 再将这个表达式带回到 (1)中， 就变成了一个 $\lambda$ 的方程， 并可以通过椭球法 (ellipsoid method) 进行求解。 这也是使用拉格朗日对偶方法来求解带约束凸问题的范式。

有了在 ${\mathcal{F}}_1$约束下的闭式解， 再进行投影就非常简单了 ${\theta }_n^{\bullet }={\mathrm{Pj}}_{\mathcal{F}}\left({\theta }_n^{\circ }\right)$：

当 $\mathcal{F}={\mathcal{F}}_2$时， $\angle {\theta }_n^{\bullet }=\angle {\theta }_n^{\circ }$
当 $\mathcal{F}={\mathcal{F}}_3$时， ∠ θ n ∙ = arg ⁡ min ⁡ ϕ n ∈ { 0 , 2 π τ , ⋯   , 2 π ( τ − 1 ) τ } ∣ ϕ n − ∠ θ n ∘ ∣ . \angle \theta_{n}^{\bullet}=\arg \min _{\phi_{n} \in\left\{0, \frac{2 \pi}{\tau}, \cdots, \frac{2 \pi(\tau-1)}{\tau}\right\}}\left|\phi_{n}-\angle \theta_{n}^{\circ}\right| . ∠θn∙​=argminϕn​∈{ 0,τ2π​,⋯,τ2π(τ−1)​}​∣ϕn​−∠θn∘​∣.

很显然， 这样的优化是次优的， 且显见有性能损失。 因此， 还需要对算法进一步优化。

元素迭代

这个算法的思路非常简单， 由于限制条件都是针对 $\theta$ 的单一元素的（和其他元素并不耦合）， 因此一个直接的想法就是可以固定向量中的其余元素，单独优化一个元素， 并循环往复进行迭代。

这样做的好处就在于， 此时限制条件极易处理了。 由于这个方法在HBF问题中也极为常用， 因此这里就不展开赘述了。 感兴趣的读者可以自行参考原文，很通俗易懂。 我们重点讲 ADMM 算法。

ADMM

本文是一个ADMM算法非常非常经典的应用， 强调推荐想学习这个算法的人都可以来看看这个实例。 这里我推荐另外一些资料， 首先就是引用过万的 凸优化宗师 Boyd 的 巨作 Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers， 重点看前五章的内容， 再来看本文的实例就更得心应手一些。 然后推荐另一篇 毫米波信道估计的文章 Wideband MIMO Channel Estimation for Hybrid Beamforming Millimeter Wave Systems via Random Spatial Sampling， 也是使用了 ADMM 算法， 可以作为另一个 深入理解的 实例 。

关于 ADMM 的 最基本思想， 在 ADMM算法简介 一文中， 已经做了基本的介绍。 知乎上也有不错的相关回答。 建议大家先了解其基本概念后， 再往下看。 那么 ADMM 一种常见的使用， 就是应对 有约束的 问题。 具体而言， 对于如下问题：
$$\begin{array}{ll}\mathrm{minimize}& f(x)\\ \text{ subject to }& x\in \mathcal{C}\end{array}$$
可以将问题等价地写为：
$$\begin{array}{ll}\mathrm{minimize}& f(x)+g(z)\\ \text{ subject to }& x-z=0\end{array}$$
这里 $g(z)$ 为 $\mathcal{C}$ 的 示性函数 (indicator function)。示性函数很简单， 就是 当 $z\in \mathcal{C}$ 时， $g(z)=0$， 否则 $g(z)=\infty$. 而如果了解ADMM算法的话， 可以知道上面这个等效问题，就是ADMM的标准形式。

回到论文中， 对于 (P4a) 这个问题 （本文最开始的那个优化问题）， 我们同样可以用类似的思路， 将其转化为：
$$\begin{array}{ll}\mathrm{maximize}& f_{4a}(\mathbf{q})-{\sum }_{n=1}^{N}g([\mathbf{\theta }{]}_n)\\ \text{ subject to }& \mathbf{q}=\mathbf{\theta }\end{array}$$
这里由于问题是最大化问题， 所以形式稍有不同， 但思想是完全一样可以直接拓展的。 $g$ 此处是 $\mathcal{F}$ 的示性函数。 那么其对应的 拉格朗日增广函数为：
$$\begin{array}{rl}\mathcal{G}\left(\mathrm{q},\theta ,{\lambda }_{\mathrm{R}},{\lambda }_{\mathrm{I}}\right)=& -q^{\mathrm{H}}Uq-\sum _{n=1}^N{1}_{\mathcal{F}}\left({\theta }_n\right)-\frac{\mu }{2}\Vert \mathrm{q}-\theta {\Vert }_2^2+\mathrm{Re}\left\{2q^{\mathrm{H}}\nu +{\left({\lambda }_{\mathrm{R}}+j{\lambda }_{\mathrm{I}}\right)}^{\mathrm{H}}(\mathrm{q}-\theta )\right\}\end{array}$$
其中 ${\mathbf{\lambda }}_{\mathrm{R}}={\left[{\lambda }_{\mathrm{R},1},\cdots ,{\lambda }_{\mathrm{R},N}\right]}^{\mathrm{T}}$ 和 ${\mathbf{\lambda }}_{\mathrm{I}}={\left[{\lambda }_{\mathrm{I},1},\cdots ,{\lambda }_{\mathrm{I},N}\right]}^{\mathrm{T}}$ 是分别对应于 Re ⁡ { q − θ } = 0 \operatorname{Re}\{\mathrm{q}-\theta\}=0 Re{ q−θ}=0 和 Im ⁡ { q − θ } = 0 \operatorname{Im}\{\mathrm{q}-\theta\}=0 Im{ q−θ}=0 两个限制的 拉格朗日系数。 $-\frac{\mu }{2}\Vert \mathrm{q}-\theta {\Vert }_2^2$ 是惩罚项。 至此， 我们开始以 $\mathcal{G}$ 为目标进行求解这一对偶问题如下：
min ⁡ λ R , λ I L ( λ R , λ I ) = max ⁡ θ , q { G ( q , θ , λ R , λ I ) } \min _{\lambda_{\mathrm{R}}, \lambda_{\mathrm{I}}} \mathcal{L}\left(\lambda_{\mathrm{R}}, \lambda_{\mathrm{I}}\right)=\max _{\theta, q}\left\{\mathcal{G}\left(\mathbf{q}, \theta, \lambda_{\mathrm{R}}, \lambda_{\mathrm{I}}\right)\right\} λR​,λI​min​L(λR​,λI​)=θ,qmax​{ G(q,θ,λR​,λI​)}

如果 $\mathcal{F}={\mathcal{F}}_1$， 那么原问题和对偶问题的最优解是一致的， 即没有 duality gap. 否则， 是存在一定最优性损失的。 这个可以参考 博客 【凸优化】关于 KKT 条件 及其最优性。 接下来， 通过 ADMM 算法求解 该对偶问题， 为：
$$\begin{array}{rl}& {\theta }^{t+1}=\arg \underset{\theta }{\max }\mathcal{G}\left({\mathrm{q}}^t,\theta ,{\bar{\lambda }}^t\right)\\ & {\mathrm{q}}^{t+1}=\arg \underset{\mathrm{q}}{\max }\mathcal{G}\left(\mathrm{q},{\theta }^{t+1},{\bar{\lambda }}^t\right)\\ & {\bar{\lambda }}^{t+1}={\bar{\lambda }}^t-\mu \left({\mathrm{q}}^{t+1}-{\theta }^{t+1}\right)\end{array}$$
其中， $\bar{\lambda }={\lambda }_{\mathrm{R}}+j{\lambda }_{\mathrm{I}}$， $t$ 代表迭代次数。 可以看到实质上则是固定其余变量优化单一变量的 交替优化方法。

对于第二步， 这是一个关于 $\mathbf{q}$ 的凸函数， 因此很容易用求导得到闭式解：
$${\mathbf{q}}^{t+1}={\left(2\mathbf{U}+\mu {\mathbf{I}}_N\right)}^{-1}\left(2\mathbf{v}+{\bar{\lambda }}^t+\mu {\theta }^{t+1}\right)$$
关键我们看第一步， 把 $\mathcal{G}$ 中 与 $\theta$ 相关的项取出， 问题可写为：
$$\underset{\theta }{\max }-\frac{\mu }{2}\Vert {\mathrm{q}}^t-\theta {\Vert }_2^2+\mathrm{Re}\left\{{\left({\lambda }_{\mathrm{R}}^t+j{\lambda }_{\mathrm{I}}^t\right)}^{\mathrm{H}}({\mathrm{q}}^t-\theta )\right\}-\sum _{n=1}^{N}g([\mathbf{\theta }{]}_n)$$
通过加入无关的常数项, 目标函数可以改写为：
$$-\frac{\mu }{2}(\Vert q^t-\frac{1}{\mu }{\lambda }^t-\theta {\Vert }^2)-\sum _{n=1}^{N}g([\mathbf{\theta }{]}_n)$$

要想最大化上式， 结果为：
$${\theta }^{t+1}=\mathrm{P}{\mathrm{j}}_{\mathcal{F}}\left({\mathrm{q}}^t-\frac{1}{\mu }{\bar{\lambda }}^t\right)$$
其中 $\mathrm{P}\mathrm{j}$代表投影操作。 这里解释下为什么是这个解： 首先必须满足 $\theta \in \mathcal{F}$， 否则由于示性函数的存在， 目标函数直接变为 $-\infty$。 在看第一项， 代表的物理意义就是， 寻找离 向量 $q^t-\frac{1}{\mu }{\lambda }^t$ 最近的向量。 结合起来就变为： 寻找 在 $\mathcal{F}$中的， 离 向量 $q^t-\frac{1}{\mu }{\lambda }^t$ 最近的向量， 那这不正是投影操作的定义么！ 因此：

• When ${\theta }_n\in {\mathcal{F}}_1$ :
  $${\theta }_n^{t+1}=\frac{{\bar{\theta }}_n}{\left|{\bar{\theta }}_n\right|}\min \left\{1,\left|{\bar{\theta }}_n\right|\right\}$$
• When ${\theta }_n\in {\mathcal{F}}_2$ :
  $$\angle {\theta }_n^{t+1}=\angle {\bar{\theta }}_n$$
• When ${\theta }_n\in {\mathcal{F}}_3$ :
  ∠ θ n t + 1 = arg ⁡ min ⁡ φ n ∈ { 0 , 2 π τ , ⋯   , 2 π ( τ − 1 ) τ } ∣ φ n − ∠ θ ˉ n ∣ \angle \theta_{n}^{t+1}=\arg \min _{\varphi_{n} \in\left\{0, \frac{2 \pi}{\tau}, \cdots, \frac{2 \pi(\tau-1)}{\tau}\right\}}\left|\varphi_{n}-\angle \bar{\theta}_{n}\right| ∠θnt+1​=argφn​∈{ 0,τ2π​,⋯,τ2π(τ−1)​}min​∣∣​φn​−∠θˉn​∣∣​
  至此， 可以用ADMM对问题进行求解。 在这个例子中我们可以看到， 作为非凸限制的 ${\mathcal{F}}_2$ 和 ${\mathcal{F}}_3$， 可以通过ADMM的方式， 简单地用投影算子解决， 这不得不说是一种算是求解特定非凸问题的利刃， 值得大家掌握。