当前位置: 首页 > >

Second-Order Cone Programming(SOCP) 二阶锥规划

发布时间:


个人博客Glooow,欢迎各位老师来踩踩





文章目录
1. 二阶锥1.1 二阶锥定义1.2 二阶锥约束
2. 优化问题建模3. 类似问题转化3.1 二次规划3.2 随机线性规划
4. 问题求解



1. 二阶锥
1.1 二阶锥定义

在此之前,先给出二阶锥的定义。







k



k


k 维空间中二阶锥 (Second-order cone) 的定义为






C


k



=



{



[






u








t






]



?


u






R



k


?


1




,


t





R


,





u








t


}




mathcal{C}_{k}=left{left[egin{array}{l} {u} \ {t} end{array} ight] | u in mathbb{R}^{k-1}, t in mathbb{R},|u| leq t ight}


Ck?={[ut?]?u∈Rk?1,t∈R,∥u∥≤t}
其也被称为 quadratic,ice-cream,Lorentz cone。


1.2 二阶锥约束

在此基础上,二阶锥约束即为








A


x


+


b









c


T



x


+


d


?



[






A









c


T







]



x


+



[






b








d






]







C


k




|A x+b| leq c^{T} x+d Longleftrightarrowleft[egin{array}{c} {A} \ {c^{T}} end{array} ight] x+left[egin{array}{l} {b} \ {d} end{array} ight] in mathcal{C}_{k}


∥Ax+b∥≤cTx+d?[AcT?]x+[bd?]∈Ck?
其中




x






R


n



,


A






R



(


k


?


1


)


×


n




,


b






R



k


?


1




,


c






R


n



,


R



xin mathbb{R}^{n}, Ainmathbb{R}^{(k-1) imes n}, binmathbb{R}^{k-1},cinmathbb{R}^{n},mathbb{R}


x∈Rn,A∈R(k?1)×n,b∈Rk?1,c∈Rn,R。实际上是对




x



x


x 进行了仿射变换,由于仿射变换不改变凹凸性,因此二阶锥也是凸锥。


2. 优化问题建模

优化目标如下,其中




f






R


n



,



A


i







R




n


i



×


n




,



b


i







R



n


i




,



c


i







R


n



,



d


i






R


,


F






R



p


×


n




,



f in mathbb{R}^{n}, A_{i} in mathbb{R}^{n_{i} imes n}, b_{i} in mathbb{R}^{n_{i}}, c_{i} in mathbb{R}^{n}, d_{i} in mathbb{R}, F in mathbb{R}^{p imes n},


f∈Rn,Ai?∈Rni?×n,bi?∈Rni?,ci?∈Rn,di?∈R,F∈Rp×n, and




g






R


p



,


x






R


n




g in mathbb{R}^{p}, x in mathbb{R}^{n}


g∈Rp,x∈Rn









minize











f


T



x










subject?to

















A


i



x


+



b


i







2







c


i


T



x


+



d


i



,



i


=


1


,





,


m


















F


x


=


g








egin{aligned} ext{minize}quad& f^{T} x\ ext{subject to}quad& {left|A_{i} x+b_{i} ight|_{2} leq c_{i}^{T} x+d_{i}, quad i=1, ldots, m}\ &{F x=g} end{aligned}


minizesubject?to?fTx∥Ai?x+bi?∥2?≤ciT?x+di?,i=1,…,mFx=g?
上述问题被称为二次锥规划是因为其约束,要求仿射函数




(


A


x


+


b


,



c


T



x


+


d


)



(Ax+b,c^T x+d)


(Ax+b,cTx+d) 为





R



k


+


1





mathbb{R}^{k+1}


Rk+1 空间中的二阶锥。


3. 类似问题转化

一些其他优化问题也可以转化为 SOCP,例如


3.1 二次规划

考虑二次约束






x


T




A


T



A


x


+



b


T



x


+


c





0



x^{T} A^{T} A x+b^{T} x+c leq 0


xTATAx+bTx+c≤0
可以等价转化为 SOC 约束
















(


1


+



b


T



x


+


c


)



/


2










A


x











2







(


1


?



b


T



x


?


c


)



/


2



left|egin{array}{c}left(1+b^{T} x+c ight) / 2 \ Axend{array} ight|_{2} leqleft(1-b^{T} x-c ight) / 2


∥∥∥∥?(1+bTx+c)/2Ax?∥∥∥∥?2?≤(1?bTx?c)/2


3.2 随机线性规划

问题模型为









minize











c


T



x










subject?to










P



(



a


i


T



x






b


i



)






p


,



i


=


1


,





,


m







egin{aligned} ext{minize}quad& c^{T} x\ ext{subject to}quad& mathbb{P}left(a_{i}^{T} x leq b_{i} ight) geq p, quad i=1, ldots, m end{aligned}


minizesubject?to?cTxP(aiT?x≤bi?)≥p,i=1,…,m?
问题转化可参考维基百科


4. 问题求解

二阶锥规划可以应用内点法快速求解,且比半正定规划(semidefinite programming)更有效。


Matlab 有专门的凸优化工具包,下载地址在这里,安装教程在官网上有。使用方法如下,只需要修改优化目标和约束条件即可


m = 20; n = 10; p = 4;
A = randn(m,n); b = randn(m,1);
C = randn(p,n); d = randn(p,1); e = rand;
cvx_begin
variable x(n)
minimize( norm( A * x - b, 2 ) )
subject to
C * x == d
norm( x, Inf ) <= e
cvx_end



友情链接: