解析一下 Boyd & Vandenberghe, “Convex Optimization”上的例子，重点在于其对偶形式是怎么得到的
Section 5.2.4: Solves a simple QCQP
输入数据
randn('state',13);
n = 6;
P0 = randn(n); P0 = P0'*P0 + eps*eye(n);
P1 = randn(n); P1 = P1'*P1;
P2 = randn(n); P2 = P2'*P2;
P3 = randn(n); P3 = P3'*P3;
q0 = randn(n,1); q1 = randn(n,1); q2 = randn(n,1); q3 = randn(n,1);
r0 = randn(1); r1 = randn(1); r2 = randn(1); r3 = randn(1);
优化代码
cvx_begin
variable x(n)
dual variables lam1 lam2 lam3
minimize( 0.5*quad_form(x,P0) + q0'*x + r0 )
lam1: 0.5*quad_form(x,P1) + q1'*x + r1 <= 0;
lam2: 0.5*quad_form(x,P2) + q2'*x + r2 <= 0;
lam3: 0.5*quad_form(x,P3) + q3'*x + r3 <= 0;
cvx_end
obj1 = cvx_optval;
计算对偶间隙
P_lam = P0 + lam1*P1 + lam2*P2 + lam3*P3;
q_lam = q0 + lam1*q1 + lam2*q2 + lam3*q3;
r_lam = r0 + lam1*r1 + lam2*r2 + lam3*r3;
obj2 = -0.5*q_lam'*inv(P_lam)*q_lam + r_lam;
disp('The duality gap is equal to ');
disp(obj1-obj2)
原目标
m
i
n
i
m
i
z
e
1
2
x
T
P
0
x
+
q
0
T
x
+
r
0
1
2
x
T
P
1
x
+
q
1
T
x
+
r
1
<
=
0
1
2
x
T
P
2
x
+
q
2
T
x
+
r
2
<
=
0
1
2
x
T
P
3
x
+
q
3
T
x
+
r
3
<
=
0
minimize \ \frac{1}{2}x^TP_0x+q_0^Tx+r_0\\ \frac{1}{2}x^TP_1x+q_1^Tx+r_1<=0\\ \frac{1}{2}x^TP_2x+q_2^Tx+r_2<=0\\ \frac{1}{2}x^TP_3x+q_3^Tx+r_3<=0
m
i
n
i
m
i
z
e
2
1
x
T
P
0
x
+
q
0
T
x
+
r
0
2
1
x
T
P
1
x
+
q
1
T
x
+
r
1
<
=
0
2
1
x
T
P
2
x
+
q
2
T
x
+
r
2
<
=
0
2
1
x
T
P
3
x
+
q
3
T
x
+
r
3
<
=
0
P
0
∈
S
+
+
,
P
1
,
P
2
,
P
3
∈
S
+
P_0 \in S_{++},P_1,P_2,P_3 \in S_+
P
0
∈
S
+
+
,
P
1
,
P
2
,
P
3
∈
S
+
,原目标是严格凸函数，有唯一极小解
拉格朗日的形式
L
(
x
,
λ
1
,
λ
2
,
λ
3
)
=
1
2
x
T
P
0
x
+
q
0
T
x
+
r
0
+
∑
i
=
1
3
λ
i
(
1
2
x
T
P
i
x
+
q
i
T
x
+
r
i
)
=
1
2
x
T
P
(
λ
)
x
+
q
(
λ
)
T
x
+
r
(
λ
)
P
(
λ
)
=
P
0
+
∑
i
=
1
3
λ
i
P
i
q
(
λ
)
=
q
0
+
∑
i
=
1
3
λ
i
q
i
r
(
λ
)
=
r
0
+
∑
i
=
1
3
λ
i
r
i
λ
⪰
0
\mathcal{L}(x,\lambda_1,\lambda_2,\lambda_3)=\frac{1}{2}x^TP_0x+q_0^Tx+r_0+\sum_{i=1}^3\lambda_i(\frac{1}{2}x^TP_ix+q_i^Tx+r_i)\\= \frac{1}{2}x^TP(\lambda)x+q(\lambda)^Tx+r(\lambda)\\ P(\lambda)=P_0+\sum_{i=1}^3\lambda_iP_i\\ q(\lambda)=q_0+\sum_{i=1}^3\lambda_iq_i\\ r(\lambda)=r_0+\sum_{i=1}^3\lambda_ir_i\\ \lambda\succeq 0
L
(
x
,
λ
1
,
λ
2
,
λ
3
)
=
2
1
x
T
P
0
x
+
q
0
T
x
+
r
0
+
i
=
1
∑
3
λ
i
(
2
1
x
T
P
i
x
+
q
i
T
x
+
r
i
)
=
2
1
x
T
P
(
λ
)
x
+
q
(
λ
)
T
x
+
r
(
λ
)
P
(
λ
)
=
P
0
+
i
=
1
∑
3
λ
i
P
i
q
(
λ
)
=
q
0
+
i
=
1
∑
3
λ
i
q
i
r
(
λ
)
=
r
0
+
i
=
1
∑
3
λ
i
r
i
λ
⪰
0
对偶形式
由于对偶变量
λ
⪰
0
\lambda\succeq 0
λ
⪰
0
,因此，
P
(
λ
)
∈
S
+
+
P(\lambda)\in S_{++}
P
(
λ
)
∈
S
+
+
对拉格朗日求导可以得到极小值的位置
L
(
x
,
λ
)
=
1
2
x
T
P
(
λ
)
x
+
q
(
λ
)
T
x
+
r
(
λ
)
→
P
(
λ
)
x
+
q
(
λ
)
=
0
→
x
=
−
P
(
λ
)
−
1
q
(
λ
)
\mathcal{L}(x,\lambda)=\frac{1}{2}x^TP(\lambda)x+q(\lambda)^Tx+r(\lambda)\rightarrow\\ P(\lambda)x+q(\lambda)=0\rightarrow x=-P(\lambda)^{-1}q(\lambda)
L
(
x
,
λ
)
=
2
1
x
T
P
(
λ
)
x
+
q
(
λ
)
T
x
+
r
(
λ
)
→
P
(
λ
)
x
+
q
(
λ
)
=
0
→
x
=
−
P
(
λ
)
−
1
q
(
λ
)
代入拉格朗日函数，得到对偶形式
g
(
λ
)
=
i
n
f
x
(
L
(
x
,
λ
)
)
=
−
1
2
q
(
λ
)
T
P
(
λ
)
−
1
q
(
λ
)
+
r
(
λ
)
λ
⪰
0
g(\lambda)=\underset{x}{inf}(\mathcal{L}(x,\lambda))=-\frac{1}{2}q(\lambda)^TP(\lambda)^{-1}q(\lambda)+r(\lambda)\\\lambda\succeq 0
g
(
λ
)
=
x
in
f
(
L
(
x
,
λ
)
)
=
−
2
1
q
(
λ
)
T
P
(
λ
)
−
1
q
(
λ
)
+
r
(
λ
)
λ
⪰
0
参考
http://web.cvxr.com/cvx/examples/cvxbook/Ch05_duality/html/qcqp.html