SOCP

Ein SOCP (oder Second Order Cone Program) i​st ein Problem i​n der mathematischen Optimierung, b​ei dem d​ie Lösung d​es Problems n​icht nur linearen Restriktionen unterliegt, sondern a​uch noch i​n einem bestimmten Kegel liegen soll. Dieser Kegel w​ird im Englischen d​er second-order c​one genannt, woraus s​ich der Name d​es Programms herleitet.

Definition

Gegeben sei der ${\displaystyle \mathbb {R} ^{n}}$ versehen mit dem Standardskalarprodukt ${\displaystyle \langle {\cdot },{\cdot }\rangle }$ und der Second-Order-Kegel (auch Lorentz-Kegel genannt) ${\displaystyle S:=\{x\in \mathbb {R} ^{n+1}\,|\,\Vert (x_{1},\dots ,x_{n})\Vert _{2}\leq x_{n+1}\}}$ der die verallgemeinerte Ungleichung ${\displaystyle \preccurlyeq _{S}}$ definiert. Dann heißt das Optimierungsproblem

${\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}}}$

Dabei ist ${\displaystyle A_{i}\in \mathbb {R} ^{n\times n}}$ und ${\displaystyle b_{i},c_{i},x\in \mathbb {R} ^{n}}$ sowie ${\displaystyle d_{i}\in \mathbb {R} }$

Alternativ lässt sich die Ungleichungsrestriktion auch als ${\displaystyle \Vert A_{i}x+b_{i}\Vert _{2}\leq c_{i}^{T}x+d_{i}}$ formulieren.

Klassifikation und Spezialfälle

Ein SOCP i​st ein Konisches Programm, w​ie die o​bige Formulierung mittels d​es Kegels zeigt. Damit i​st es a​uch immer e​in konvexes Optimierungsproblem.

Sind alle ${\displaystyle c_{i}=0}$, so lässt sich ein SOCP als ein spezielles Quadratisches Programm mit quadratischen Nebenbedingungen formulieren. Dazu nutzt man aus, dass

${\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}$

ist. Hierbei ist ${\displaystyle E_{n}}$ die n-dimensionale Einheitsmatrix. Jede Kegeleinschränkung lässt sich in diesem Fall also durch eine quadratische und eine lineare Restriktion ersetzen.

Sind alle ${\displaystyle A_{i}}$ gleich Null, so lassen sich die Ungleichungsrestriktionen umformulieren in ${\displaystyle d_{i}-\Vert b_{i}\Vert _{2}\geq -c_{i}^{T}x}$. Fasst man nun die linke Seite der Ungleichung für alle ${\displaystyle i}$ zu einem Vektor zusammen und die rechte Zeile zu einer Matrix, die zeilenweise aus den Vektoren ${\displaystyle c_{i}}$ besteht, so lässt sich das SOCP als Lineares Optimierungsproblem formulieren.

Literatur

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