Second-order cone programming

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (October 2011) (Learn how and when to remove this message)

A second-order cone program (SOCP) is a convex optimization problem of the form

minimize ${\displaystyle \ f^{T}x\ }$

subject to

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,m}$

${\displaystyle Fx=g\ }$

where the problem parameters are ${\displaystyle f\in \mathbb {R} ^{n},\ A_{i}\in \mathbb {R} ^{{n_{i}}\times n},\ b_{i}\in \mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^{p\times n}}$, and ${\displaystyle g\in \mathbb {R} ^{p}}$. ${\displaystyle x\in \mathbb {R} ^{n}}$ is the optimization variable. ${\displaystyle \lVert x\rVert _{2}}$ is the Euclidean norm and ${\displaystyle ^{T}}$ indicates transpose.^[1] The "second-order cone" in SOCP arises from the constraints, which are equivalent to requiring the affine function ${\displaystyle (Ax+b,c^{T}x+d)}$ to lie in the second-order cone in ${\displaystyle \mathbb {R} ^{n_{i}+1}}$.^[1]

SOCPs can be solved by interior point methods^[2] and in general, can be solved more efficiently than semidefinite programming (SDP) problems.^[3] Some engineering applications of SOCP include filter design, antenna array weight design, truss design, and grasping force optimization in robotics.^[4] Applications in quantitative finance include portfolio optimization; some market impact constraints, because they are not linear, cannot be solved by quadratic programming but can be formulated as SOCP problems.^[5][6][7]