Second Order Cone Programming

Back to Semidefinite Programming or Continuous Optimization

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.

Online and Software Resources

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