Second-Order Cone Programming

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

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.
  • Optimization Online Linear, Cone, and Semidefinite Programming area