A second-order cone program (SOCP) is a convex optimization problem of the form
where the problem parameters are f ∈ R n , A i ∈ R n i × n , b i ∈ R n i , c i ∈ R n , d i ∈ R , F ∈ R p × n {\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 g ∈ R p {\displaystyle g\in \mathbb {R} ^{p}} . x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} is the optimization variable. ‖ x ‖ 2 {\displaystyle \lVert x\rVert _{2}} is the Euclidean norm and T {\displaystyle ^{T}} indicates transpose.[1] The "second-order cone" in SOCP arises from the constraints, which are equivalent to requiring the affine function ( A x + b , c T x + d ) {\displaystyle (Ax+b,c^{T}x+d)} to lie in the second-order cone in R n i + 1 {\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]
The standard or unit second-order cone of dimension n + 1 {\displaystyle n+1} is defined as
C n + 1 = { [ x t ] | x ∈ R n , t ∈ R , ‖ x ‖ 2 ≤ t } {\displaystyle {\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 quadratic cone or ice-cream cone or Lorentz cone. The standard second-order cone in R 3 {\displaystyle \mathbb {R} ^{3}} is { ( x , y , z ) | x 2 + y 2 ≤ z } {\displaystyle \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:
‖ A i x + b i ‖ 2 ≤ c i T x + d i ⇔ [ A i c i T ] x + [ b i d i ] ∈ C n i + 1 {\displaystyle \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 | | ≤ t ⇔ [ t I x x T t ] ≽ 0 , {\displaystyle ||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 (Here M ≽ 0 {\displaystyle M\succcurlyeq 0} means M {\displaystyle M} is semidefinite matrix). Similarly, we also have,
‖ A i x + b i ‖ 2 ≤ c i T x + d i ⇔ [ ( c i T x + d i ) I A i x + b i ( A i x + b i ) T c i T x + d i ] ≽ 0 {\displaystyle \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} .
When A i = 0 {\displaystyle A_{i}=0} for i = 1 , … , m {\displaystyle i=1,\dots ,m} , the SOCP reduces to a linear program. When c i = 0 {\displaystyle c_{i}=0} for i = 1 , … , m {\displaystyle 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.[4] Semidefinite programming subsumes SOCPs as the SOCP constraints can be written as linear matrix inequalities (LMI) and can be reformulated as an instance of semidefinite program.[4] The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.[3]
Any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,[8]. 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).[9]
Consider a convex quadratic constraint of the form
This is equivalent to the SOCP constraint
Consider a stochastic linear program in inequality form
where the parameters a i {\displaystyle a_{i}\ } are independent Gaussian random vectors with mean a ¯ i {\displaystyle {\bar {a}}_{i}} and covariance Σ i {\displaystyle \Sigma _{i}\ } and p ≥ 0.5 {\displaystyle p\geq 0.5} . This problem can be expressed as the SOCP
where Φ − 1 ( ⋅ ) {\displaystyle \Phi ^{-1}(\cdot )\ } is the inverse normal cumulative distribution function.[1]
We refer to second-order cone programs as deterministic second-order cone programs since data defining them are deterministic. Stochastic second-order cone programs are a class of optimization problems that are defined to handle uncertainty in data defining deterministic second-order cone programs.[10]
Other modeling examples are available at the MOSEK modeling cookbook.[11]
coneprog