Second order cone programming (SOCP) problems are a type of convex optimization problems. The general form of the problem is
\[\begin{array}{ll}
\mbox{minimize} & \ f^T x \\
\mbox{subject to} & \lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m \\
& Fx = g
\end{array} \]
where \(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 \(g \in \mathbb{R}^p\). The inequalities, \(\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i\) are the second order cone constraints.
Special cases
- When \(A_i = 0\) for \(i = 1,\dots,m\), the SOCP reduces to a linear programming problem.
- When \(c_i = 0\) for \(i = 1,\dots,m\), the SOCP is equivalent to a convex quadratically constrained quadratic programming problem.
Note that semidefinite programming subsumes second order cone programming since the SOCP constraints can be written as linear matrix inequalities.
References
- Alizadeh, F. and D. Goldfarb. 2003. Second-order cone programming. Mathematical Programming 95, 3 – 51.
- Boyd, S. and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press.