Konisches Programm

Ein konisches Programm ist in der mathematischen Optimierung ein bestimmtes Problem, bei dem in der Formulierung der zulässigen Punkte auch ein Kegel verwendet wird, was zu dieser Namensgebung führte. Einige Problemklassen lassen sich als konische Programme formulieren.

Definition

Gegeben sei ein Skalarprodukt $\langle {\cdot },{\cdot }\rangle$ im $\mathbb {R} ^{n}$ und ein abgeschlossener, spitzer und konvexer Kegel $K$ mit nichtleerem Inneren, der die verallgemeinerte Ungleichung $\preccurlyeq _{K}$ definiert. Dann heißt das Optimierungsproblem

${\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle \\{\text{unter den Nebenbedingungen }}&x\succcurlyeq _{K}0\\&Ax=b\end{aligned}}$

ein konisches Programm oder konisches Optimierungsproblem. Insbesondere sind alle auftretenden Funktionen entweder linear oder K-konvex, daher handelt es sich um ein allgemeineres konvexes Optimierungsproblem.

Beispiele

• Jedes Lineare Optimierungsproblem ist ein konisches Optimierungsproblem. Dazu wählt man als Kegel $K:=\{x\in \mathbb {R} ^{n}\,|\,x_{i}\geq 0\forall i\}$. Die verallgemeinerte Ungleichung ist dann das "komponentenweise größer als".
• Semidefinite Programme sind konische Programme, die den Kegel der positiv semidefiniten Matrizen verwenden.
• Die SOCPs (Second Order Cone Program) verwenden den second-order cone, der auch Lorentz-Kegel genannt wird.

Normalform und Ungleichungsform

Analog zur Linearen Optimierung nennt man die in der Definition verwendete Form die Normalform eines konischen Programms. Die Darstellung

${\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle \\{\text{unter den Nebenbedingungen }}&Fx+g\preccurlyeq _{K}0\end{aligned}}$

heißt dann die Ungleichungsform eines konischen Programms.

Literatur

• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. (online)