1-《Secure Over-the-Air Computation for Wireless Sensor Network》

P 1 : min ⁡ c , f , W , ν α β ≥ Γ , ∣ ν m c m ∣ 2 + W m , m ≤ P , m ∈ M , W ⪰ 0 , ν m ∈ { 0 , 1 } , m ∈ M , \begin{aligned} \mathcal{P}1:\min_{\boldsymbol{c},\boldsymbol{f},\boldsymbol{W},\boldsymbol{\nu}} &\alpha \\ & \beta\geq\Gamma, \\ & |\nu_{m}c_{m}|^{2}+W_{m,m}\leq P,m\in\mathcal{M}, \\ & W\succeq0, \\ & \nu_{m}\in\{0,1\},m\in\mathcal{M}, \end{aligned} P1:c,f,W,νmin​​αβ≥Γ,∣νm​cm​∣2+Wm,m​≤P,m∈M,W⪰0,νm​∈{0,1},m∈M,​

$\begin{array}{rl}\alpha & =\sum _{m=1}^M{\nu }_m^2-\frac{f^{†}\left({\sum }_{m=1}^M{c}_m{\nu }_m{h}_m\right){\left({\sum }_{m=1}^M{c}_m{\nu }_m{h}_m\right)}^{†}f}{f^{†}\left({\sum }_{m=1}^M|c_m{|}^2{\nu }_m^2{h}_m{h}_m^{†}+HW{H}^{†}+A\right)f}\end{array}$

$\begin{array}{rl}\beta & =\sum _{m=1}^M{\nu }_m^2-\frac{|{\sum }_{m=1}^M{c}_m{\nu }_m{g}_m{|}^2}{{\sum }_{m=1}^M|c_m{|}^2{\nu }_m^2|g_m{|}^2+g^{†}Wg+P_{\mathrm{J}}|g_{\mathrm{J}}{|}^2+{\sigma }_{\mathrm{e}}^2}\end{array}$

定义辅助变量$\tilde{\mathbf{\nu }}$来处理离散的整数变量$\mathbf{\nu }$

P 2 : min ⁡ f , c , W , ν ~ , ν α  s.t.  β ≥ Γ , ν ~ m = ν m , m ∈ M , ν m ( 1 − ν ~ m ) = 0 , m ∈ M , c m ( 1 − ν m ) = 0 , m ∈ M , W ⪰ 0 , ν m ∈ { 0 , 1 } , m ∈ M , \begin{aligned} \mathcal{P} 2: \min _{\boldsymbol{f}, c, \boldsymbol{W}, \tilde{\boldsymbol{\nu}}, \boldsymbol{\nu}} & \alpha \\ \text { s.t. } & \beta \geq \Gamma, \\ & \tilde{\nu}_m=\nu_m, \quad m \in \mathcal{M}, \\ & \nu_m\left(1-\tilde{\nu}_m\right)=0, \quad m \in \mathcal{M}, \\ & c_m\left(1-\nu_m\right)=0, \quad m \in \mathcal{M}, \\ & W\succeq0, \\ & \nu_{m}\in\{0,1\},m\in\mathcal{M},\end{aligned} P2:f,c,W,ν~,νmin​ s.t. ​αβ≥Γ,ν~m​=νm​,m∈M,νm​(1−ν~m​)=0,m∈M,cm​(1−νm​)=0,m∈M,W⪰0,νm​∈{0,1},m∈M,​

下面利用罚对偶分解（penalty dual decomposition）来处理上面的优化问题，首先定义增广拉格朗日函数

$\begin{array}{rl}& \mathcal{A}=\alpha +\psi =\alpha +{\mathbf{\kappa }}^{\top }(\mathbf{\nu }-\tilde{\mathbf{\nu }})+\sum _{m=1}^M{\varpi }_m\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)+\sum _{m=1}^M{\eta }_m\left(c_m\left(1-{\nu }_m\right)\right)+\frac{1}{2\varrho }\left(\Vert \mathbf{\nu }-\tilde{\mathbf{\nu }}{\Vert }^2\right)\\ & +\frac{1}{2\varrho }\left(\sum _{m=1}^M{\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)}^2+{\left|c_m\left(1-{\nu }_m\right)\right|}^2\right)\end{array}$
其中$\mathbf{\kappa }$ $\varpi$ $\nu$ $\eta$是对偶变量，$\varrho$是罚系数，于是求解下面的问题

$\begin{array}{rl}\mathcal{P}3:\underset{\begin{array}{c}\mathbf{f},\mathbf{c},\mathbf{W},\tilde{\mathbf{\nu }},\mathbf{\nu }\end{array},\mathbf{\kappa },\varpi ,\varrho ,\eta }{\min }& \mathcal{A},\\ \text{ s.t. }& |{\nu }_m{c}_m{|}^2+W_{m,m}\le P,m\in \mathcal{M},\\ & W⪰0,\\ & \beta \ge \Gamma \end{array}$

在罚对偶分解中外层循环更新$\mathbf{f},c,\mathbf{W},\tilde{\mathbf{\nu }},\mathbf{\kappa }$ $\varpi$ $\nu$ $\varrho$，内层更新下面的变量

当给定$c,\mathbf{W},\tilde{\mathbf{\nu }},\mathbf{\nu }$，最优的$\mathbf{f}$等价求解如下问题
$\mathcal{P}3.1:{\max }_{\mathbf{f}}\frac{{\mathbf{f}}^{†}\left({\sum }_{m=1}^M{c}_m{\mathbf{h}}_m\right){\left({\sum }_{m=1}^M{c}_m{\mathbf{h}}_m\right)}^{†}\mathbf{f}}{{\mathbf{f}}^{†}\left({\sum }_{m=1}^M{|c_m|}^2{\mathbf{h}}_m{\mathbf{h}}_m^{†}+\mathbf{F}\right)\mathbf{f}},$

基于广义瑞利熵 $\mathbf{F}=\mathbf{H}\mathbf{W}{\mathbf{H}}^{†}+\mathbf{A}$. 最优的$\mathbf{f}$ 如下
$\mathbf{f}={\left({\sum }_{m=1}^M{\left|c_m\right|}^2{\mathbf{h}}_m{\mathbf{h}}_m^{†}+\mathbf{F}\right)}^{-1}{\sum }_{m=1}^M{c}_m{\mathbf{h}}_m$

当给定 { f , W , ν ~ , ν } \{\boldsymbol{f}, \boldsymbol{W}, \tilde{\boldsymbol{\nu}}, \boldsymbol{\nu}\} {f,W,ν~,ν} 更新$\mathbf{c}$, 则问题退化为一个分式规划，使用二次转换（quadratic transform）忽略与$\mathbf{c}$无关的项，则$\mathcal{P}3$可以转为如下优化问题，其中$t$是辅助变量。

$\begin{array}{rl}\mathcal{P}3.2:{\max }_{\mathbf{c},t}& 2\Re \left\{t^{\ast }{\mathbf{f}}^{†}\mathbf{H}\mathbf{c}\right\}-|t{|}^2\left({\mathbf{c}}^{†}\mathbf{D}\mathbf{c}+\zeta \right)-\varphi \\ \text{ s.t. }& {\mathbf{c}}^{†}\mathbf{g}{\mathbf{g}}^{†}\mathbf{c}-\left(1^{\top }\mathbf{\nu }-\Gamma \right)\left({\mathbf{c}}^{†}\mathbf{B}\mathbf{c}+\varsigma \right)\le 0\\ & |{\nu }_m{c}_m{|}^2+W_{m,m}\le P,m\in \mathcal{M},\end{array}$

$\begin{array}{rl}& \varphi \triangleq (\mathbf{\eta }\odot (1-\mathbf{\nu }){)}^{\top }\mathbf{c}+\frac{1}{2\varrho }{\mathbf{c}}^{†}\mathrm{diag}((1-\mathbf{\nu })\odot (1-\mathbf{\nu }))\mathbf{c}\\ & \zeta \triangleq {\mathbf{f}}^{†}\left(\mathbf{H}\mathbf{W}{\mathbf{H}}^{†}+\mathbf{A}\right)\mathbf{f}\\ & \varsigma \triangleq {\mathbf{g}}^{†}\mathbf{W}\mathbf{g}+P_{\mathrm{J}}{\left|g_{\mathrm{J}}\right|}^2+{\sigma }_{\mathrm{e}}^2\\ & \mathbf{B}\triangleq \mathrm{diag}\left({\left[{\left|g_1\right|}^2,\dots ,{\left|g_M\right|}^2\right]}^{\top }\right)\\ & \mathbf{D}\triangleq \mathrm{diag}\left({\left[f^{†}{\mathbf{h}}_1{\mathbf{h}}_1^{†}\mathbf{f},\dots ,{\mathbf{f}}^{†}{\mathbf{h}}_M{\mathbf{h}}_M^{†}\mathbf{f}\right]}^{\top }\right),\end{array}$

• 为什么${\sum }_{m=1}^M{\eta }_m\left(c_m\left(1-{\nu }_m\right)\right)$等价于$(\mathbf{\eta }\odot (1-\mathbf{\nu }){)}^{\top }\mathbf{c}$

首先这个结果是一个数，因为有求和，对应等价项有内积，求和项中是三项的乘积，转为向量则为哈达玛积，三个向量的哈达玛积，再对所有元素求和，也可以表示为其中两个向量的哈达玛积的结果与另外一个的内积，顺序不影响结果

• 当其他变量给定，关于$\tilde{\mathbf{\nu }}$是凸函数吗？写出对$\tilde{\mathbf{\nu }}$求导的表达式

$\begin{array}{rl}& \psi ={\mathbf{\kappa }}^{\top }(\mathbf{\nu }-\tilde{\mathbf{\nu }})+\sum _{m=1}^M{\varpi }_m\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)+\sum _{m=1}^M{\eta }_m\left(c_m\left(1-{\nu }_m\right)\right)+\frac{1}{2\varrho }\left(\Vert \mathbf{\nu }-\tilde{\mathbf{\nu }}{\Vert }^2\right)\\ & +\frac{1}{2\varrho }\left(\sum _{m=1}^M{\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)}^2+{\left|c_m\left(1-{\nu }_m\right)\right|}^2\right)\end{array}$

• ${\mathbf{\kappa }}^{\top }(\mathbf{\nu }-\tilde{\mathbf{\nu }})$ 是关于 $\tilde{\mathbf{\nu }}$的线性项，不影响凸性。
• ${\sum }_{m=1}^M{\varpi }_m\left({\nu }_m(1-{\tilde{\nu }}_m)\right)$ 也是线性项，不影响凸性。
• $\frac{1}{2\varrho }\Vert \mathbf{\nu }-\tilde{\mathbf{\nu }}{\Vert }^2$是二次凸函数，因为其 Hessian 矩阵是对角矩阵，且对角元素全是正的 $\frac{1}{\varrho }$。
• $\frac{1}{2\varrho }{\sum }_{m=1}^M{\left({\nu }_m(1-{\tilde{\nu }}_m)\right)}^2$ 也是二次函数，每一项的二阶导数都是 $\frac{{\nu }_m^2}{\varrho }$，显然是非负的，因此是凸函数。

---

$\frac{\partial \psi }{\partial {\tilde{\nu }}_m}=-{\kappa }_m-{\varpi }_m{\nu }_m-\frac{1}{\varrho }({\nu }_m-{\tilde{\nu }}_m)-\frac{1}{\varrho }{\nu }_m^2(1-{\tilde{\nu }}_m)=0.$
整理得到：
$-\varrho {\kappa }_m-\varrho {\varpi }_m{\nu }_m-({\nu }_m-{\tilde{\nu }}_m)-{\nu }_m^2(1-{\tilde{\nu }}_m)=0.$
${\tilde{\nu }}_m-{\nu }_m^2(1-{\tilde{\nu }}_m)={\nu }_m+\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m.$
${\tilde{\nu }}_m-{\nu }_m^2+{\nu }_m^2{\tilde{\nu }}_m={\nu }_m+\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m.$
${\tilde{\nu }}_m+{\nu }_m^2{\tilde{\nu }}_m={\nu }_m+\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m+{\nu }_m^2.$
${\tilde{\nu }}_m=\frac{{\nu }_m+\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m+{\nu }_m^2}{1+{\nu }_m^2}.$
${\tilde{\nu }}_m=\frac{\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m+{\nu }_m^2+{\nu }_m}{1+{\nu }_m^2}.$

• 当其他变量给定，关于$\mathbf{\nu }$利用KKT条件，解释下$\mathbf{\nu }$和$\lambda$的求解过程

$\begin{array}{rl}\mathcal{P}3.5:\underset{\mathbf{\nu }}{\min }& 1^{\top }\mathbf{\nu }+\psi \\ \text{ s.t. }& \beta \ge \Gamma \end{array}$
$\begin{array}{rl}& \psi ={\mathbf{\kappa }}^{\top }(\mathbf{\nu }-\tilde{\mathbf{\nu }})+\sum _{m=1}^M{\varpi }_m\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)+\sum _{m=1}^M{\eta }_m\left(c_m\left(1-{\nu }_m\right)\right)+\frac{1}{2\varrho }\left(\Vert \mathbf{\nu }-\tilde{\mathbf{\nu }}{\Vert }^2\right)\\ & +\frac{1}{2\varrho }\left(\sum _{m=1}^M{\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)}^2+{\left|c_m\left(1-{\nu }_m\right)\right|}^2\right)\end{array}$
$\begin{array}{rl}\beta & =\sum _{m=1}^M{\nu }_m^2-\frac{|{\sum }_{m=1}^M{c}_m{\nu }_m{g}_m{|}^2}{{\sum }_{m=1}^M|c_m{|}^2{\nu }_m^2|g_m{|}^2+g^{†}Wg+P_{\mathrm{J}}|g_{\mathrm{J}}{|}^2+{\sigma }_{\mathrm{e}}^2}\end{array}$
$\begin{array}{rl}\mathbf{\nu }=& \varrho {\left(\mathbf{I}+\mathrm{diag}\left((1-\tilde{\mathbf{\nu }})\odot (1-\tilde{\mathbf{\nu }})+{\mathbf{c}}^{\ast }\odot \mathbf{c}\right)\right)}^{-1}\left(-1-\mathbf{\kappa }-\varpi \odot (1-\tilde{\mathbf{\nu }})+\mathbf{\eta }\odot \mathbf{c}+\frac{1}{\varrho }\left(\tilde{\mathbf{\nu }}+{\mathbf{c}}^{\ast }\odot \mathbf{c}\right)-1\lambda \right)\\ \lambda =& (1^{\top }\varrho {\left(\mathbf{I}+\mathrm{diag}\left((1-\tilde{\mathbf{\nu }})\odot (1-\tilde{\mathbf{\nu }})+{\mathbf{c}}^{\ast }\odot \mathbf{c}\right)\right)}^{-1}\left(-1-\mathbf{\kappa }-\varpi \odot (1-\tilde{\mathbf{\nu }})+\mathbf{\eta }\odot \mathbf{c}+\frac{1}{\varrho }\left(\tilde{\mathbf{\nu }}+{\mathbf{c}}^{\ast }\odot \mathbf{c}\right)\right)\\ & -(\Gamma +\gamma ))\frac{1}{\varrho }\mathrm{Tr}{\left({\left(\mathbf{I}+\mathrm{diag}\left((1-\tilde{\mathbf{\nu }})\odot (1-\tilde{\mathbf{\nu }})+{\mathbf{c}}^{\ast }\odot \mathbf{c}\right)\right)}^{-1}\right)}^{-1}.\end{array}$
$\gamma \triangleq 1^{\top }\mathbf{\nu }-\beta$

$\mathcal{L}(\mathbf{\nu },\lambda )=1^{\top }\mathbf{\nu }+\psi -\lambda (\beta -\Gamma ).$
${\nabla }_{\mathbf{\nu }}\mathcal{L}(\mathbf{\nu },\lambda )=0.$

进一步化简：$(1+{\nu }_m^2/\varrho ){\tilde{\nu }}_m={\nu }_m+\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m.$
${\tilde{\nu }}_m=\frac{{\nu }_m+\varrho {\kappa }_m+\varrho {\varpi }_m{\nu }_m}{1+{\nu }_m^2/\varrho }.$
转为向量形式：
$\tilde{\mathbf{\nu }}=(\mathbf{I}+\mathrm{diag}(\mathbf{\nu }\odot \mathbf{\nu }){)}^{-1}(\varrho \mathbf{\kappa }+(\varrho \varpi +\mathbf{\nu })\odot \mathbf{\nu }+\mathbf{\nu }).$

下面问题通常难以直接求解，因为分子与分母之间耦合较强。
$\begin{array}{rl}& \alpha +{\mathbf{\kappa }}^{\top }(\mathbf{\nu }-\tilde{\mathbf{\nu }})+\sum _{m=1}^M{\varpi }_m\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)+\sum _{m=1}^M{\eta }_m\left(c_m\left(1-{\nu }_m\right)\right)+\frac{1}{2\varrho }\left(\Vert \mathbf{\nu }-\tilde{\mathbf{\nu }}{\Vert }^2\right)\\ & +\frac{1}{2\varrho }\left(\sum _{m=1}^M{\left({\nu }_m\left(1-{\tilde{\nu }}_m\right)\right)}^2+{\left|c_m\left(1-{\nu }_m\right)\right|}^2\right)\end{array}$

$\begin{array}{r}\frac{|{\mathbf{f}}^{†}\mathbf{H}\mathbf{c}{|}^2}{{\mathbf{c}}^{†}\mathbf{D}\mathbf{c}+\zeta }\end{array}$

二次转换（Quadratic Transform）引入一个辅助变量$t$，将原来的分式形式转化为一个关于 $\mathbf{c}$和 $t$ 的二次函数。这样可以将原本难以优化的比值形式分解为两个较容易处理的部分，从而交替优化：

• 对于固定的 $t$，问题关于$\mathbf{c}$ 变成一个二次规划；
• 对于固定的 $\mathbf{c}$，可以解析地求得最优的辅助变量$t$。
• 将原目标函数写成分子形式 $|{\mathbf{f}}^{†}\mathbf{H}\mathbf{c}{|}^2$与分母 ${\mathbf{c}}^{†}\mathbf{D}\mathbf{c}+\zeta$ 的比值。
• 引入辅助变量 $t$，利用等价变换得到一个新的目标函数形式。最优的 $t$ 可由 $t^{\star }=\frac{{\mathbf{f}}^{†}\mathbf{H}\mathbf{c}}{{\mathbf{c}}^{†}\mathbf{D}\mathbf{c}+\zeta }$得到，从而使得新目标函数达到与原分式目标相同的最优值。

2-分式规划中二次变换的本质

考虑函数$f(n,z)=\frac{n^2}{z}$，我们希望在当前点$(n_0,z_0)$附近构造它的一阶泰勒展开来作为 surrogate function。

1. 求偏导数

   对$n$的偏导数为$\frac{\partial f}{\partial n}=\frac{2n}{z}$
   对 $z$的偏导数为$\frac{\partial f}{\partial z}=-\frac{n^2}{z^2}$

2. 在点 $(n_0,z_0)$ 处做一阶泰勒展开

   一阶泰勒展开形式为
   $f(n,z)\approx f(n_0,z_0)+\frac{\partial f}{\partial n}{|}_{(n_0,z_0)}(n-n_0)+\frac{\partial f}{\partial z}{|}_{(n_0,z_0)}(z-z_0).$
   代入各项，有
   $\frac{n^2}{z}\approx \frac{n_0^2}{z_0}+\frac{2n_0}{z_0}(n-n_0)-\frac{n_0^2}{z_0^2}(z-z_0)$

3. 忽略常数项

   在优化问题中，我们关心的是关于 $n$ 和$z$ 的变量项，因此常数项 $\frac{n_0^2}{z_0}-\frac{2n_0^2}{z_0}+\frac{n_0^2}{z_0^2}{z}_0$对最优解没有影响，可以忽略。这样 surrogate function 取
   $\tilde{f}(n,z)=\frac{2n_0}{z_0}n-\frac{n_0^2}{z_0^2}z.$

4. 与二次转换的关联
   通常在二次转换中，我们引入辅助变量$t$定义为$t=\frac{n_0}{z_0}$，则 surrogate function 可以写为 f ~ ( n , z ) = 2 ℜ { t ∗ n } − ∣ t ∣ 2 z . \tilde{f}(n,z)=2\Re\{t^* n\}-|t|^2 z. f~​(n,z)=2ℜ{t∗n}−∣t∣2z.
   这种形式正是将原问题中形如 $\frac{n^2}{z}$ 的分式项利用一阶泰勒展开构造出的 surrogate function，从而将分式形式转化为一个关于 $n$ 和 $z$ 的二次函数，便于后续交替优化。