Second-order cone programming

A second-order cone program (SOCP) is a convex optimization problem of the form

minimize [math]\displaystyle{ \ f^T x \ }[/math]

subject to

[math]\displaystyle{ \lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m }[/math]

[math]\displaystyle{ Fx = g \ }[/math]

where the problem parameters are [math]\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} }[/math], and [math]\displaystyle{ g \in \mathbb{R}^p }[/math]. [math]\displaystyle{ x\in\mathbb{R}^n }[/math] is the optimization variable. [math]\displaystyle{ \lVert x \rVert_2 }[/math] is the Euclidean norm and [math]\displaystyle{ ^T }[/math] indicates transpose.^[1] The "second-order cone" in SOCP arises from the constraints, which are equivalent to requiring the affine function [math]\displaystyle{ (A x + b, c^T x + d) }[/math] to lie in the second-order cone in [math]\displaystyle{ \mathbb{R}^{n_i + 1} }[/math].^[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]

Second-order cone

The standard or unit second-order cone of dimension [math]\displaystyle{ n+1 }[/math] is defined as

[math]\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\} }[/math].

The second-order cone is also known by quadratic cone, ice-cream cone, or Lorentz cone. The second-order cone in [math]\displaystyle{ \mathbb{R}^3 }[/math] is [math]\displaystyle{ \left\{(x,y,z) \Big| \sqrt{x^2 + y^2} \leq z \right\} }[/math].

The set of points satisfying a second-order cone constraint is the inverse image of the unit second-order cone under an affine mapping:

[math]\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} }[/math]

and hence is convex.

The second-order cone can be embedded in the cone of the positive semidefinite matrices since

[math]\displaystyle{ ||x||\leq t \Leftrightarrow \begin{bmatrix} tI & x \\ x^T & t \end{bmatrix} \succcurlyeq 0, }[/math]

i.e., a second-order cone constraint is equivalent to a linear matrix inequality (Here [math]\displaystyle{ M\succcurlyeq 0 }[/math] means [math]\displaystyle{ M }[/math] is semidefinite matrix). Similarly, we also have,

[math]\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 }[/math].

Relation with other optimization problems

A hierarchy of convex optimization problems. (LP: linear program, QP: quadratic program, SOCP second-order cone program, SDP: semidefinite program, CP: cone program.)

When [math]\displaystyle{ A_i = 0 }[/math] for [math]\displaystyle{ i = 1,\dots,m }[/math], the SOCP reduces to a linear program. When [math]\displaystyle{ c_i = 0 }[/math] for [math]\displaystyle{ i = 1,\dots,m }[/math], 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] In fact, while any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,^[8] it is known that there exist convex semialgebraic sets that are not representable by SDPs, that is, there exist convex semialgebraic sets that can not be written as a feasible region of a SDP.^[9]

Examples

Quadratic constraint

Consider a convex quadratic constraint of the form

[math]\displaystyle{ x^T A x + b^T x + c \leq 0. }[/math]

This is equivalent to the SOCP constraint

[math]\displaystyle{ \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}} }[/math]

Stochastic linear programming

Consider a stochastic linear program in inequality form

minimize [math]\displaystyle{ \ c^T x \ }[/math]

subject to

[math]\displaystyle{ \mathbb{P}(a_i^Tx \leq b_i) \geq p, \quad i = 1,\dots,m }[/math]

where the parameters [math]\displaystyle{ a_i \ }[/math] are independent Gaussian random vectors with mean [math]\displaystyle{ \bar{a}_i }[/math] and covariance [math]\displaystyle{ \Sigma_i \ }[/math] and [math]\displaystyle{ p\geq0.5 }[/math]. This problem can be expressed as the SOCP

minimize [math]\displaystyle{ \ c^T x \ }[/math]

subject to

[math]\displaystyle{ \bar{a}_i^T x + \Phi^{-1}(p) \lVert \Sigma_i^{1/2} x \rVert_2 \leq b_i , \quad i = 1,\dots,m }[/math]

where [math]\displaystyle{ \Phi^{-1}(\cdot) \ }[/math] is the inverse normal cumulative distribution function.^[1]

Stochastic second-order cone programming

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.

Solvers and scripting (programming) languages

References

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Second-order cone programming. Read more