概述
文章目录
- 输入数据
- 优化代码
- 计算对偶间隙
- 原目标
- 拉格朗日的形式
- 对偶形式
- 参考
解析一下 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
minimize 21xTP0x+q0Tx+r021xTP1x+q1Tx+r1<=021xTP2x+q2Tx+r2<=021xTP3x+q3Tx+r3<=0
P
0
∈
S
+
+
,
P
1
,
P
2
,
P
3
∈
S
+
P_0 in S_{++},P_1,P_2,P_3 in S_+
P0∈S++,P1,P2,P3∈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}^3lambda_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}^3lambda_iP_i\ q(lambda)=q_0+sum_{i=1}^3lambda_iq_i\ r(lambda)=r_0+sum_{i=1}^3lambda_ir_i\ lambdasucceq 0 L(x,λ1,λ2,λ3)=21xTP0x+q0Tx+r0+i=1∑3λi(21xTPix+qiTx+ri)=21xTP(λ)x+q(λ)Tx+r(λ)P(λ)=P0+i=1∑3λiPiq(λ)=q0+i=1∑3λiqir(λ)=r0+i=1∑3λiriλ⪰0
对偶形式
由于对偶变量
λ
⪰
0
lambdasucceq 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)=0rightarrow x=-P(lambda)^{-1}q(lambda)
L(x,λ)=21xTP(λ)x+q(λ)Tx+r(λ)→P(λ)x+q(λ)=0→x=−P(λ)−1q(λ)
代入拉格朗日函数，得到对偶形式
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)\lambdasucceq 0
g(λ)=xinf(L(x,λ))=−21q(λ)TP(λ)−1q(λ)+r(λ)λ⪰0
参考
http://web.cvxr.com/cvx/examples/cvxbook/Ch05_duality/html/qcqp.html
最后
以上就是典雅枕头为你收集整理的二次规划的对偶形式(CVX)的全部内容，希望文章能够帮你解决二次规划的对偶形式(CVX)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复