SOCP

Problem in der mathematischen Optimierung

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.

Definition

Bearbeiten

Gegeben sei der   versehen mit dem Standardskalarprodukt   und der Second-Order-Kegel (auch Lorentz-Kegel genannt)   der die verallgemeinerte Ungleichung   definiert. Dann heißt das Optimierungsproblem

 

Dabei ist   und   sowie  

Alternativ lässt sich die Ungleichungsrestriktion auch als   formulieren.

Klassifikation und Spezialfälle

Bearbeiten

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

Sind alle  , so lässt sich ein SOCP als ein spezielles Quadratisches Programm mit quadratischen Nebenbedingungen formulieren. Dazu nutzt man aus, dass

 

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

Sind alle   gleich Null, so lassen sich die Ungleichungsrestriktionen umformulieren in  . Fasst man nun die linke Seite der Ungleichung für alle   zu einem Vektor zusammen und die rechte Zeile zu einer Matrix, die zeilenweise aus den Vektoren   besteht, so lässt sich das SOCP als Lineares Optimierungsproblem formulieren.

Literatur

Bearbeiten