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 $⟨\cdot ,\cdot {⟩}_1$ und einem abgeschlossenen, spitzen und konvexen Kegel $K$ mit nichtleerem Inneren. Des Weiteren seien $B,C\in V_1$ und $ℒ$ ein linearer Unterraum von $V_1$. Dann heißt das Optimierungsproblem

$\begin{array}{cc}\text{Minimiere }& s(X)=⟨C,X{⟩}_1\\ \text{unter den Nebenbedingungen }& X\in 𝒦\\ & X\in ℒ+B\end{array}$

ein konisches Programm oder konisches Optimierungsproblem. Gesucht wird also ein Element 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 $⟨\cdot ,\cdot {⟩}_2$

Standardform

Ein konisches Programm in Standardform (oder Normalform) lässt sich nun wie folgt definieren: $X\in 𝒦$ 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 lineare Unterraum $ℒ$ durch diese Funktion beschreiben. Somit lässt sich auch folgende Definition eines konischen Programmes geben:

$\begin{array}{cc}\text{Minimiere }& s(X)=⟨C,X{⟩}_1\\ \text{unter den Nebenbedingungen }& -X{\preccurlyeq }_K{0}_{V_1}\\ & L(X)-b=0_{V_2}\end{array}$.

Hierbei ist $X,C\in V_1$ und $b\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 $ℒ$ auch als Bild einer linearen Funktion $L^{*}:V_2\mapsto V_1$ auffassen. Dies führt dann zu dem Problem

$\begin{array}{cc}\text{Minimiere }& s(x)=⟨c,x{⟩}_2\\ \text{unter den Nebenbedingungen }& L^{*}(x)-B{\preccurlyeq }_K{0}_{V_1}\end{array}$,

einem konischen Problem in Ungleichungsform. Hierbei ist $x,c\in V_2$ und $B\in V_1$.

Mischformen

Allgemeiner werden Optimierungsprobleme mit linearer Zielfunktion, die eine Linear-affine Gleichungsnebenbedingung sowie eine Linear-affine Ungleichungsnebenbedingung mit verallgemeinerter Ungleichung enthalten als konische Optimierungsprobleme bezeichnet. Dies entspricht einer Mischung aus Standardform/Normalform und Ungleichungsform.

Beispiele

• Jedes lineare Optimierungsproblem ist ein konisches Optimierungsproblem. Dazu wählt man als Vektorraum $V_1$ den ${ℝ}^n$ und als Kegel $K:=\{x\in {ℝ}^n|\mathrm{\forall }i:x_i\ge 0\}$, den sogenannten positiven Orthanten. 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

Dualität konischer Programme

Betrachtet man das Problem

$\begin{array}{cc}\text{Minimiere }& s(X)=⟨C,X{⟩}_1\\ \text{unter den Nebenbedingungen }& X{\succcurlyeq }_{K}0\\ & X\in ℒ+B\end{array}$

als primales Problem, so ist heißt das Problem

$\begin{array}{cc}\text{Minimiere }& s(Y)=⟨B,Y{⟩}_1\\ \text{unter den Nebenbedingungen }& Y{\succcurlyeq }_{K^D}0\\ & Y\in {ℒ}^{\perp }+C\end{array}$

das duale konische Problem. Hierbei ist $K^D$ der duale Kegel von $K$ und ${ℒ}^{\perp }$ der Orthogonalraum von $ℒ$. Insbesondere ist das duale Programm des dualen Programms wieder das primale Programm.

Es gilt dann für jeden zulässigen Punkt $X$ des primalen Problems und jeden zulässigen Punkt $Y$ des dualen Problems, dass

$⟨C,X{⟩}_1+⟨B,Y{⟩}_1\ge ⟨B,C{⟩}_1$

Ist der Optimalwert $p^{*}$ des primalen Problems endlich und ist die Slater-Bedingung erfüllt (siehe unten), so besitzt das duale Problem eine Optimallösung $Y^{*}$, und es ist

$p^{*}+⟨B,Y^{*}{⟩}_1=⟨B,C{⟩}_1$.

Erfüllen sowohl das primale als auch das duale Problem die Slater-Bedingung, so existieren Optimallösungen $X^{*},Y^{*}$ mit

$⟨C,X^{*}{⟩}_1+⟨B,Y^{*}{⟩}_1=⟨B,C{⟩}_1$.

Lagrange-Dualität

Nicht mit der obigen Dualität zu verwechseln ist die Lagrange-Dualität, angewandt auf die konvexe Form eines konischen Problems. Ist ein konisches Problem in Normalform gegeben durch

$\begin{array}{cc}\text{Minimiere }& s(X)=⟨C,X{⟩}_1\\ \text{unter den Nebenbedingungen }& -X{\preccurlyeq }_K{0}_{V_1}\\ & L(X)-b=0_{V_2}\end{array}$,

so lautet die Lagrange-Funktion

$L(X,\mathrm{\Lambda },\mu )=⟨C,X{⟩}_1+⟨-X,\mathrm{\Lambda }{⟩}_1+⟨-L(X)+b,\mu {⟩}_2$.

Ist $L^{*}$ der zu $L$ Adjungierte Operator, so folgt mit der Linearität des Skalarproduktes

$L(X,\mathrm{\Lambda },\mu )=⟨C,X{⟩}_1-⟨X,\mathrm{\Lambda }{⟩}_1+⟨b,\mu {⟩}_2-⟨X,L^{*}(\mu ){⟩}_1$.

Diese Funktion ist linear in $X$, und da Lineare Funktionen genau dann unbeschränkt sind, wenn sie konstant gleich Null sind, lautet die Zielfunktion des dualen Programms

$q(\mathrm{\Lambda },\mu )=\{\begin{array}{cc}⟨b,\mu {⟩}_2& \text{ falls }C-\mathrm{\Lambda }-L^{*}(\mu )=0\\ -\mathrm{\infty }& \text{ sonst }\end{array}$

Schreibt man diese Fallunterscheidung als Nebenbedingung in das duale Problem und fasst man $\mathrm{\Lambda }$ als Schlupfvariable mit $-\mathrm{\Lambda }{\preccurlyeq }_K{0}_{V_1}$ auf, so lautet das duale Problem

$\begin{array}{cc}\text{maximiere }& s(\mu )=⟨b,\mu {⟩}_2\\ \text{unter den Nebenbedingungen }& L^{*}(\mu )-C{\preccurlyeq }_{K^D}{0}_{V_1}\end{array}$,

was ein konisches Programm in Ungleichungsform ist. Ein Minimierungsproblem erhält man, indem man das Vorzeichen der Zielfunktion umkehrt.

Für ein konisches Problem in Ungleichungsform

$\begin{array}{cc}\text{Minimiere }& s(x)=⟨c,x{⟩}_2\\ \text{unter den Nebenbedingungen }& L^{*}(x)-B{\preccurlyeq }_K{0}_{V_1}\end{array}$

lautet die Lagrange-Funktion

$L(x,\mathrm{\Lambda })=⟨c,x{⟩}_2+⟨L(\mathrm{\Lambda }),x{⟩}_2-⟨\mathrm{\Lambda },B{⟩}_1$

und mit einem analogen Vorgehen zu oben ist das duale Problem

$\begin{array}{cc}\text{Maximiere }& s(\mathrm{\Lambda })=-⟨\mathrm{\Lambda },B{⟩}_1\\ \text{unter den Nebenbedingungen }& -\mathrm{\Lambda }{\preccurlyeq }_{K^D}{0}_{V_1}\\ & L(\mathrm{\Lambda })+c=0_{V_2}\end{array}$,

was wieder ein konisches Programm in Normalform ist. Duale Probleme von konischen Problemen sind also stets wieder konische Probleme. Bildet man außerdem das duale Problem eines dualen Problems, so gelangt man wieder zum Ausgangsproblem

Gilt die Slater-Bedingung (siehe unten), so gilt starke Dualität, das heißt die Optimalwerte des primalen und des dualen Problems stimmen überein. Ein schwächeres Ergebnis ist, dass der Zielfunktionswert des dualen Problems stets kleiner als der Zielfunktionswert des primalen Problems ist. Diese Aussage ist auch als schwache Dualität bekannt.

Zusammenhang der Dualitätsbegriffe

Die beiden obigen Dualitätsbegriffe sind nicht identisch, hängen aber sehr eng zusammen. Betrachtet man zum Beispiel einen linearen Unterraum $ℒ$, der durch die Lösung der linearen Gleichung $L(Y)=0$ beschrieben wird, so wird der Orthogonalraum ${ℒ}^{\perp }$ durch den zu $L$ adjungierten Operator $L^{*}(y)$ beschrieben. Damit ist die Bedingung $Y\in {ℒ}^{\perp }+C$ äquivalent zu $Y=L^{*}(y)+C$ für $y\in V_2$. Somit ist

$⟨B,Y{⟩}_1=⟨B,L^{*}(y)+C{⟩}_1=⟨b,y{⟩}_2+⟨B,C{⟩}_1$,

wobei $L(B)=b$ ist. Nun kann man anstelle von $Y$ über $y$ optimieren, der Term $⟨B,C{⟩}_1$ kann ignoriert werden, da er den nur den Optimalwert, nicht aber den Optimalpunkt beeinflusst. Die neue Zielfunktion lautet nun also $⟨b,y{⟩}_2$. Fasst man $Y$ als Schlupfvariable mit $-Y{\preccurlyeq }_K$ auf, so ist $Y=L^{*}(y)+C$ äquivalent zu $-L^{*}(y){\preccurlyeq }_{K}C$. Somit ist das duale abstrakte Problem ein Problem in Ungleichungsform und umgekehrt.

Slater-Bedingung

Die Slater-Bedingung für konische Programme in der abstrakten Form lautet

$(ℒ+B)\cap \mathrm{Int}(𝒦)\ne \mathrm{\varnothing }$.

Hierbei ist $\mathrm{Int}$ das innere einer Menge. Es muss also mindestens einen Punkt geben, der sowohl im Inneren des Kegels als auch in dem affinen Raum $ℒ+B$ liegt.

Für konische Programme in der konvexen Form ist die Slater-Bedingung erfüllt, wenn es einen Punkt gibt, der die Gleichungsrestriktion erfüllt, und der zulässig bezüglich der von den Kegel induzierten strikten Ungleichung ${\prec }_K$ ist (dies entspricht der Forderung, dass der Punkt im Inneren des Kegels liegen soll). Solche Punkte werden auch strikt zulässige Punkte genannt.

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)