Second-order cone programming

The standard or unit second-order cone of dimension n+1 is defined as :\mathcal{C}_{n+1}=\left\{ \begin{bmatrix} x \\ t \end{bmatrix} \Bigg| x \in \mathbb{R}^n, t\in \mathbb{R}, \|x\|_2\leq t \right\}. The second-order cone is also known by the names quadratic cone, ice-cream cone, or Lorentz cone. For example, the standard second-order cone in \mathbb{R}^3 is :\left\{(x,y,z) \Big| \sqrt{x^2 + y^2} \leq z \right\}. The set of points satisfying a second-order cone constraint is the inverse image of the unit second-order cone under an affine mapping: :\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i \Leftrightarrow \begin{bmatrix} A_i \\ c_i^T \end{bmatrix} x + \begin{bmatrix} b_i \\ d_i \end{bmatrix} \in \mathcal{C}_{n_i+1} and hence is convex. The second-order cone can be embedded in the cone of the positive semidefinite matrices since :||x||\leq t \Leftrightarrow \begin{bmatrix} tI & x \\ x^T & t \end{bmatrix} \succcurlyeq 0, i.e., a second-order cone constraint is equivalent to a linear matrix inequality. The nomenclature here can be confusing; here M\succcurlyeq 0 means M is a semidefinite matrix: that is to say :x^T M x \geq 0 \text{ for all } x \in \mathbb{R}^n which is not a linear inequality in the conventional sense. Similarly, we also have, :\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i \Leftrightarrow \begin{bmatrix} (c_i^T x+d_i)I & A_i x+b_i \\ (A_i x + b_i)^T & c_i^T x + d_i \end{bmatrix} \succcurlyeq 0. == Relation with other optimization problems ==

When A_i = 0 for i = 1,\dots,m, the SOCP reduces to a linear program. When c_i = 0 for i = 1,\dots,m, the SOCP is equivalent to a convex quadratically constrained linear program. Convex quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint. Any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP. However, it is known that there exist convex semialgebraic sets of higher dimension that are not representable by SDPs; that is, there exist convex semialgebraic sets that can not be written as the feasible region of a SDP (nor, a fortiori, as the feasible region of a SOCP). == Examples ==

Quadratic constraint Consider a convex quadratic constraint of the form : x^T A x + b^T x + c \leq 0. This is equivalent to the SOCP constraint : \lVert A^{1/2} x + \frac{1}{2}A^{-1/2}b \rVert \leq \left(\frac{1}{4}b^T A^{-1} b - c \right)^{\frac{1}{2}} Stochastic linear programming Consider a stochastic linear program in inequality form :minimize \ c^T x \ :subject to ::\mathbb{P}(a_i^Tx \leq b_i) \geq p, \quad i = 1,\dots,m where the parameters a_i \ are independent Gaussian random vectors with mean \bar{a}_i and covariance \Sigma_i \ and p\geq0.5. This problem can be expressed as the SOCP :minimize \ c^T x \ :subject to :: \bar{a}_i^T x + \Phi^{-1}(p) \lVert \Sigma_i^{1/2} x \rVert_2 \leq b_i , \quad i = 1,\dots,m where \Phi^{-1}(\cdot) \ is the inverse normal cumulative distribution function. Other examples Other modeling examples are available at the MOSEK modeling cookbook. ==Solvers and scripting (programming) languages==