Second Order Conic Programming

If the objective function or constraint condition contains nonlinear function, this kind of programming problem is called nonlinear programming problem. Second order conic programming (SOCP) is a common nonlinear programming problem, which has a wide range of application fields and practical significance. It researchs on problems include design, combinatorial optimization, finance, game theory, economics and many other fields.

Cone

For a vector space V and its subset C, if the product ax of any point X and any positive number a in subset C still belongs to subset C, then C is called a cone. (by definition, a cone is always unbounded.)

Convex cone

if any two points x and y in a cone C , for any two positive numbers a and b in,it has , , then the cone is a convex cone.

Conic optimization is a generalization of linear optimization, allowing constraints of the type

$x^t \in K^t$

where is a subset of the problem variables and is a convex cone.

A conic quadratic optimization is a problem of the following form:

$MAX(min)z=\sum_{j=1}^{n}c_{j}x_{j}$

subject to the constraints

$\begin{array}{c} &s.t.\quad\begin{cases}l ^{c} \leq \sum\limits_{j=1}^n a_{ij}x_j \leq u ^{c} & (i=1,2,3,\cdots, m) \\ l ^{x} \leq x_j \leq u ^{x} \\ a\in \kappa \end{cases} \end{array}$

• and — the lower and upper bounds on constraints,
• and — the lower and upper bounds on variables.

where the domain restriction, , implies that all variables are partitioned into convex cones

There are two standard forms of second-order cones:

Quadratic cone

$Q ^{n} = \left \{ \sum_{j=1}^{n-1} x_j ^{2} \leq x_0, x \in \mathbb{R} ^{n} \right \}$

Rotated quadratic cone

$Q_r ^{n} = \left \{ \sum_{j=2}^{n-1} x_j ^{2} \leq 2 x_0 x_1, x \in \mathbb{R} ^{n} \right \}$