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.

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

Minimiere  s ( X ) = ⟨ C , X ⟩ 1 unter den Nebenbedingungen  X ∈ K X ∈ L + B {\displaystyle {\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 Element eines Vektorraumes, das sowohl in einem Kegel als auch in einem affinen Unterraum liegt und minimal bezüglich des Skalarproduktes ist.

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 ≼ K {\displaystyle \preccurlyeq _{K}} und einen weiteren Vektorraum V 2 {\displaystyle V_{2}} mit einem Skalarprodukt ⟨ ⋅ , ⋅ ⟩ 2 {\displaystyle \langle {\cdot },{\cdot }\rangle _{2}}

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

Minimiere  s ( X ) = ⟨ C , X ⟩ 1 unter den Nebenbedingungen  − X ≼ K 0 V 1 L ( X ) − b = 0 V 2 {\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-X\preccurlyeq _{K}0_{V_{1}}\\&L(X)-b=0_{V_{2}}\end{aligned}}} .

Hierbei ist X , C ∈ V 1 {\displaystyle X,C\in V_{1}} und b ∈ V 2 {\displaystyle b\in V_{2}} .

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

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

Minimiere  s ( x ) = ⟨ c , x ⟩ 2 unter den Nebenbedingungen  L ∗ ( x ) − B ≼ K 0 V 1 {\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(x)-B\preccurlyeq _{K}0_{V_{1}}\end{aligned}}} ,

einem konischen Problem in Ungleichungsform. Hierbei ist x , c ∈ V 2 {\displaystyle x,c\in V_{2}} und B ∈ V 1 {\displaystyle B\in V_{1}} .

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.

• Jedes lineare Optimierungsproblem ist ein konisches Optimierungsproblem. Dazu wählt man als Vektorraum V 1 {\displaystyle V_{1}} den R n {\displaystyle \mathbb {R} ^{n}} und als Kegel K := { x ∈ R n | ∀ i : x i ≥ 0 } {\displaystyle K:=\{x\in \mathbb {R} ^{n}\,|\,\forall i:x_{i}\geq 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 A x = b {\displaystyle Ax=b} .
• Semidefinite Programme sind konische Programme auf dem Vektorraum der symmetrischen Matrizen S n {\displaystyle S^{n}} versehen mit dem Frobenius-Skalarprodukt. Der Kegel ist die Menge der positiv semidefiniten Matrizen S + n {\displaystyle 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.

Betrachtet man das Problem

Minimiere  s ( X ) = ⟨ C , X ⟩ 1 unter den Nebenbedingungen  X ≽ K 0 X ∈ L + B {\displaystyle {\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

Minimiere  s ( Y ) = ⟨ B , Y ⟩ 1 unter den Nebenbedingungen  Y ≽ K D 0 Y ∈ L ⊥ + C {\displaystyle {\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 {\displaystyle K^{D}} der duale Kegel von K {\displaystyle K} und L ⊥ {\displaystyle {\mathcal {L}}^{\perp }} der Orthogonalraum von L {\displaystyle {\mathcal {L}}} . Insbesondere ist das duale Programm des dualen Programms wieder das primale Programm.

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

⟨ C , X ⟩ 1 + ⟨ B , Y ⟩ 1 ≥ ⟨ B , C ⟩ 1 {\displaystyle \langle {C},{X}\rangle _{1}+\langle {B},{Y}\rangle _{1}\geq \langle {B},{C}\rangle _{1}}

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

p ∗ + ⟨ B , Y ∗ ⟩ 1 = ⟨ B , C ⟩ 1 {\displaystyle p^{*}+\langle {B},{Y^{*}}\rangle _{1}=\langle {B},{C}\rangle _{1}} .

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

⟨ C , X ∗ ⟩ 1 + ⟨ B , Y ∗ ⟩ 1 = ⟨ B , C ⟩ 1 {\displaystyle \langle {C},{X^{*}}\rangle _{1}+\langle {B},{Y^{*}}\rangle _{1}=\langle {B},{C}\rangle _{1}} .

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

Minimiere  s ( X ) = ⟨ C , X ⟩ 1 unter den Nebenbedingungen  − X ≼ K 0 V 1 L ( X ) − b = 0 V 2 {\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-X\preccurlyeq _{K}0_{V_{1}}\\&L(X)-b=0_{V_{2}}\end{aligned}}} ,

so lautet die Lagrange-Funktion

L ( X , Λ , μ ) = ⟨ C , X ⟩ 1 + ⟨ − X , Λ ⟩ 1 + ⟨ − L ( X ) + b , μ ⟩ 2 {\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{1}+\langle {-X},{\Lambda }\rangle _{1}+\langle {-L(X)+b},{\mu }\rangle _{2}} .

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

L ( X , Λ , μ ) = ⟨ C , X ⟩ 1 − ⟨ X , Λ ⟩ 1 + ⟨ b , μ ⟩ 2 − ⟨ X , L ∗ ( μ ) ⟩ 1 {\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{1}-\langle {X},{\Lambda }\rangle _{1}+\langle {b},{\mu }\rangle _{2}-\langle {X},{L^{*}(\mu )}\rangle _{1}} .

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

q ( Λ , μ ) = { ⟨ b , μ ⟩ 2  falls  C − Λ − L ∗ ( μ ) = 0 − ∞  sonst  {\displaystyle q(\Lambda ,\mu )={\begin{cases}\langle {b},{\mu }\rangle _{2}&{\text{ falls }}C-\Lambda -L^{*}(\mu )=0\\-\infty &{\text{ sonst }}\end{cases}}}

Schreibt man diese Fallunterscheidung als Nebenbedingung in das duale Problem und fasst man Λ {\displaystyle \Lambda } als Schlupfvariable mit − Λ ≼ K 0 V 1 {\displaystyle -\Lambda \preccurlyeq _{K}0_{V_{1}}} auf, so lautet das duale Problem

maximiere  s ( μ ) = ⟨ b , μ ⟩ 2 unter den Nebenbedingungen  L ∗ ( μ ) − C ≼ K D 0 V 1 {\displaystyle {\begin{aligned}{\text{maximiere }}&s(\mu )=\langle {b},{\mu }\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(\mu )-C\preccurlyeq _{K^{D}}0_{V_{1}}\end{aligned}}} ,

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

Minimiere  s ( x ) = ⟨ c , x ⟩ 2 unter den Nebenbedingungen  L ∗ ( x ) − B ≼ K 0 V 1 {\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(x)-B\preccurlyeq _{K}0_{V_{1}}\end{aligned}}}

lautet die Lagrange-Funktion

L ( x , Λ ) = ⟨ c , x ⟩ 2 + ⟨ L ( Λ ) , x ⟩ 2 − ⟨ Λ , B ⟩ 1 {\displaystyle L(x,\Lambda )=\langle {c},{x}\rangle _{2}+\langle {L(\Lambda )},{x}\rangle _{2}-\langle {\Lambda },{B}\rangle _{1}}

und mit einem analogen Vorgehen zu oben ist das duale Problem

Maximiere  s ( Λ ) = − ⟨ Λ , B ⟩ 1 unter den Nebenbedingungen  − Λ ≼ K D 0 V 1 L ( Λ ) + c = 0 V 2 {\displaystyle {\begin{aligned}{\text{Maximiere }}&s(\Lambda )=-\langle {\Lambda },{B}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-\Lambda \preccurlyeq _{K^{D}}0_{V_{1}}\\&L(\Lambda )+c=0_{V_{2}}\end{aligned}}} ,

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.

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

⟨ B , Y ⟩ 1 = ⟨ B , L ∗ ( y ) + C ⟩ 1 = ⟨ b , y ⟩ 2 + ⟨ B , C ⟩ 1 {\displaystyle \langle {B},{Y}\rangle _{1}=\langle {B},{L^{*}(y)+C}\rangle _{1}=\langle {b},{y}\rangle _{2}+\langle {B},{C}\rangle _{1}} ,

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

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

( L + B ) ∩ Int ⁡ ( K ) ≠ ∅ {\displaystyle ({\mathcal {L}}+B)\cap \operatorname {Int} ({\mathcal {K}})\neq \emptyset } .

Hierbei ist Int {\displaystyle \operatorname {Int} } das innere einer Menge. Es muss also mindestens einen Punkt geben, der sowohl im Inneren des Kegels als auch in dem affinen Raum L + B {\displaystyle {\mathcal {L}}+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 ≺ K {\displaystyle \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.

• 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)