前言
本文是博主对于 Zhi-quan Luo 老师的经典著作 《Semidefinite Relaxation of Quadratic Optimization Problems》 的读书笔记，希望可作为对全文以中文形式的核心梳理。
单刀直入
首先， Semidefinite Relaxation (SDR) 适用的问题可以写为如下形式：
min
x
∈
R
n
x
T
C
x
s.t.
x
T
A
i
x
⊵
i
b
i
,
i
=
1
,
…
,
m
(1)
\begin{aligned} \min _{x \in \mathbb{R}^{n}} & \;\;x^{T} C x \\ \text { s.t. } & x^{T} A_{i} x \unrhd_{i} b_{i}, \quad i=1, \ldots, m \end{aligned}\tag{1}
x∈Rnmin s.t. xTCxxTAix⊵ibi,i=1,…,m(1)
有几个注意点：
暂时定义在实数域上， 但复数域有类似的结论。
⊵
i
\unrhd_{i}
⊵i 表示
≥
\ge
≥,
≤
\le
≤,
=
=
= 的 其中之一。也就是说， 只要限制条件是二次约束即可。
C
C
C，
A
i
A_i
Ai 都是对称矩阵。 即,
C
,
A
1
,
…
,
A
m
∈
S
n
C, A_{1}, \ldots, A_{m} \in \mathbb{S}^{n}
C,A1,…,Am∈Sn。
显然， 目标函数和限制条件中都有两个
x
x
x， 因此这类问题也被称为 二次约束二次规划 (quadratically constrained quadratic programs, QCQP) 问题。 需要注意的是， 这并不是一个凸问题。 因为
x
T
A
i
x
>
0
x^{T} A_{i} x>0
xTAix>0 和
x
T
A
i
x
=
0
x^{T} A_{i} x=0
xTAix=0 都并非一个凸集。
而SDR方法的目的就是将问题转化为一个凸问题从而求解。
我们引入一个新的变量
X
=
x
x
T
X = xx^T
X=xxT， 并以此为优化变量， 那么问题(1)可以被写为：
min
X
∈
S
n
Tr
(
C
X
)
s.t.
Tr
(
A
i
X
)
⊵
i
b
i
,
i
=
1
,
…
,
m
,
X
⪰
0
,
rank
(
X
)
=
1
(2)
\begin{aligned} \min _{X \in \mathbb{S}^{n}} & \operatorname{Tr}(C X) \\ \text { s.t. } & \operatorname{Tr}\left(A_{i} X\right)\unrhd_{i} b_{i}, \quad i=1, \ldots, m, \\ & X \succeq 0, \operatorname{rank}(X)=1 \end{aligned}\tag{2}
X∈Snmin s.t. Tr(CX)Tr(AiX)⊵ibi,i=1,…,m,X⪰0,rank(X)=1(2) 详细解释一下这一步的转化：
注意到 (1) 的 目标函数
x
T
C
x
x^TCx
xTCx显然是一个标量。 而标量可以看成一个
1
×
1
1\times 1
1×1的矩阵， 且迹等于本身。 即
t
r
(
x
T
C
x
)
=
x
T
C
x
\mathrm{tr}(x^TCx)=x^TCx
tr(xTCx)=xTCx。 而根据迹的性质， 有
t
r
(
A
B
)
=
t
r
(
B
A
)
\mathrm{tr}(AB) = \mathrm{tr}(BA)
tr(AB)=tr(BA)。 也就是说，
t
r
(
x
T
C
x
)
=
t
r
(
C
x
x
T
)
=
t
r
(
C
X
)
\mathrm{tr}(x^TCx)=\mathrm{tr}(Cxx^T)=\mathrm{tr}(CX)
tr(xTCx)=tr(CxxT)=tr(CX)。 这也就变成了 (2)中的目标函数。 那么 (2) 中的限制条件，也就可以根据相同的变换轻易得到。相比于(1)， (2)中多了两个限制条件， 这是由于
X
=
x
x
T
X = xx^T
X=xxT 引入的。 显然
rank
(
X
)
=
1
\operatorname{rank}(X)=1
rank(X)=1， 因为
X
X
X的所有列都线性相关。 也因此，只有一个特征值等于
x
T
x
x^Tx
xTx，显然是大于0的，所以肯定是半正定矩阵。
这一步转化的意义在哪呢？
事实上， 除了
rank
(
X
)
=
1
\operatorname{rank}(X)=1
rank(X)=1 这个限制以外， 整个问题是一个凸问题。 由于迹函数是个仿射变换， 很容易证明其凸性。 而半正定约束也显然是个凸集， 因为两个半正定矩阵的和一定也是一个半正定矩阵。
因此， 工程上很自然的想法就是， **暂时得忽略 该约束
rank
(
X
)
=
1
\operatorname{rank}(X)=1
rank(X)=1， 并通过凸优化方法 （事实上以CVX工具包为代表的内点法数值算法）来求解出一个解
X
X
X. 这一步大家百度下CVX的使用就可以了，没有任何障碍。
而问题的关键点在于，始终我们问题需要得到的是
x
x
x，而非
X
X
X。 如果通过凸优化求出的
X
X
X刚好就是一个
rank
(
X
)
=
1
\operatorname{rank}(X)=1
rank(X)=1的矩阵，那么
x
x
x可以直接得到（对X做个SVD或EVD啥的都可以）。 但更多时候，
X
X
X没有道理是一个
rank
(
X
)
=
1
\operatorname{rank}(X)=1
rank(X)=1的矩阵。 也就是说， 根本不存在一个
x
x
x， 使得
X
=
x
x
T
X=xx^T
X=xxT。
工程实现
那么SDR要解决的另一个问题就是如何从
X
X
X中恢复出一个满足原问题约束的
x
x
x。 出于工程实现角度的思路其实非常清晰， 我们可以直接求解下面的问题以获得
x
x
x：
min
x
∥
X
−
x
x
T
∥
F
2
(3)
\min_x \;\; \|X-xx^T\|_F^2\tag{3}
xmin∥X−xxT∥F2(3) 即找一个最接近
X
X
X的
x
x
T
xx^T
xxT。 这个问题很经典了，而他的闭式解就是，
x
x
x是
X
X
X的最大特征向量乘以最大特征值的平方根。 即， 将
X
X
X的特征值分解表示为：
X
⋆
=
∑
i
=
1
r
λ
i
q
i
q
i
T
X^{\star}=\sum_{i=1}^{r} \lambda_{i} q_{i} q_{i}^{T}
X⋆=i=1∑rλiqiqiT 其中
λ
i
\lambda_i
λi，
q
i
q_i
qi，代表第
i
i
i大的特征值和对应的特征向量。 那么(3)的最优解
x
x
x就是
x
~
=
λ
1
q
1
\tilde{x}=\sqrt{\lambda_{1} }q_1
x~=λ1
q1。
但是，问题又出现了！ 虽然
X
X
X满足了(2)中的所有的约束， 但由于在这一步中，(3)中求得的
x
x
x是一个近似的结果。 此时得到的
x
x
x，不一定满足原问题(1)中的约束了！ 也就是说， 经过一顿转化之后， 求得的
x
x
x并不是原问题的可行解！此时怎么办呢？ 解决方案也非常符合工程思维：直接从
x
x
x出发找一个离
x
x
x最近的可行解， 这就是SDR的最终结果。
最后提两点：
直接从
x
x
x出发找一个离
x
x
x最近的可行解， 这本身就是一个独立的问题， 具体问题具体分析，后面会给一个具体的例子。毫无疑问，在SDR中有许许多多的近似，工程处理。 因此， SDR的解远非全局最优解。
具体实例
为节约篇幅， 本文只讲一个例子。 也不是论文中给出的， 而是HBF混合波束成形的经典论文 《Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems》中的 一个使用。 有兴趣的读者也可以去看 SDR论文的原文， 接触更多的例子。
以HBF为例， 作者将问题转化为了如下的形式， 熟悉HBF的读者应该很亲切了：
minimize
F
B
B
∥
F
o
p
t
−
F
R
F
F
B
B
∥
F
2
subject to
∥
F
B
B
∥
F
2
=
N
R
F
t
N
s
N
t
(4)
\begin{array}{ll} \underset{\mathbf{F}_{\mathrm{BB}}}{\operatorname{minimize}} & \left\|\mathbf{F}_{\mathrm{opt}}-\mathbf{F}_{\mathrm{RF}} \mathbf{F}_{\mathrm{BB}}\right\|_{F}^{2} \\ \text { subject to } & \left\|\mathbf{F}_{\mathrm{BB}}\right\|_{F}^{2}=\frac{N_{\mathrm{RF}}^{t} N_{s}}{N_{t}} \end{array}\tag{4}
FBBminimize subject to ∥Fopt−FRFFBB∥F2∥FBB∥F2=NtNRFtNs(4)
作者使用了 SDR作为一种算法来求解该问题。 那么首先， 为什么会选用 SDR呢？ 因为可以看到， 目标函数和限制条件都是二次形式， 这就是我们之前说到的SDR目标问题：QCQP问题。 接下来，通过这个例子展示如果实战使用SDR。
首先， 刚刚介绍SDR时都是向量形式的变量
x
x
x, 而(4)中都是矩阵，不利于处理， 因此第一步先进行列化：
∥
F
o
p
t
−
F
R
F
F
B
B
∥
F
2
=
∥
vec
(
F
o
p
t
−
F
R
F
F
B
B
)
∥
2
2
=
∥
vec
(
F
o
p
t
)
−
vec
(
F
R
F
F
B
B
)
∥
2
2
=
∥
vec
(
F
o
p
t
)
−
(
I
N
s
⊗
F
R
F
)
vec
(
F
B
B
)
∥
2
2
.
\begin{aligned} \left\|\mathbf{F}_{\mathrm{opt}}-\mathbf{F}_{\mathrm{RF}} \mathbf{F}_{\mathrm{BB}}\right\|_{F}^{2} &=\left\|\operatorname{vec}\left(\mathbf{F}_{\mathrm{opt}}-\mathbf{F}_{\mathrm{RF}} \mathbf{F}_{\mathrm{BB}}\right)\right\|_{2}^{2} \\ &=\left\|\operatorname{vec}\left(\mathbf{F}_{\mathrm{opt}}\right)-\operatorname{vec}\left(\mathbf{F}_{\mathrm{RF}} \mathbf{F}_{\mathrm{BB}}\right)\right\|_{2}^{2} \\ &=\left\|\operatorname{vec}\left(\mathbf{F}_{\mathrm{opt}}\right)-\left(\mathbf{I}_{N_{s}} \otimes \mathbf{F}_{\mathrm{RF}}\right) \operatorname{vec}\left(\mathbf{F}_{\mathrm{BB}}\right)\right\|_{2}^{2} . \end{aligned}
∥Fopt−FRFFBB∥F2=∥vec(Fopt−FRFFBB)∥22=∥vec(Fopt)−vec(FRFFBB)∥22=∥vec(Fopt)−(INs⊗FRF)vec(FBB)∥22. 进行变量代换后 (
f
=
vec
(
F
o
p
t
)
\mathbf{f}=\operatorname{vec}\left(\mathbf{F}_{\mathrm{opt}}\right)
f=vec(Fopt),
b
=
vec
(
F
B
B
)
\mathbf{b}=\operatorname{vec}\left(\mathbf{F}_{\mathrm{BB}}\right)
b=vec(FBB) and
E
=
I
N
s
⊗
F
R
F
.
\mathbf{E}=\mathbf{I}_{N_{s}} \otimes \mathbf{F}_{\mathrm{RF}} .
E=INs⊗FRF.，原问题可写为：
minimize
b
∥
t
f
−
E
b
∥
2
2
subject to
{
∥
b
∥
2
2
=
N
R
F
t
N
s
N
t
t
2
=
1
(5)
\begin{aligned} &\underset{\mathbf{b}}{\operatorname{minimize}} \quad\|t \mathbf{f}-\mathbf{E b}\|_{2}^{2} \\ &\text { subject to } & \left\{\begin{array}{l} \|\mathbf{b}\|_{2}^{2}=\frac{N_{\mathrm{RF}}^{t} N_{s}}{N_{t}} \\ t^{2}=1 \end{array}\right. \end{aligned}\tag{5}
bminimize∥tf−Eb∥22 subject to {∥b∥22=NtNRFtNst2=1(5)
**这里必须强调的一点是， 作者引入了
t
t
t这样一个辅助变量。这是SDR的常见技巧之一！**接下来阐释这个
t
t
t的作用。
首先， 对于原问题的影响上：以(5)求解之后， 如果得到
t
=
1
t=1
t=1， 那么
f
\mathbf{f}
f就是(4）的最优解。 而如果
t
=
−
1
t=-1
t=−1， 那么
f
\mathbf{f}
f就是(4)的最优解的相反数， 仍等效于得到了最优解。其次， 加入这个
t
t
t辅助变量后， 可以更好地将(5)写成SDR的标准形式。 继续看：
目标函数可以写为：
∥
t
f
−
E
b
∥
2
2
=
[
b
H
t
]
[
E
H
E
−
E
H
f
−
f
H
E
f
H
f
]
[
b
t
]
\|t \mathbf{f}-\mathbf{E b}\|_{2}^{2}=\left[\begin{array}{ll} \mathbf{b}^{H} & t \end{array}\right]\left[\begin{array}{cc} \mathbf{E}^{H} \mathbf{E} & -\mathbf{E}^{H} \mathbf{f} \\ -\mathbf{f}^{H} \mathbf{E} & \mathbf{f}^{H} \mathbf{f} \end{array}\right]\left[\begin{array}{l} \mathbf{b} \\ t \end{array}\right]
∥tf−Eb∥22=[bHt][EHE−fHE−EHffHf][bt] 注意到： 此时令
y
=
[
b
t
]
\mathbf{y}=\left[\begin{array}{l}\mathbf{b} \\ t\end{array}\right]
y=[bt],
C
=
[
E
H
E
−
E
H
f
−
f
H
E
f
H
f
]
\mathbf{C}=\left[\begin{array}{cc}\mathbf{E}^{H} \mathbf{E} & -\mathbf{E}^{H} \mathbf{f} \\ -\mathbf{f}^{H} \mathbf{E} & \mathbf{f}^{H} \mathbf{f}\end{array}\right]
C=[EHE−fHE−EHffHf], 上式就等于
y
H
C
y
\mathbf{y}^H\mathbf{C}\mathbf{y}
yHCy，而
C
\mathbf{C}
C是个显然的半正定矩阵：
C
=
[
E
,
−
f
]
H
[
E
,
−
f
]
\mathbf{C}=[\mathbf{E}, -\mathbf{f}]^H[\mathbf{E}, -\mathbf{f}]
C=[E,−f]H[E,−f]，一个矩阵的共轭转置乘以本身肯定是半正定矩阵（可从特征值角度得证）。
那么(5)中的另外两个约束又可以转换为：
∥
b
∥
2
2
=
[
b
H
t
]
[
I
N
R
F
t
N
s
0
0
0
]
[
b
t
]
=
N
R
F
t
N
s
N
t
t
2
=
[
b
H
t
]
[
0
N
R
F
t
N
s
0
0
1
]
[
b
t
]
=
1
\begin{aligned}\|\mathbf{b}\|_{2}^{2} &=\left[\begin{array}{ll}\mathbf{b}^{H} & t\end{array}\right]\left[\begin{array}{cc}\mathbf{I}_{N_{\mathrm{RF}}^{t}} N_{s} & 0 \\ \mathbf{0} & 0\end{array}\right]\left[\begin{array}{c}\mathbf{b} \\ t\end{array}\right]=\frac{N_{\mathrm{RF}}^{t} N_{s}}{N_{t}} \\ t^{2} &=\left[\begin{array}{ll}\mathbf{b}^{H} & t\end{array}\right]\left[\begin{array}{cc}0_{N_{\mathrm{RF}}^{t}} N_{s} & 0 \\ 0 & 1\end{array}\right]\left[\begin{array}{l}\mathbf{b} \\ t\end{array}\right]=1 \end{aligned}
∥b∥22t2=[bHt][INRFtNs000][bt]=NtNRFtNs=[bHt][0NRFtNs001][bt]=1
大家可以细致体会下， 为什么SDR可以应用广泛的原因， 因为大部分二次约束都可以通过稍加构造就写成QCQP的形式。
那么，最后经过一步变量代换：
y
=
[
b
t
]
,
Y
=
y
y
H
,
C
=
[
E
H
E
−
E
H
f
−
f
H
E
f
H
f
]
A
1
=
[
I
N
R
F
t
N
s
0
0
0
]
,
A
2
=
[
0
N
R
F
t
N
s
0
0
1
]
\begin{aligned} &\mathbf{y}=\left[\begin{array}{c} \mathbf{b} \\ t \end{array}\right], \mathbf{Y}=\mathbf{y} \mathbf{y}^{H}, \mathbf{C}=\left[\begin{array}{cc} \mathbf{E}^{H} \mathbf{E} & -\mathbf{E}^{H} \mathbf{f} \\ -\mathbf{f}^{H} \mathbf{E} & \mathbf{f}^{H} \mathbf{f} \end{array}\right] \\ &\mathbf{A}_{1}=\left[\begin{array}{cc} \mathbf{I}_{N_{\mathrm{RF}}^{t} N_{s}} & 0 \\ \mathbf{0} & 0 \end{array}\right], \mathbf{A}_{2}=\left[\begin{array}{cc} \mathbf{0}_{N_{\mathrm{RF}}^{t}} N_{s} & 0 \\ \mathbf{0} & 1 \end{array}\right] \end{aligned}
y=[bt],Y=yyH,C=[EHE−fHE−EHffHf]A1=[INRFtNs000],A2=[0NRFtNs001]
（5）终于可写为SDR的标准形式：
minimize
Y
∈
H
n
(
Tr
C
Y
)
subject to
{
Tr
(
A
1
Y
)
=
N
R
F
t
N
s
N
t
Tr
(
A
2
Y
)
=
1
Y
⪰
0
,
rank
(
Y
)
=
1
\begin{aligned} &\underset{\mathbf{Y} \in \mathbb{H}^{n}}{\operatorname{minimize}} \underset{\operatorname{Tr}}(\mathbf{C Y}) \\ &\text { subject to }\left\{\begin{array}{l} \operatorname{Tr}\left(\mathbf{A}_{1} \mathbf{Y}\right)=\frac{N_{\mathrm{RF}}^{t} N_{s}}{N_{t}} \\ \operatorname{Tr}\left(\mathbf{A}_{2} \mathbf{Y}\right)=1 \\ \mathbf{Y} \succeq 0, \operatorname{rank}(\mathbf{Y})=1 \end{array}\right. \end{aligned}
Y∈HnminimizeTr(CY) subject to ⎩⎨⎧Tr(A1Y)=NtNRFtNsTr(A2Y)=1Y⪰0,rank(Y)=1 通过松弛掉最后一个约束， 问题就可以通过凸优化直接求解。 最后必须强调， 如何从
Y
\mathbf{Y}
Y中恢复出
b
\mathbf{b}
b（即原问题真正的目标）。 首先，用特征值分解得到
y
\mathbf{y}
y。 此时
y
\mathbf{y}
y的最后一个元素大概率不是1，而按照定义案例
t
t
t应该必须是
1
或
−
1
1或-1
1或−1。此时处理方式很简单， 直接对最后一个元素取正负号， 强行归成
1
1
1或
−
1
-1
−1即可。 而
b
\mathbf{b}
b（
y
\mathbf{y}
y的前面的元素）也不符合
∥
b
∥
2
2
=
N
R
F
t
N
s
N
t
\|\mathbf{b}\|_{2}^{2}=\frac{N_{\mathrm{RF}}^{t} N_{s}}{N_{t}}
∥b∥22=NtNRFtNs的约束，此时的做法就是将
b
\mathbf{b}
b强行归一化成
∥
b
∥
2
2
=
N
R
F
t
N
s
N
t
\|\mathbf{b}\|_{2}^{2}=\frac{N_{\mathrm{RF}}^{t} N_{s}}{N_{t}}
∥b∥22=NtNRFtNs即可。 操作非常简单， 那么其对应的思路就是我们在上文中提到的：当得到了
x
x
x后， 以离
x
x
x最近的可行解作为原问题的解。
实例2
再举个近期的实例好了。 是来自于 智能反射面相关paper 《Intelligent Reflecting Surface Enhanced Wireless Network: Joint Active and Passive Beamforming Design》中， 对于passive beamforming 的设计， 同样使用了 SDR 算法。
原问题可以转化为这样的形式：
max
v
v
H
Φ
Φ
H
v
+
v
H
Φ
h
d
+
h
d
H
Φ
H
v
s.t.
∣
v
n
∣
=
1
,
∀
n
=
1
,
⋯
,
N
\begin{array}{cl} \max _{\boldsymbol{v}} & \boldsymbol{v}^{H} {\Phi} \Phi^{H} \boldsymbol{v}+\boldsymbol{v}^{H}{\Phi} \boldsymbol{h}_{d}+\boldsymbol{h}_{d}^{H}{\Phi}^{H} \boldsymbol{v} \\ \text { s.t. } & \left|v_{n}\right|=1, \forall n=1, \cdots, N \end{array}
maxv s.t. vHΦΦHv+vHΦhd+hdHΦHv∣vn∣=1,∀n=1,⋯,N 简单而言， 就是其余参数都已给定， 要求优化向量
v
\mathbf{v}
v， 其中
v
\mathbf{v}
v的每个元素需要满足恒模约束。 那么同样的， 可以通过引入辅助变量
t
t
t， 把问题转换为 齐次的 QCQP 问题：
max
v
‾
v
‾
H
R
v
‾
s.t.
∣
v
ˉ
n
∣
=
1
,
∀
n
=
1
,
⋯
,
N
+
1
\begin{array}{cl} \max _{\overline{\boldsymbol{v}}} & \overline{\boldsymbol{v}}^{H} \boldsymbol{R} \overline{\boldsymbol{v}} \\ \text { s.t. } & \left|\bar{v}_{n}\right|=1, \forall n=1, \cdots, N+1 \end{array}
maxv s.t. vHRv∣vˉn∣=1,∀n=1,⋯,N+1
其中，
R
=
[
Φ
Φ
H
Φ
h
d
h
d
H
Φ
H
0
]
,
v
‾
=
[
v
t
]
\boldsymbol{R}=\left[\begin{array}{cc} \boldsymbol{\Phi} \Phi^{H} & \mathbf{\Phi} \boldsymbol{h}_{d} \\ \boldsymbol{h}_{d}^{H} \boldsymbol{\Phi}^{H} & 0 \end{array}\right], \quad \overline{\boldsymbol{v}}=\left[\begin{array}{l} v \\ t \end{array}\right]
R=[ΦΦHhdHΦHΦhd0],v=[vt]
那么根据SDR的方法， 令
V
=
v
ˉ
v
ˉ
H
\mathbf{V}=\bar{\mathbf{v}}\bar{\mathbf{v}}^H
V=vˉvˉH, 就可以将问题转化为：
max
V
tr
(
R
V
)
s.t.
V
n
,
n
=
1
,
∀
n
=
1
,
⋯
,
N
+
1
,
V
⪰
0
\begin{array}{ll} \max _{\boldsymbol{V}} & \operatorname{tr}(\boldsymbol{R} \boldsymbol{V}) \\ \text { s.t. } & \boldsymbol{V}_{n, n}=1, \forall n=1, \cdots, N+1, \\ & \boldsymbol{V} \succeq 0 \end{array}
maxV s.t. tr(RV)Vn,n=1,∀n=1,⋯,N+1,V⪰0
当然这里同样的放松掉了
rank
(
V
)
=
1
\operatorname{rank}(\boldsymbol{V})=1
rank(V)=1这一约束。 可以看到， 上述问题已经是凸问题了， 因为非凸的恒模约束经过转化后变成了
V
n
,
n
=
1
,
∀
n
=
1
,
⋯
,
N
+
1
\boldsymbol{V}_{n, n}=1, \forall n=1, \cdots, N+1
Vn,n=1,∀n=1,⋯,N+1， 这无疑是一个凸约束 （可以用凸集的定义轻松得证）。
因此， SDR也是处理恒模约束的一种思路。
注意， 这个例子的后续处理，也是从SDR解
V
\mathbf{V}
V获得原问题可行解的一种经典思路：SDR + Gaussian randomization. 这种处理相比于上面提到的直接寻找欧氏距离最近的
v
\mathbf{v}
v，会有通过复杂度提升换来的一定性能增益。
首先， 对
V
\mathbf{V}
V进行 EVD分解， 得到
V
=
U
Σ
U
H
\boldsymbol{V}=\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{U}^{H}
V=UΣUH， 此时， 我们令
v
‾
=
U
Σ
1
/
2
r
\overline{\boldsymbol{v}}=\boldsymbol{U} \boldsymbol{\Sigma}^{\mathbf{1} / \mathbf{2}} \boldsymbol{r}
v=UΣ1/2r， 其中
r
∈
C
N
(
0
,
I
N
+
1
)
\boldsymbol{r} \in \mathcal{C} \mathcal{N}\left(\mathbf{0}, \boldsymbol{I}_{N+1}\right)
r∈CN(0,IN+1)。 注意， 如果是上面提到的普通SDR方法，
r
=
[
1
,
0
,
⋯
,
0
]
\mathbf{r}=[1, 0, \cdots, 0]
r=[1,0,⋯,0]， 即
v
ˉ
\bar{\mathbf{v}}
vˉ等于最大特征向量。 而这里，引入了一个随机变量， 使得我们尝试更多种的
v
ˉ
\bar{\mathbf{v}}
vˉ， 再选出使得目标函数值最大的
v
ˉ
\bar{\mathbf{v}}
vˉ作为最优解。 可以看到， 这种方法其实就是通过遍历更多解来获得更好的性能。 最后， 还是把得到的
v
ˉ
\bar{\mathbf{v}}
vˉ转换为可行解：
v
=
e
j
arg
(
[
v
ˉ
v
ˉ
N
+
1
]
(
1
:
N
)
)
\boldsymbol{v}=e^{j \arg \left(\left[\frac{\bar{v}}{\bar{v}_{N+1}}\right]_{(1: N)}\right)}
v=ejarg([vˉN+1vˉ](1:N))。
代码
关于SDR 更细节一些的实现和相关代码， 在下一篇博文 经典的SDR算法（下）：SDR的具体使用细节与相关代码 进行了更详细的介绍。