Komplementaritätsbedingung

Die Komplementaritätsbedingung, auch komplementärer Schlupf genannt (englisch complementary Slackness), ist eine Aussage der mathematischen Optimierung, die eine Verbindung zwischen den Optimalpunkten zweier Optimierungsprobleme knüpft, die zueinander dual bezüglich der Lagrange-Dualität sind. Die Komplementaritätsbedingung ist ein notwendiges Optimalitätskriterium und findet Anwendung bei Innere-Punkte-Verfahren und den Karush-Kuhn-Tucker-Bedingungen.

Aussage

Allgemeiner Fall

Problemstellung

Gegeben seien zwei Optimierungsprobleme wie in der nachfolgenden Tabelle:

Primales Problem	Duales Problem
${\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}$	${\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\geq 0&i=1,\dotsc ,p\end{aligned}}$

Dabei ist

$q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)\right)$

die duale Funktion und $f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R}$

Aussage

Die Komplementaritätsbedingung lautet nun

$\lambda _{i}^{*}g_{i}(x^{*})=0{\text{ für alle }}i=1,\dotsc ,p$

für zulässige $x^{*},\lambda ^{*}$. Eine alternative Formulierung in Vektorschreibweise mit $g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}$ und $\lambda =(\lambda _{1},\dots ,\lambda _{p})^{T}$ ist

$(\lambda ^{*})^{T}g(x^{*})=0$.

Ist der $i$-te Lagrange-Multiplikator (die $i$-te Ungleichungsrestriktion) ungleich Null, so muss die $i$-te Ungleichungsrestriktion (der $i$-te Lagrange-Multiplikator) folglich gleich Null sein:

${\begin{aligned}\lambda _{i}^{*}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}^{*}=0\end{aligned}}$.

Es muss also stets mindestens einer der beiden Faktoren null sein. Dies folgt daraus, dass $\lambda _{i}^{*}\geq 0$ und $g_{i}(x^{*})\leq 0$ gilt, da beide dual bzw. primal zulässig sind.

Gültigkeit

Gilt die starke Dualität (d. h. sind der Optimalwert des primalen und des dualen Problems gleich), wird der Optimalwert in $x^{*}$ und $(\lambda ^{*},\mu ^{*})$ angenommen und ist er endlich, so gilt die Komplementaritätsbedingung.

Alternativ findet sich auch im Rahmen der KKT-Bedingungen die Formulierung, dass wenn $x^{*}$ optimal für das primale Problem ist, $f(x^{*})$ endlich ist und gewisse Regularitätsbedingungen (auch constraint qualifications genannt) gelten, so existieren $\lambda _{i}^{*}\geq 0$, so dass für $x^{*},\lambda ^{*}$ die Komplementaritätsbedingung gilt. Die Regularitätsbedingungen garantieren die starke Dualität (meist nur im Punkt $x^{*}$) und ermöglichen damit die Ergänzung der primalen Optimallösung um die duale Optimallösung.

Für lineare Programme

Problemstellung

Handelt es sich bei den Optimierungsproblemen um lineare Programme, so nehmen das primale und das duale Problem eine besondere Form an und der komplementäre Schlupf vereinfacht sich.

Primales Problem	Duales Problem
${\begin{aligned}{\text{Minimiere }}&c^{T}x&\\{\text{unter den Nebenbedingungen }}&Ax=b\\&x\geq 0\end{aligned}}$	${\begin{aligned}{\text{Maximiere }}&b^{T}y&\\{\text{unter den Nebenbedingungen }}&A^{T}y\leq c\end{aligned}}$

Dabei ist $x,c\in \mathbb {R} ^{n}\,,\,b,y\in \mathbb {R} ^{m}$ und $A\in \mathbb {R} ^{m\times n}$.

Aussage

Bezeichne $[x]_{i}$ die i-te Komponente des Vektors $x$. Dann lautet die Komplementaritätsbedingung für zulässige $x^{*},y^{*}$

$(x^{*})^{T}(A^{T}y^{*}-c)=0{\text{ bzw. }}[x^{*}]_{i}\cdot [A^{T}y^{*}-c]_{i}=0$.

Damit folgt

${\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[A^{T}y^{*}\right]_{i}=\left[c\right]_{i}\\\left[A^{T}y^{*}-c\right]_{i}<0\implies \left[x^{*}\right]_{i}=0\end{aligned}}$.

Ist das duale Problem mit einer Schlupfvariable $s\in \mathbb {R} ^{n}$ formuliert, lauten die Nebenbedingungen also

$A^{T}y+s=c\,,\,s\geq 0,$

so lautet die Komplementaritätsbedingung

$(x^{*})^{T}s^{*}=0{\text{ bzw. }}[x^{*}]_{i}\cdot [s]_{i}=0$

und

${\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[s^{*}\right]_{i}=0\\\left[s^{*}\right]_{i}>0\implies \left[x^{*}\right]_{i}=0\end{aligned}}$.

Dies erklärt die Namensgebung als komplementärer Schlupf: Entweder die Schlupfvariable ist null oder die primale Variable ist null.

Gültigkeit

Die Formulierung der Komplementaritätsbedingung basiert auf der Tatsache, dass für lineare Programme starke Dualität gilt und der Optimalwert endlich ist, genau dann, wenn sowohl das primale als auch das duale Problem einen zulässigen Punkt besitzen.

Die Formulierung lautet also, dass falls das primale und das duale Problem zulässige Lösungen besitzen, zulässige Lösungen $x^{*},y^{*}$ (bzw. je nach Formulierung $s^{*}$) existieren, die die Komplementaritätsbedingung erfüllen. Die $x^{*},y^{*}$ sind dann Optimallösungen des primalen und dualen Problems.

Umgekehrt erfüllt jedes endliche primal-duale Optimalpaar $x^{*},y^{*}$ die Komplementaritätsbedingung.

Beispiel

Wir betrachten das primale lineare Programm

${\begin{aligned}{\text{Minimiere }}&(-1,0,0)x\\{\text{unter den Nebenbedingungen }}&(1,1,1)x=1\\&x\geq 0\end{aligned}}$

und das zugehörige duale Programm

${\begin{aligned}{\text{Maximiere }}&y_{1}\\{\text{unter den Nebenbedingungen }}&{\begin{pmatrix}1\\1\\1\end{pmatrix}}y\leq {\begin{pmatrix}-1\\0\\0\end{pmatrix}}\end{aligned}}$

Beide Probleme besitzen einen zulässigen Punkt, somit gilt starke Dualität. Der optimale duale Zielfunktionswert ist $y_{1}=-1$. Aus der starken Dualität folgert man wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c^Tx=b^Ty } , dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1=1 } ist. Der komplementäre Schlupf liefert nun

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} x_2\cdot (y_1-0)=0 \\ x_3 \cdot (y_1-0)=0 \end{align} }

und damit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_2=x_3=0 } . Somit liefert hier der komplementäre Schlupf den vollständigen primalen Optimalpunkt. Umgekehrt kann man auch bei gegebenen primalen und dualen Punkten überprüfen, ob diese Optimalpunkte sind: Wenn sie optimal sind, müssen sie den komplementären Schlupf erfüllen.

Herleitung

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^* } primal optimal und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\lambda^*, \mu^*) } dual optimal. Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i(x^*)\leq 0 } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_i^* \geq 0 } , da die Optimalpunkte zulässig sind. Somit ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda^* g_i(x^*)\leq 0 } . Wegen der starken Dualität ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} f(x^*)=q(\lambda^*, \mu^*)= \inf_{x \in X} \left( f(x)+\sum_{i=1}^p\lambda^*_ig_i(x)+\sum_{j=1}^q\mu^*_jh_j(x) \right) \\ \leq f(x^*)+\sum_{i=1}^p\underbrace{ \lambda^*_ig_i(x^*)}_{\leq 0}+\sum_{j=1}^q\underbrace{ \mu^*_jh_j(x^*)}_{=0} \leq f(x^*) \end{align} }

Die erste geschweifte Klammer folgt aus der oben gezeigten Identität, die zweite aus der Tatsache, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_j(x^*)=0} , da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^* } zulässig ist. Ist nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x^*) } endlich, so gilt in der Ungleichung Gleichheit und es folgt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{i=1}^p\lambda^*_ig_i(x^*) = 0} ,

was die Behauptung impliziert, da jeder der Summanden kleinergleich null ist.

Verallgemeinerungen

Der komplementäre Schlupf lässt sich auch allgemeiner formulieren für Abbildungen zwischen vollständigen reellen Vektorräumen, die mit Skalarprodukt versehen sind und auf denen eine verallgemeinerte Ungleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \preccurlyeq_{K}} bzw. ein Ordnungskegel definiert ist. Die Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i } bilden in den Vektorraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_i } versehen mit dem Skalarprodukt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle \cdot ; \cdot \rangle_i } ab, ebenso bilden die Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_j } in den Vektorraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_j } versehen mit dem Skalarprodukt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle \cdot ; \cdot \rangle_j } ab. Das primale und duale Problem lauten dann

Primales Problem

Duales Problem

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \text{Minimiere } & f(x) & \\ \text{unter den Nebenbedingungen } & g_i(x) \preccurlyeq_{K_i} 0 & i=1, \dotsc, p\\ & h_j(x)=0 & j=1, \dotsc, q\\ & x \in X & \end{align} }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \text{Maximiere } & q(\lambda, \mu) & \\ \text{unter den Nebenbedingungen } & \lambda_i \succcurlyeq_{K_i^*} 0 & i=1, \dotsc, p \end{align} } .

Dabei ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(\lambda, \mu)=\inf_{x \in X}\left( f(x)+ \sum_{i=1}^p \langle \lambda ; g(x) \rangle_i+ \sum_{j=1}^q \langle \mu_j ; h_j(x) \rangle_j \right) }

die duale Funktion und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K^* } der duale Kegel zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K } .

Gilt starke Dualität und sind die Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^* } sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\lambda^*, \mu^*) } optimal und ist der Zielfunktionswert endlich, so gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle\lambda^*_i ; g_i(x^*) \rangle_i = 0 \text{ für } i=1, \dots, p } .

Daraus folgt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \lambda^*_i >_{K_i^*}0 & \implies g_i(x^*)=0 \\ g_i(x^*) <_{K_i}0 & \implies \lambda_i^*=0 \end{align} }

Die Herleitung für diesen allgemeinen Fall ist größtenteils analog zur obigen Vorgehensweise unter Ausnutzung der Tatsache, dass wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \preccurlyeq_{K} 0, b \succcurlyeq_{K^*} 0 } ist, folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle a;b \rangle \leq 0 } .

Formuliert man das Problem mit Ordnungskegeln, sind also die Ungleichungsrestriktionen von der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i(x) \in -K_i } bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda \in K_i^* } , so gilt genauso wie oben

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle\lambda^*_i ; g_i(x^*) \rangle_i = 0 \text{ für } i=1, \dots, p } .

Die Aussage

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda^*_i \in \operatorname{int}(K_i^*) \implies g_i(x^*)=0 }

gilt aber nur, wenn der Kegel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_i^* } ein nichtleeres Inneres hat. Analog gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i(x^*) \in \operatorname{int}(-K_i) \implies \lambda_i^*=0 }

nur, wenn das Innere von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_i } nicht leer ist.

Literatur

• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. (online)
• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2.