SOCP

Ein SOCP (oder Second Order Cone Program) ist ein Problem in der mathematischen Optimierung, bei dem die Lösung des Problems nicht nur linearen Restriktionen unterliegt, sondern auch noch in einem bestimmten Kegel liegen soll. Dieser Kegel wird im Englischen der second-order cone genannt, woraus sich der Name des Programms herleitet.

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

Minimiere  s ( x ) = ⟨ c , x ⟩ unter den Nebenbedingungen  ( A i x + b i , c i T x + d i ) ≽ S 0 i = 1 , … , m F x = g {\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 A i ∈ R n × n {\displaystyle A_{i}\in \mathbb {R} ^{n\times n}} und b i , c i , x ∈ R n {\displaystyle b_{i},c_{i},x\in \mathbb {R} ^{n}} sowie d i ∈ R {\displaystyle d_{i}\in \mathbb {R} }

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

Ein SOCP ist ein Konisches Programm, wie die obige Formulierung mittels des Kegels zeigt. Damit ist es auch immer ein konvexes Optimierungsproblem.

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

( x , t ) ≽ S 0 ⟺ [ x t ] T [ E n 0 0 − 1 ] [ x t ] ≤ 0  und  − t ≤ 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}

ist. Hierbei ist E n {\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 A i {\displaystyle A_{i}} gleich Null, so lassen sich die Ungleichungsrestriktionen umformulieren in d i − ‖ b i ‖ 2 ≥ − c i T x {\displaystyle d_{i}-\Vert b_{i}\Vert _{2}\geq -c_{i}^{T}x} . Fasst man nun die linke Seite der Ungleichung für alle i {\displaystyle i} zu einem Vektor zusammen und die rechte Zeile zu einer Matrix, die zeilenweise aus den Vektoren c i {\displaystyle c_{i}} besteht, so lässt sich das SOCP als Lineares Optimierungsproblem formulieren.

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