SOCP

A SOCP (or Second Order Cone Program ) is a problem in mathematical optimization in which the solution to the problem is not only subject to linear restrictions, but should also lie in a certain cone . This cone is called the second-order cone in English, from which the name of the program is derived.

definition

Given is the one provided with the standard scalar product and the second-order cone (also called Lorentz cone ) which defines the generalized inequality . Then the optimization problem is called ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \langle {\cdot },{\cdot }\rangle }$ ${\displaystyle S:=\{x\in \mathbb {R} ^{n+1}\,|\,\Vert (x_{1},\dots ,x_{n})\Vert _{2}\leq x_{n+1}\}}$ ${\displaystyle \preccurlyeq _{S}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle &\\{\text{unter den Nebenbedingungen }}&(A_{i}x+b_{i},c_{i}^{T}x+d_{i})\succcurlyeq _{S}0&i=1,\dots ,m\\&Fx=g&\end{aligned}}}$

There is and as well ${\displaystyle A_{i}\in \mathbb {R} ^{n\times n}}$ ${\displaystyle b_{i},c_{i},x\in \mathbb {R} ^{n}}$ ${\displaystyle d_{i}\in \mathbb {R} }$

Alternatively, the inequality restriction can also be formulated as. ${\displaystyle \Vert A_{i}x+b_{i}\Vert _{2}\leq c_{i}^{T}x+d_{i}}$

Classification and special cases

A SOCP is a conical program , as the above formulation shows using the cone. So it is always a convex optimization problem .

If all , a SOCP can be formulated as a special quadratic program with quadratic constraints . To do this, one takes advantage of the fact that ${\displaystyle c_{i}=0}$

${\displaystyle (x,t)\succcurlyeq _{S}0\iff {\begin{bmatrix}x\\t\end{bmatrix}}^{T}{\begin{bmatrix}E_{n}&0\\0&-1\end{bmatrix}}{\begin{bmatrix}x\\t\end{bmatrix}}\leq 0\,{\text{ und }}\,-t\leq 0}$

is. Here is the n-dimensional identity matrix . In this case, every cone restriction can be replaced by a quadratic and a linear restriction. ${\displaystyle E_{n}}$

If all are equal to zero, the inequality restrictions can be reformulated as . If one now combines the left side of the inequality for all into a vector and the right line into a matrix that consists of the vectors line by line , then the SOCP can be formulated as a linear optimization problem. ${\displaystyle A_{i}}$ ${\displaystyle d_{i}-\Vert b_{i}\Vert _{2}\geq -c_{i}^{T}x}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$

literature

• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3 . ( online )