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

Abstrakte Definition

Gegeben sei ein reeller Vektorraum $V_{1}$ versehen mit einem Skalarprodukt $\langle {\cdot },{\cdot }\rangle _{1}$ und einem abgeschlossenen, spitzen und konvexen Kegel $K$ mit nichtleerem Inneren. Des Weiteren seien $B,C\in V_{1}$ und ${\mathcal {L}}$ ein linearer Unterraum von $V_{1}$. Dann heißt das Optimierungsproblem

${\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&X\in {\mathcal {K}}\\&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.

Konvexe Definition

Analog zu den Linearen Programmen kann man konische Programme auch in einer Standardform und einer Ungleichungsform angeben. Dazu betrachtet man die von dem Kegel induzierte verallgemeinerte Ungleichung $\preccurlyeq _{K}$ und einen weiteren Vektorraum $V_{2}$ mit einem Skalarprodukt $\langle {\cdot },{\cdot }\rangle _{2}$

Standardform

Ein konisches Programm in Standardform (oder Normalform) lässt sich nun wie folgt definieren: $X\in {\mathcal {K}}$ lässt sich auch als $X\succcurlyeq _{K}0$ schreiben. Betrachtet man eine lineare Funktion $L:V_{1}\mapsto V_{2}$, so lässt sich der linearen Unterraum ${\mathcal {L}}$ durch die diese Funktion beschreiben. Somit lässt sich auch folgende Definition eines konischen Programmes geben:

${\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-X\preccurlyeq _{K}0_{V_{1}}\\&L(X)-d=0_{V_{2}}\end{aligned}}$.

Hierbei ist $X,C\in V_{1}$ und $d\in V_{2}$.

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

Ungleichungsform

Alternativ kann man den Linearen Unterraum ${\mathcal {L}}$ auch als Bild einer linearen Funktion $L^{*}:V_{2}\mapsto V_{1}$ auffassen. Dies führt dann zu dem Problem

${\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(x)-D\preccurlyeq _{K}0_{V_{1}}\end{aligned}}$,

einem konischen Problem in Ungleichungsform. Hierbei ist $x,c\in V_{2}$ und $D\in V_{1}$.

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.

Dualität

Betrachtet man das Problem

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

als primales Problem, so ist heißt das Problem

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

das duale konische Problem. 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)