优化问题-半正定规划（Semi-Definite Program, SDP）

文章目录

背景
SDP的两种形式
QCQP和SOCP转化为SDP
SDP在组合优化中的应用
SDR的一些例子
- 下行发送功率最小化

背景

半正定规划（Semi-Definite Program, SDP）在MIMO无线通信相关的信号处理中具有广泛的应用，在某些场景可以分析证明SDP的得到的解释原问题的全局最优化或者次优解。因此，对其做一个简要介绍，同时其与LPQP、QCQP、SOCP的关系。

符号说明：
X

⪰

0

\mathbf{X} \succeq \mathbf{0}

X⪰0代表PSD矩阵，

x

⪰

0

\mathbf{x} \succeq \mathbf{0}

x⪰0代表列向量的每个元素均大于等于0。

SDP的两种形式

不等式形式：

min

⁡

c

T

x

s.t.

F

(

x

)

⪯

0

\begin{array}{ll}\min & \mathbf{c}^{\mathrm{T}} \mathbf{x} \\ \text { s.t. } & \mathbf{F}(\mathbf{x}) \preceq \mathbf{0}\end{array}

min s.t. cTxF(x)⪯0

其中

∈

\mathbf{c} \in \mathbb{R}^n

c∈Rn，求解变量

∈

\mathbf{x} \in \mathbb{R}^n

x∈Rn。约束条件为线性矩阵不等式。即：

(

)

⋯

\mathbf{F}(\mathbf{x})=\mathbf{F}_0+x_1 \mathbf{F}_1+\cdots+x_n \mathbf{F}_n

F(x)=F0+x1F1+⋯+xnFn

注：若具有多个LMI约束，可以归结为只有一个LMI约束，其等价于：

DIAG

⁡

(

)

…

(

)

⪯

\operatorname{DIAG}\left(\mathbf{F}_1(\mathbf{x}), \ldots, \mathbf{F}_m(\mathbf{x})\right) \preceq \mathbf{0}

DIAG(F1(x),…,Fm(x))⪯0

标准形式：

min

⁡

Tr

⁡

(

C

X

)

s.t.

X

⪰

0

Tr

⁡

(

A

i

X

)

=

b

i

∈

R

,

i

=

1

,

…

,

m

\begin{array}{cl} \min & \operatorname{Tr}(\mathbf{C X}) \\ \text { s.t. } & \mathbf{X} \succeq \mathbf{0} \\ & \operatorname{Tr}\left(\mathbf{A}_i \mathbf{X}\right)=b_i \in \mathbb{R}, i=1, \ldots, m \end{array}

min s.t. Tr(CX)X⪰0Tr(AiX)=bi∈R,i=1,…,m

其中，

A

i

∈

S

n

,

C

∈

S

n

\mathbf{A}_i \in \mathbb{S}^n, \mathbf{C} \in \mathbb{S}^n

Ai∈Sn,C∈Sn，变量

X

∈

S

n

\mathbf{X} \in \mathbb{S}^n

X∈Sn。

注：不等式形式和标准形式是等价的，后面将证明。

QCQP和SOCP转化为SDP

引入一个重要的定理：Schur补定理。

其定义如下：

假设

∈

\mathbf{A} \in \mathbb{S}_{++}^n, \mathbf{C} \in \mathbb{S}^m

A∈S++n,C∈Sm，则当且仅当

≜

−

⪰

\mathbf{S}_{\mathbf{A}} \triangleq \mathbf{C}-\mathbf{B}^{\mathrm{T}} \mathbf{A}^{-1} \mathbf{B} \succeq \mathbf{0}

SA≜C−BTA−1B⪰0成立时有：

≜

[

]

⪰

\mathbf{S} \triangleq\left[\begin{array}{cc} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{\mathrm{T}} & \mathbf{C} \end{array}\right] \succeq \mathbf{0}

S≜[ABTBC]⪰0

反之亦然。

因此，凸二次不等式：

(

)

(

)

−

⩽

∀

∈

(\mathbf{A x}+\mathbf{b})^{\mathrm{T}}(\mathbf{A x}+\mathbf{b})-\mathbf{c}^{\mathrm{T}} \mathbf{x}-d \leqslant 0, \forall \mathbf{x} \in \mathbb{R}^n

(Ax+b)T(Ax+b)−cTx−d⩽0,∀x∈Rn成立的充要条件是如下的LMI成立：

[

(

)

]

⪰

∀

∈

\left[\begin{array}{cc} \mathbf{I} & \mathbf{A x}+\mathbf{b} \\ (\mathbf{A x}+\mathbf{b})^{\mathrm{T}} & \mathbf{c}^{\mathrm{T}} \mathbf{x}+d \end{array}\right] \succeq \mathbf{0}, \forall \mathbf{x} \in \mathbb{R}^n

[I(Ax+b)TAx+bcTx+d]⪰0,∀x∈Rn

QCQP问题：

考虑凸QCQP问题：

min

⁡

x

∈

R

n

∥

A

0

x

+

b

0

∥

2

2

−

c

0

T

x

−

d

0

s.t.

∥

A

i

x

+

b

i

∥

2

2

−

c

i

T

x

−

d

i

⩽

0

,

i

=

1

,

…

,

m

\begin{aligned} \min _{\mathbf{x} \in \mathbb{R}^n} &\left\|\mathbf{A}_0 \mathbf{x}+\mathbf{b}_0\right\|_2^2-\mathbf{c}_0^{\mathrm{T}} \mathbf{x}-d_0 \\ \text { s.t. } &\left\|\mathbf{A}_i \mathbf{x}+\mathbf{b}_i\right\|_2^2-\mathbf{c}_i^{\mathrm{T}} \mathbf{x}-d_i \leqslant 0, i=1, \ldots, m \end{aligned}

x∈Rnmin s.t. ∥A0x+b0∥22−c0Tx−d0∥Aix+bi∥22−ciTx−di⩽0,i=1,…,m

其上镜图形式可以表示为：

min

⁡

x

∈

R

n

,

t

∈

R

t

s.t.

[

I

A

0

x

+

b

0

(

A

0

x

+

b

0

)

T

c

0

T

x

+

d

0

+

t

]

⪰

0

[

I

A

i

x

+

b

i

(

A

i

x

+

b

i

)

T

c

i

T

x

+

d

i

]

⪰

0

,

i

=

1

,

…

,

m

\begin{array}{rl} \min _{\mathbf{x} \in \mathbb{R}^n, t \in \mathbb{R}} & t \\ \text { s.t. } & {\left[\begin{array}{cc} \mathbf{I} & \mathbf{A}_0 \mathbf{x}+\mathbf{b}_0 \\ \left(\mathbf{A}_0 \mathbf{x}+\mathbf{b}_0\right)^{\mathrm{T}} & \mathbf{c}_0^{\mathrm{T}} \mathbf{x}+d_0+t \end{array}\right] \succeq \mathbf{0}} \\ & {\left[\begin{array}{cc} \mathbf{I} & \mathbf{A}_i \mathbf{x}+\mathbf{b}_i \\ \left(\mathbf{A}_i \mathbf{x}+\mathbf{b}_i\right)^{\mathrm{T}} & \mathbf{c}_i^{\mathrm{T}} \mathbf{x}+d_i \end{array}\right] \succeq \mathbf{0}, i=1, \ldots, m} \end{array}

minx∈Rn,t∈R s.t. t[I(A0x+b0)TA0x+b0c0Tx+d0+t]⪰0[I(Aix+bi)TAix+biciTx+di]⪰0,i=1,…,m

该问题是SDP
SOCP问题：

同样地，对于二阶锥不等式：

∥

A

x

+

b

∥

2

⩽

f

T

x

+

d

,

x

∈

R

n

\|\mathbf{A} \mathbf{x}+\mathbf{b}\|_2 \leqslant \mathbf{f}^{\mathrm{T}} \mathbf{x}+d, \mathbf{x} \in \mathbb{R}^n

∥Ax+b∥2⩽fTx+d,x∈Rn，其可以表示为

f

T

x

+

d

−

1

f

T

x

+

d

(

A

x

+

b

)

T

(

A

x

+

b

)

⩾

0

,

x

∈

R

n

\mathbf{f}^{\mathrm{T}} \mathbf{x}+d-\frac{1}{\mathbf{f}^{\mathrm{T}} \mathbf{x}+d}(\mathbf{A} \mathbf{x}+\mathbf{b})^{\mathrm{T}}(\mathbf{A} \mathbf{x}+\mathbf{b}) \geqslant 0, \quad \mathbf{x} \in \mathbb{R}^n

fTx+d−fTx+d1(Ax+b)T(Ax+b)⩾0,x∈Rn，根据Schur补，其等价为LMI：

[

(

f

T

x

+

d

)

I

m

A

x

+

b

(

A

x

+

b

)

T

f

T

x

+

d

]

⪰

0

,

x

∈

R

n

\left[\begin{array}{cc} \left(\mathbf{f}^{\mathrm{T}} \mathbf{x}+d\right) \mathbf{I}_m & \mathbf{A x}+\mathbf{b} \\ (\mathbf{A x}+\mathbf{b})^{\mathrm{T}} & \mathbf{f}^{\mathrm{T}} \mathbf{x}+d \end{array}\right] \succeq \mathbf{0}, \quad \mathbf{x} \in \mathbb{R}^n

[(fTx+d)Im(Ax+b)TAx+bfTx+d]⪰0,x∈Rn

SDP在组合优化中的应用

考虑如下的Boolean二次规划（BQP）问题：

max

⁡

s.t.

∈

{

−

}

…

(即

∈

{

−

}

)

\begin{aligned} \max &\qquad \mathrm{x}^{\mathrm{T}} \mathbf{C x} \\ \text { s.t. } &\quad\left.x_i \in\{-1,+1\}, i=1, \ldots, n \text { (即 } \mathbf{x} \in\{-1,+1\}^n\right) \end{aligned}

max s.t. xTCxxi∈{−1,+1},i=1,…,n (即 x∈{−1,+1}n)

分析：当

⪰

\mathbf{C} \succeq \mathbf{0}

C⪰0时，该目标函数为凸函数，但约束问题等于非仿射射约束

…

x_i^2=1, i=1, \ldots, n

xi2=1,i=1,…,n，故该问题是非凸的。青桔发求解BQP的复杂度是

2^n

2n。接下来将以此为例子讨论如何通过半正定松弛（Semi-Definite Relaxation, SDR）求解BQP问题。

首先引入如下辅助变量：

\mathbf{X}=\mathbf{xx}^{\mathbf{T}}

X=xxT，原BQP问题等价为：

max

⁡

(

)

s.t.

[

]

…

\begin{aligned} \max _{\mathbf{x}, \mathbf{X}} & \quad\operatorname{Tr}(\mathbf{C X}) \\ \text { s.t. } &\quad \mathbf{X}=\mathbf{x x}^{\mathrm{T}} \\ & \quad{[\mathbf{X}]_{i i}=1, i=1, \ldots, n } \end{aligned}

x,Xmax s.t. Tr(CX)X=xxT[X]ii=1,i=1,…,n

分析

\mathbf{X}=\mathbf{xx}^{\mathbf{T}}

X=xxT（

\mathbf{X}

X是秩-1的PSD矩阵），等价于

⟺

⪰

且

rank

⁡

(

)

\mathbf{X}=\mathrm{xx}^{\mathrm{T}} \Longleftrightarrow \mathbf{X} \succeq \mathbf{0} \text { 且 } \operatorname{rank}(\mathbf{X})=1

X=xxT⟺X⪰0 且 rank(X)=1

如果去掉秩-1约束，放松为

⪰

\mathrm{X} \succeq 0

X⪰0（这种去掉秩-1约束的松弛方法称为：SDR），可以得到如下的SDP问题：

max

⁡

(

)

s.t.

⪰

[

]

…

\begin{aligned} \max & \quad\operatorname{Tr}(\mathbf{C X}) \\ \text { s.t. } & \quad\mathbf{X} \succeq \mathbf{0} \\ &\quad {[\mathbf{X}]_{i i}=1, i=1, \ldots, n } \end{aligned}

max s.t. Tr(CX)X⪰0[X]ii=1,i=1,…,n

该SDP问题成为前者优化问题的BQP。前者的约束集包含后者的约束集合，即SDP问题是原问题的一个下界。

如果SDP问题得以解决，其秩恰好为1，通过特征值分解：

⋆

\mathbf{X}^{\star}=\mathbf{x}^{\star} \mathbf{x}^{\star T}

X⋆=x⋆x⋆T可以得到原问题最优解，若秩不为1，则可以通过两种方法得到原问题的近似解：

秩-1近似：选
X

\mathbf{X}

X的主特征向量

x

^

\widehat{\mathbf{x}}

x
，再利用

[

x

^

]

i

=

sgn

⁡

(

[

x

~

]

i

)

[\widehat{\mathbf{x}}]_i=\operatorname{sgn}\left([\tilde{\mathbf{x}}]_i\right)

[x
]i=sgn([x~]i)得到近似解
高斯随机化：产生
L

L

L个服从均值为

0

\mathbf{0}

0，协方差矩阵为

X

∗

\mathbf{X}^*

X∗的高斯随机向量

{

ξ

(

ℓ

)

,

ℓ

=

1

,

…

,

L

}

\left\{\boldsymbol{\xi}^{(\ell)}, \ell=1, \ldots, L\right\}

{ξ(ℓ),ℓ=1,…,L}，再将其量化进行如下量化：

[

x

^

(

ℓ

)

]

i

=

sgn

⁡

(

[

ξ

(

ℓ

)

]

i

)

,

∀

i

\left[\widehat{\mathbf{x}}^{(\ell)}\right]_i=\operatorname{sgn}\left(\left[\boldsymbol{\xi}^{(\ell)}\right]_i\right), \quad \forall i

[x
(ℓ)]i=sgn([ξ(ℓ)]i),∀i，最后得到

x

^

=

x

^

(

ℓ

∗

)

\widehat{\mathbf{x}}=\widehat{\mathbf{x}}^{\left(\ell^*\right)}

x
=x
(ℓ∗)，其中：

ℓ

⋆

=

arg

⁡

max

⁡

ℓ

=

1

,

…

,

L

(

x

^

(

ℓ

)

)

T

C

x

^

(

ℓ

)

\ell^{\star}=\arg \max _{\ell=1, \ldots, L}\left(\widehat{\mathbf{x}}^{(\ell)}\right)^{\mathrm{T}} \mathbf{C} \widehat{\mathbf{x}}^{(\ell)}

ℓ⋆=argmaxℓ=1,…,L(x
(ℓ))TCx
(ℓ)

注：在很多时候，高斯随机化方法得到的近似解优于秩1近似解。

SDR的一些例子

下行发送功率最小化

考虑如下下行广播信道的波束成形问题：

…

y_i=\mathbf{h}_i^{\mathrm{T}} \mathbf{f} s+v_i, i=1, \ldots, n

yi=hiTfs+vi,i=1,…,n

承载信号

∈

s \in \mathbb{C}

s∈C满足：

{

∣

}

\mathbb{E}\left\{|s|^2\right\}=1

E{∣s∣2}=1

该问题对发射功率最小化，并保证每个接收端的SNR不小于阈值

\gamma_0

γ0，即：

∣

⩾

…

\gamma_i=\frac{\left|\mathbf{h}_i^{\mathrm{T}} \mathbf{f}\right|^2}{\sigma_i^2} \geqslant \gamma_0, i=1, \ldots, n

γi=σi2∣∣hiTf∣∣2⩾γ0,i=1,…,n

有：

∣

(

)

∗

⁡

(

∗

)

\left|\mathbf{h}_i^{\mathrm{T}} \mathbf{f}\right|^2=\left(\mathbf{h}_i^{\mathrm{T}} \mathbf{f}\right) \mathbf{f}^{\mathrm{H}} \mathbf{h}_i^*=\operatorname{Tr}\left(\mathbf{f f}^{\mathrm{H}} \mathbf{h}_i^* \mathbf{h}_i^{\mathrm{T}}\right)

∣∣hiTf∣∣2=(hiTf)fHhi∗=Tr(ffHhi∗hiT)，令

∗

(

)

\mathbf{Q}_i=\mathbf{h}_i^* \mathbf{h}_i^{\mathrm{T}} /\left(\gamma_0 \sigma_i^2\right)

Qi=hi∗hiT/(γ0σi2)，有优化问题如下：

min

⁡

∥

s.t.

⁡

(

)

⩾

…

\begin{aligned} \min &\quad\|\mathbf{f}\|_2^2 \\ \text { s.t. } & \quad\operatorname{Tr}\left(\mathbf{f} \mathbf{f}^{\mathrm{H}} \mathbf{Q}_i\right) \geqslant 1, i=1, \ldots, n \end{aligned}

min s.t. ∥f∥22Tr(ffHQi)⩾1,i=1,…,n

该问题非凸，并且是NP-hard的。原问题等价为：

min

⁡

∈

⁡

(

)

s.t.

⁡

(

)

⩾

…

\begin{aligned} \min _{\mathbf{f} \in \mathbb{C}^m, \mathbf{F} \in \mathbb{H}^m} & \quad\operatorname{Tr}(\mathbf{F}) \\ \text { s.t. } & \quad\mathbf{F}=\mathbf{f f}^{\mathrm{H}}, \operatorname{Tr}\left(\mathbf{F} \mathbf{Q}_i\right) \geqslant 1, i=1, \ldots, n \end{aligned}

f∈Cm,F∈Hmmin s.t. Tr(F)F=ffH,Tr(FQi)⩾1,i=1,…,n

利用SDR近似，有：

min

⁡

(

)

s.t.

⪰

⁡

(

)

⩾

…

\begin{array}{ll} \min & \operatorname{Tr}(\mathbf{F}) \\ \text { s.t. } & \mathbf{F} \succeq \mathbf{0}, \operatorname{Tr}\left(\mathbf{F} \mathbf{Q}_i\right) \geqslant 1, i=1, \ldots, n \end{array}

min s.t. Tr(F)F⪰0,Tr(FQi)⩾1,i=1,…,n

在RIS 、HBF中也有诸多应用，但是基本的原理万变不离其宗，太多例子，不再赘述。

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/cb5dfab70f.html