经典的SDR算法：用半正定松弛法（SemidefiniteRelaxation）求解二次优化问题
经典的SDR 算法：⽤半正定松弛法（SemidefiniteRelaxation ）求解⼆次优化问
题
前⾔
本⽂是博主对于 Zhi-quan Luo ⽼师的经典著作 《Semidefinite Relaxation of Quadratic Optimization Problems》 的读书笔记，希望可作为对全⽂以中⽂形式的核⼼梳理。
单⼑直⼊
⾸先， Semidefinite Relaxation (SDR) 适⽤的问题可以写为如下形式：
有⼏个注意点：
暂时定义在实数域上， 但复数域有类似的结论。
表⽰ , ,  的 其中之⼀。也就是说， 只要限制条件是⼆次约束即可。，  都是对称矩阵。 即, 。
显然， ⽬标函数和限制条件中都有两个， 因此这类问题也被称为 ⼆次约束⼆次规划 (quadratically
constrained quadratic programs, QCQP) 问题。 需要注意的是， 这并不是⼀个凸问题。 因为  和  都并⾮⼀个凸集。
⽽SDR⽅法的⽬的就是将问题转化为⼀个凸问题从⽽求解。
我们引⼊⼀个新的变量 ， 并以此为优化变量， 那么问题(1)可以被写为：
详细解释⼀下这⼀步的转化：
注意到 (1) 的 ⽬标函数 显然是⼀个标量。 ⽽标量可以看成⼀个 的矩阵， 且迹等于本⾝。 即 。 ⽽根据迹的性质， 有 。 也就是说， 。 这也就变成了 (2)中的⽬标函数。 那么 (2) 中的限制条件，也就可以根据相同的变换轻易得到。
相⽐于(1)， (2)中多了两个限制条件， 这是由于  引⼊的。 显然， 因为的所有列都线性相关。 也因此，只有⼀个特征值等于 ，显然是⼤于0的，所以肯定是半正定矩阵。这⼀步转化的意义在哪呢？
事实上， 除了  这个限制以外， 整个问题是⼀个凸问题。 由于迹函数是个仿射变换， 很容易证明其凸性。 ⽽半正定约束也显然是个凸集， 因为两个半正定矩阵的和⼀定也是⼀个半正定矩阵。
因此， ⼯程上很⾃然的想法就是， **暂时得忽略 该约束， 并通过凸优化⽅法 （事实上以CVX⼯具包
为代表的内点法数值算法）来求解出⼀个解 . 这⼀步⼤家百度下CVX的使⽤就可以了，没有任何障碍。
x ∈R n
min
< x Cx
T x A x ⊵b ,i =1,…,m
T
i i i (1)
⊵i ≥≤=C A i C ,A ,…,A ∈1m S n x x A x >T i 0x A x =T i 0X =xx T X ∈S n min
< Tr(CX )
Tr A X ⊵b ,i =1,…,m ,(i )i i X ⪰0,rank(X )=1
(2)
x Cx T 1×1tr(x Cx )=T x Cx T tr(AB )=tr(BA )tr(x Cx )=T tr(Cxx )=T tr(CX )X =xx T rank(X )=1X x x T rank(X )=1rank(X )=1X
⽽问题的关键点在于，始终我们问题需要得到的是，⽽⾮。 如果通过凸优化求出的刚好就是⼀个的矩阵，那么可以直接得到（对X做个SVD或EVD啥的都可以）。 但更多时候， 没有道理是⼀个 的矩阵。 也就是说， 根本不存在⼀个，使得 。
⼯程实现
那么SDR要解决的另⼀个问题就是如何从中恢复出⼀个满⾜原问题约束的。出于⼯程实现⾓度的思路其实⾮常清晰， 我们可以直接求解下⾯的问题以获得 ：
即⼀个最接近的 。 这个问题很经典了，⽽他的闭式解就是， 是的最⼤特征向量乘以最⼤特征值的平⽅根。 即， 将的特征值分解表⽰为：
其中， ，代表第⼤的特征值和对应的特征向量。 那么(3)的最优解 就是 。
孝心小故事但是，问题⼜出现了！ 虽然满⾜了(2)中的所有的约束， 但由于在这⼀步中，(3)中求得的是⼀个近似的结果。 此时得到的，不⼀定满⾜原问题(1)中的约束了！ 也就是说， 经过⼀顿转化之后， 求得的并不是原问题的可⾏解！此时怎么办呢？ 解决⽅案也⾮常符合⼯程思维：直接从出发⼀个离最近的可
⾏解， 这就是SDR的最终结果。最后提两点：
直接从出发⼀个离最近的可⾏解， 这本⾝就是⼀个独⽴的问题， 具体问题具体分析，后⾯会给⼀个具体的例⼦。毫⽆疑问，在SDR中有许许多多的近似，⼯程处理。 因此， SDR的解远⾮全局最优解。
具体实例
为节约篇幅， 本⽂只讲⼀个例⼦。 也不是论⽂中给出的， ⽽是HBF混合波束成形的经典论⽂ 《Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems》中的 ⼀个使⽤。 有兴趣的读者也可以去看 SDR论⽂的原⽂， 接触更多的例⼦。
以HBF为例， 作者将问题转化为了如下的形式， 熟悉HBF的读者应该很亲切了：
作者使⽤了 SDR作为⼀种算法来求解该问题。 那么⾸先， 为什么会选⽤ SDR呢？ 因为可以看到， ⽬标函数和限制条件都是⼆次形式，这就是我们之前说到的SDR⽬标问题：QCQP问题。 接下来，通过这个例⼦展⽰如果实战使⽤SDR。
x X X rank(X )=1x X rank(X )=1x X =xx T X x x ∥X −x
min
xx ∥T F
2
(3)
X xx T x X X X =
⋆
λq q i =1
∑
r同学录祝福语
i i i
T
λi q i i x =x
~
q λ11X x x x x x x x F BB手机怎么连接wifi
minimize
subject to F −F F ∥opt RF BB ∥F
2
F =
∥BB ∥F
2
N t
N N RF t
漫反射s (4)
⾸先， 刚刚介绍SDR时都是向量形式的变量, ⽽(4)中都是矩阵，不利于处理， 因此第⼀步先进⾏列化：
进⾏变量代换后 (, and ，原问题可写为：
**这⾥必须强调的⼀点是， 作者引⼊了 这样⼀个辅助变量。这是SDR的常见技巧之⼀！**接下来阐释这个的作⽤。
⾸先， 对于原问题的影响上：以(5)求解之后， 如果得到， 那么就是(4）的最优解。 ⽽如果， 那么就是(4)的最优解的相反数， 仍等效于得到了最优解。
其次， 加⼊这个辅助变量后， 可以更好地将(5)写成SDR的标准形式。 继续看：⽬标函数可以写为：
注意到： 此时令 , , 上式就等于 ，⽽是个显然的半正定矩阵：，⼀个矩阵的共轭转置乘以本⾝肯定是半正定矩阵（可从特征值⾓度得证）。那么(5)中的另外两个约束⼜可以转换为：
⼤家可以细致体会下， 为什么SDR可以应⽤⼴泛的原因， 因为⼤部分⼆次约束都可以通过稍加构造就写成QCQP的形式。那么，最后经过⼀步变量代换：
x F −
F F ∥opt RF BB ∥F
2
=vec F −
F F ∥(opt RF BB )∥2
2
=vec F −vec F F ∥(opt )(RF BB )∥22
=
vec F −I ⊗
F vec F .
∥(opt )
(N s RF )(BB )∥22
f =vec F (opt )b =vec F (BB )E =I ⊗N s F .RF ∥t f −Eb ∥b
minimize
网站设计是什么专业2
2
subject to
{∥b ∥=
22N t
N N RF t
s t =1
2
(5)
t t t =1f t =−1f t ∥t f −Eb ∥=22
[b
H t ][E E H −f E H −E f H f f H
][b t ]
y =[b t ]C =[E E H −f E
H
土家族的饮食−E f
H f f H ]y Cy H C C =[E ,−f ][E ,−f ]H ∥b ∥22
t 2==[
b H
t ][I N N RF s 000][
b t ]N t N N RF s
==1
[b
H
t ][0N N RF t
s 001][
b
t ]y =,Y =yy ,C =[b t ]H [E E H −f E
H
−E f
H f f H ]A =,A =1[I N N RF t s 0
00]2[0N N RF t s 00
1]
（5）终于可写为SDR的标准形式：
通过松弛掉最后⼀个约束， 问题就可以通过凸优化直接求解。
最后必须强调， 如何从中恢复出（即原问题真正的⽬标）。 ⾸先，⽤特征值分解得到。 此时 的最后⼀个元素⼤概率不是1，⽽按照定义案例应该必须是。此时处理⽅式很简单， 直接对最后⼀个元素取正负号， 强⾏归成或即可。 ⽽（ 的前⾯的元
素）也不符合的约束，此时的做法就是将强⾏归⼀化成即可。 操作⾮常简单， 那么其对应的思路就是我们
在上⽂中提到的：当得到了后， 以离最近的可⾏解作为原问题的解。
实例2
再举个近期的实例好了。 是来⾃于 智能反射⾯相关paper 《Intelligent Reflecting Surface Enhanced Wireless
Network: Joint Active and Passive Beamforming Design》中， 对于passive beamforming 的设计， 同样使⽤了 SDR 算法。原问题可以转化为这样的形式：
简单⽽⾔， 就是其余参数都已给定， 要求优化向量， 其中的每个元素需要满⾜恒模约束。那么同样的， 可以通过引⼊辅助变量 ， 把问题转换为 齐次的 QCQP 问题：
其中，
那么根据SDR的⽅法， 令 , 就可以将问题转化为：
当然这⾥同样的放松掉了这⼀约束。 可以看到， 上述问题已经是凸问题了， 因为⾮凸的恒模约束经过转化后变成了
， 这⽆疑是⼀个凸约束 （可以⽤凸集的定义轻松得证）。
因此， SDR也是处理恒模约束的⼀种思路。
注意， 这个例⼦的后续处理，也是从SDR解获得原问题可⾏解的⼀种经典思路：SDR + Gaussian randomization. 这种处理相⽐于上⾯提到的直接寻欧⽒距离最近的，会有通过复杂度提升换来的⼀定性能增益。
CY )
Y ∈H
n
minimize Tr ( subject to
⎩
⎨⎧Tr A Y =(1)N t
N N RF t
s
Tr A Y =1(2)Y ⪰0,rank(Y )=1Y b y y t 1或−11−1b y ∥b ∥=
2
2
N t N N RF t
s
b ∥b ∥=
2
2
N t N N RF t
s
x x max v  s.t. v ΦΦv +v Φh +h Φv H H H d d H
H v =1,∀n =1,⋯,N
∣n ∣v v t max v  s.t. R v H v =1,∀n =1,⋯,N +1
∣v ˉn ∣R =,
=[ΦΦH
h Φ
d H H Φh d
0]v [v t ]
V =v ˉv ˉH max V
<
tr(RV )
V =1,∀n =1,⋯,N +1,n ,n V ⪰0
rank(V )=1V =n ,n 1,∀n =1,⋯,N +1V v
⾸先， 对进⾏ EVD分解， 得到， 此时， 我们令 ， 其中。 注意， 如果是上⾯提到的普通SDR⽅法， ， 即等于最⼤特征向量。 ⽽这⾥，引⼊了⼀个随机变量， 使得我们尝试更多种的， 再选出使得⽬标函数值最⼤的作为最优解。 可以看到， 这种⽅法其实就是通过遍历更多解来获得更好的性能。 最后， 还是把得到的转换为可⾏解：
。
代码
关于SDR 更细节⼀些的实现和相关代码， 在下⼀篇博⽂ 进⾏了更详细的介绍。
V V =UΣU H =v UΣr 1/2r ∈CN 0,I (N +1)r =[1,0,⋯,0]v ˉv ˉv ˉv ˉv =e
j a rg ([v
ˉN +1v ˉ
](1:N ))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。