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 reeller Vektorraum $V$ versehen mit einem Skalarprodukt $\langle {\cdot },{\cdot }\rangle$ und ein abgeschlossener, spitzer und konvexer Kegel $K$ mit nichtleerem Inneren, der die verallgemeinerte Ungleichung $\preccurlyeq _{K}$ definiert. Des Weiteren seien $b,c\in V$ und ${\mathcal {L}}$ ein linearer Unterraum von $V$. Dann heißt das Optimierungsproblem

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

ein konisches Programm oder konisches Optimierungsproblem. Gesucht wird also ein Elemente eines Vektorraumes, das sowohl in einem Kegel als auch in einem affinen Unterraum liegt und minimal bezüglich des Skalarproduktes ist. 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 Vektorraum den $\mathbb {R} ^{n}$ und als Kegel $K:=\{x\in \mathbb {R} ^{n}\,|\,\forall i:x_{i}\geq 0\}$. Die verallgemeinerte Ungleichung ist dann das „komponentenweise größer als“. Als Skalarprodukt wählt man das Standardskalarprodukt und als affinen Unterraum die Lösungsmenge der Gleichung $Ax=b$.
• Semidefinite Programme sind konische Programme auf dem Vektorraum der symmetrischen Matrizen $S^{n}$ versehen mit dem Frobenius-Skalarprodukt. Der Kegel ist die Menge der positiv semidefiniten Matrizen $S_{+}^{n}$, der affine Raum wird auch über das Frobenius-Skalarprodukt definiert.
• 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.

Lagrange-Dualität

Betrachtet man das Problem

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

als primales Problem, so ist das Duale Problem bezüglich der Lagrange-Dualität von der Form

${\begin{aligned}{\text{Minimiere }}&s(y)=\langle {b},{y}\rangle \\{\text{unter den Nebenbedingungen }}&y\succcurlyeq _{K^{D}}0\\&y\in {\mathcal {L}}^{\perp }+c\end{aligned}}$

Hierbei ist $K^{D}$ der duale Kegel von $K$ und ${\mathcal {L}}^{\perp }$ der Orthogonalraum von ${\mathcal {L}}$.

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)