Lagrange-Dualität

Die Lagrange-Dualität ist eine wichtige Dualität in der mathematischen Optimierung, die sowohl Optimalitätskriterien mittels der Karush-Kuhn-Tucker-Bedingungen oder der Lagrange-Multiplikatoren liefert als auch äquivalente Umformulierungen von Optimierungsproblemen möglich macht. Ziel ist es das ursprüngliche (primale) Problem in ein duales Problem zu überführen.

Lagrange-Funktion, duales Problem

Gegeben sei folgendes Optimierungsproblem:

{\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}}

Dabei kann die abstrakte Restriktion $x\in X$ beispielsweise Forderungen wie $x\in \mathbb {Z} ^{n}$ (Ganzzahligkeit) oder $x\in {\mathcal {K}}$ für einen Kegel ${\mathcal {K}}$ aufnehmen. Die auftretenden Funktionen müssen weder konvex noch differenzierbar sein.

Die Funktion

L(x,\lambda ,\mu ):=f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)

heißt dann die zu dem obigen Optimierungsproblem gehörende Lagrange-Funktion. Gelegentlich werden die Funktionen $g_{i},h_{j}$ sowie die Skalare $\lambda _{i},\mu _{j}$ zu Vektoren $g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T},h(x)=(h_{1}(x),\dots ,h_{q}(x))^{T}$ und $\lambda =(\lambda _{1},\dots ,\lambda _{p})^{T},\mu =(\mu _{1},\dots ,\mu _{q})^{T}$ zusammengefasst. Die Lagrange-Funktion vereinfacht sich dann zu

L(x,\lambda ,\mu ):=f(x)+\lambda ^{T}g(x)+\mu ^{T}h(x).

$(\lambda ,\mu )$ werden duale Variablen oder Lagrange-Multiplikatoren genannt. Die Funktion

q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu )

heißt dann die duale Funktion zu dem obigen Optimierungsproblem. Das Optimierungsproblem

{\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )\\{\text{unter den Nebenbedingungen }}&\lambda \geq 0\end{aligned}}

heißt das duale Problem des obigen Optimierungsproblems. Dabei ist $\lambda \geq 0$ komponentenweise zu verstehen. Das ursprüngliche Problem wird dann auch als primales Problem bezeichnet. Im Allgemeinen muss die duale Funktion nicht reellwertig sein, sie kann durchaus auch den Wert $-\infty$ annehmen. Man definiert dann

\operatorname {dom} _{q}:=\{(\lambda ,\mu )\in \mathbb {R} ^{p}\times \mathbb {R} ^{q}\,|\,\lambda \geq 0,q(\lambda ,\mu )>-\infty \}

als den wesentlichen Definitionsbereich der dualen Funktion. Die dualen Variablen $(\lambda ,\mu )$ werden dual zulässig genannt, wenn sie zulässig bezüglich des dualen Problems sind, das heißt, wenn $\lambda \geq 0$ gilt.

Beispiel

Betrachtet man als Beispiel ein lineares Optimierungsproblem in Ungleichungsform:

{\begin{aligned}{\text{Minimiere }}&f(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&Ax-b\leq 0\end{aligned}}

Dabei ist $x,c\in \mathbb {R} ^{n}\,,b\in \mathbb {R} ^{m}$ und $A\in \mathbb {R} ^{m\times n}$ . Der Vollständigkeit halber setzt man $X=\mathbb {R} ^{n}$ , was in diesem Fall keine Einschränkung bedeutet. Die Lagrange-Funktion ist dann

L(x,\lambda )=c^{T}x+\lambda ^{T}(Ax-b)=(c^{T}+\lambda ^{T}A)x-\lambda ^{T}b

.

Ist $c^{T}=-\lambda ^{T}A$ , so ist $L(x,\lambda )$ unabhängig von $x$ und damit ist $\inf _{x\in X}L(x,\lambda )=-\lambda ^{T}b$ . Ist aber $c^{T}\neq -\lambda ^{T}A$ , so ist $L(x,\lambda )$ in eine Richtung nach unten unbeschränkt und demnach gilt $\inf _{x\in X}L(x,\lambda )=-\infty$ . Somit lautet die duale Funktion:

q(\lambda )={\begin{cases}-\lambda ^{T}b&{\text{ falls }}c^{T}+\lambda ^{T}A=0\\-\infty &{\text{ sonst }}\end{cases}}

Schreibt man nun die Fallunterscheidung aus der dualen Funktion als Nebenbedingung in das duale Problem, so erhält man:

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 } & -\lambda^Tb \\ \text{unter den Nebenbedingungen } & A^T \lambda +c=0 \\ & \lambda \geq 0 \end{align} }

Dies ist genau ein lineares Optimierungsproblem in Standardform.

Eigenschaften des dualen Problems

Die Definitionsmenge 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 \operatorname{dom}_q } der dualen Funktion ist konvex.
Die duale Funktion ist konkav. Für fixiertes 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 \tilde x } 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 L( \tilde x,\lambda, \mu) } eine affine Funktion und damit 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) } als punktweises Infimum von affinen Funktionen konkav. Somit ist das duale Problem immer ein konvexes Optimierungsproblem, unabhängig von der Struktur des primalen Problems.
Daher sind konvexe Optimierungsprobleme eine Klasse von Problemen, deren duales Problem wieder in derselben Problemklasse liegt. Weitere solche Klassen sind die lineare Optimierungsprobleme (siehe Beispiel), die konischen Programme sowie die semidefiniten Programme und die SOCPs.

Schwache Dualität

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 R_P } die Restriktionsmenge des primalen Problems 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 \operatorname{dom}_q } die Definitionsmenge des dualen Problems. Dann gilt für alle 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 \in R_P } 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 ) \in \operatorname{dom}_q}

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) \leq f(x).}

Der Wert 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)-q(\lambda, \mu) } heißt dann die Dualitätslücke (des zulässigen Punktes 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,\lambda, \mu )} ). Die duale Funktion ist also immer eine untere Schranke für die Zielfunktion des primalen Problems. Somit lässt sich auch das duale Problem motivieren: Es stellt die Frage nach der größten unteren Schranke für das primale Problem, die noch zulässig ist.

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 P=f(R_P) } die Wertemenge des primalen Problems 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 D=q(\operatorname{dom}_q) } die des dualen Problems, 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 \sup (D) \leq \inf (P) } .

Der Wert der dualen Optimallösung ist also stets kleiner als der Wert der primalen Optimallösung. Diese Aussage wird auch schwache Dualität genannt. Der Wert 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 \inf (P)- \sup (D) } heißt dann die optimale Dualitätslücke.

Diese Aussagen folgen direkt aus

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} q(\lambda, \mu) &=\inf_{x \in X}L(x, \lambda, \mu) \leq L( \tilde x , \lambda, \mu) \\ &= f( \tilde x) + \sum_{i=1}^p\lambda_ig_i(\tilde x)+\sum_{j=1}^q\mu_jh_j( \tilde x) \leq f(\tilde x) \quad \text{für alle } (\lambda, \mu) \in \operatorname{dom}_q \text{ und } \tilde x \in R_P.\end{align}}

Dabei folgt die letzte Ungleichung, 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 g_i(\tilde 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 h_j(\tilde x) = 0 } (Zulässigkeit 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 \tilde x } ) 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 } (Zulässigkeit 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 \lambda } ) 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 \lambda_i g_i(\tilde 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 \mu_i h_i(\tilde x) = 0 } . Da die Ungleichung für beliebige 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) \in \operatorname{dom_q} } 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 \tilde x \in R_P } gilt, folgen die beiden obigen Aussagen.

Starke Dualität

Unter gewissen Umständen stimmen der Optimalwert des primalen Problems und der des dualen Problems überein, die optimale Dualitätslücke ist also Null. Es gilt dann

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 \sup (D) = \inf (P) } .

Dieser Fall wird dann starke Dualität genannt. Gilt starke Dualität und ist der Optimalwert endlich und wird in 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^* } 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^*, \mu^*) } angenommen, 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 \sup (D) = \inf (P)=f(x^*)=q(\lambda^*, \mu^*)=L(x^*, \lambda^*,\mu^*)}

Im Allgemeinen gilt starke Dualität nicht, sondern es müssen noch weitere Regularitätsvoraussetzungen (im Englischen constraint qualifications) an das Problem erfüllt sein. Eine der wichtigsten Voraussetzungen für konvexe Optimierungsprobleme und fast-konvexe Funktionen, unter der starke Dualität gilt, ist zum Beispiel die Slater-Bedingung.

Komplementärer Schlupf

Gilt die starke Dualität, sind 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^* } 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^*) } primal bzw. dual optimal und ist der Optimalwert endlich, so gilt die complementary slackness, auch komplementärer Schlupf genannt:

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_ig_i(x^*)=0 \text { für alle } i=1, \dotsc, p }

Ist der 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 i} -te Lagrange-Multiplikator (die 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 i} -te Ungleichungsrestriktion) ungleich null, so muss die 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 i} -te Ungleichungsrestriktion (der 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 i} -te Lagrange-Multiplikator) gleich null sein:

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 > 0 \implies g_i(x^*)=0 \\ g_i(x^*) < 0 \implies \lambda_i=0 \end{align} }

Dies folgt aus 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 } 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 g_i(x^*) \leq 0 } . Es muss also stets mindestens einer der beiden Faktoren null sein.

Sattelpunkte

Ein Punkt 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^*, \lambda^*, \mu^* ) } heißt ein Sattelpunkt der Lagrange-Funktion, wenn für alle 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, \lambda, \mu) } mit 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 \geq 0 }

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 L(x^*, \lambda, \mu ) \leq L(x^*, \lambda^*, \mu^* ) \leq L(x, \lambda^*, \mu^* )}

gilt. Äquivalent dazu 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 \inf_{x \in X} \sup_{(\lambda, \mu)\in dom_q}L(x, \lambda, \mu)=L(x^*, \lambda^*, \mu^*)=\sup_{(\lambda, \mu)\in dom_q} \inf_{x \in X} L(x,\lambda, \mu).}

Dies bedeutet, 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 (\lambda^*, \mu^* ) } ein Maximum der Lagrange-Funktion für fixiertes 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^* } 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 x^* } ein Minimum der Lagrange-Funktion für fixiertes 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^* ) } ist.

Es lässt sich zeigen, 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^*, \lambda^*, \mu^* ) } genau dann ein Sattelpunkt der Lagrange-Funktion ist, 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 x^* } primal optimal 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^*, \mu^*) } dual optimal ist und starke Dualität gilt.

Sattelpunkte spielen eine wichtige Rolle bei der Bestimmung von Optimalpunkten und schlagen eine Verbindung zu den Karush-Kuhn-Tucker-Bedingungen und den Lagrange-Multiplikatoren. Sind zum Beispiel alle beteiligten Funktionen stetig differenzierbar, so lässt sich aus dem Sattelpunktkriterium ableiten, dass an einem Optimalpunkt 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^* }

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 \nabla_x L(x^*,\lambda^*, \mu^*)=0 }

gelten muss, 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^* } nach der Sattelpunktcharakterisierung 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 L(x,\lambda^* , \mu^*) } minimiert. Diese Forderung findet sich zum Beispiel in den Karush-Kuhn-Tucker-Bedingungen zur Bestimmung eines Optimalpunktes und als notwendiges Optimalitätskriterium wieder.

Allgemeinere Formulierungen

Formulierung für Hilberträume

Betrachtet man ein Optimierungsproblem mit verallgemeinerten Ungleichungen zwischen reellen Hilberträumen (also reellen vollständigen Vektorräumen, die mit einem Skalarprodukt versehen sind), so ist dies meist von folgender 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 \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} }

Hierbei sind 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: V_0 \mapsto \mathbb{R} } die Zielfunktion, 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: V_0 \mapsto V_i } die Ungleichungsrestriktionsfunktionen 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 h_j: V_0 \mapsto V_j } die Gleichheitsrestriktionsfunktionen. Die 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 } seien mit dem echten 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 } ausgestattet, der die 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_i} } induziert. Das zum 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_s } gehörende Skalarprodukt sei mit 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_s } bezeichnet. Man setzt dann 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:=(\lambda_1, \dots, \lambda_p)^T , \mu:=(\mu_1, \dots, \mu_q)^T } . Dabei 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 \lambda_i \in V_i } 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 \mu_j \in V_j } . Dann ist die Lagrange-Funktion 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 L(x,\lambda, \mu):= f(x)+\sum_{i=1}^p \langle \lambda_i;g_i(x)\rangle_i+\sum_{j=1}^q \langle \mu_j;h_j(x) \rangle_j}

und die duale Funktion lautet

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} L(x,\lambda, \mu). }

Das duale Problem lautet dann:

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^D} & 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 K^D } der duale Kegel 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 } .

Alternative Formulierungen fassen alle Ungleichungsrestriktionen und Gleichheitsrestriktionen zusammen:

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(x)=(g_1(x), \dots, g_p(x))^T \, , \, h(x)=(h_1(x), \dots, h_j(x))^T, K:=K_1 \times \dots \times K_p }

Dies führt zu einer kompakteren Schreibweise, die ohne Summenzeichen und Indizes auskommt und daher für theoretische Betrachtungen bevorzugt wird. Alternativ wird auch die Forderung nach einem echten Kegel abgeschwächt, stattdessen definiert man die Ungleichung nur durch einen Ordnungskegel, der zumindest konvex sein muss. Manchmal wir auch komplett auf Gleichheitsnebenbedingungen verzichtet, man modelliert diese dann stattdessen als Ordnungskegel mit leerem Inneren. Statt 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(x) \in -K \, , \, h(x)=0 } zu fordern, definiert man einen 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'=K \times \{0\} } . Dann 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(x), h(x)) \in -K' } genau dann, 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 g(x) \in -K \, , \, h(x)=0 } . Für alle drei Varianten sind die Lagrange-Funktion und das duale Problem in der untenstehenden Tabelle angegeben. Die duale Funktion ist stets 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 q(\lambda, \mu)=\inf_{x \in X} L(x,\lambda, \mu) } bzw., wenn nur eine duale Variable verwendet wird, 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 q(\lambda)=\inf_{x \in X} L(x,\lambda) } .

Primales Problem	Lagrange-Funktion	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(x) \preccurlyeq_{K} 0 \\ & h(x)=0 \\ & 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 L(x,\lambda, \mu)=f(x)+\langle \lambda; g(x) \rangle_1 + \langle \mu ; h(x) \rangle_2 }	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 \succcurlyeq_{K^D} 0 \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{Minimiere } & f(x) & \\ \text{unter den Nebenbedingungen } & g(x) \in -K \\ & h(x)=0 \\ & 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 L(x,\lambda, \mu)=f(x)+\langle \lambda; g(x) \rangle_1 + \langle \mu ; h(x) \rangle_2 }	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 \in K^D \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{Minimiere } & f(x) & \\ \text{unter den Nebenbedingungen } & g(x) \in -K \\ & 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 L(x,\lambda)=f(x)+\langle \lambda; g(x) \rangle_1 }	: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) & \\ \text{unter den Nebenbedingungen } & \lambda \in K^D \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 f: V_0 \mapsto \mathbb{R} } die Zielfunktion, 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: V_0 \mapsto V_1 } , wobei auf 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_1 } ein 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 } ausgezeichnet ist, der im ersten Fall ein echter Kegel ist, im zweiten und dritten Fall ein konvexer Kegel ist. Es 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 h: V_0 \mapsto V_2 } 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 \in V_1, \, \mu \in V_2 } .

Formulierung für normierte Räume

Für Probleme mit Abbildungen zwischen reellen normierten Vektorräumen ist zu beachten, dass kein Skalarprodukt definiert ist. Man wählt stattdessen die duale Paarung. Dementsprechend sind die dualen Variablen aus dem Dualraum des Vektorraumes. Ist ein Problem 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 \begin{align} \text{Minimiere } & f(x) & \\ \text{unter den Nebenbedingungen } & g(x) \in -K \\ & h(x)=0 \\ & x \in X & \end{align} }

gegeben, wobei 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: V_0 \mapsto \mathbb{R} } die Zielfunktion, 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: V_0 \mapsto V_1 } die Ungleichungsrestriktionsfunktionen 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 h_j: V_0 \mapsto V_2 } die Gleichungsrestriktionsfunktion sind. 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 } sei ein Ordnungskegel auf 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_1 } und es seien 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_0, V_1, V_2 } Banachräume. Die Lagrange-Funktion lautet dann

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 L(x, u,v)=f(x)+u(g(x))+v(h(x)). }

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 u } aus dem Dualraum 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_1^* } 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 v } aus dem Dualraum 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_2^*. } Die duale Funktion ist dann wieder

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(u,v)=\inf_{x \in X} L(x,u,v) }

und damit lautet das duale 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{Maximiere } & q(u, v) & \\ \text{unter den Nebenbedingungen } & u \in K^* \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 K^* } der duale Kegel, der in diesem Fall aber eine Teilmenge 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 V_1^* } ist. Formulierungen für alternative Problemstellungen laufen analog zu den Problemen für Abbildungen zwischen Hilberträumen. Die duale Paarung ersetzt jeweils das Skalarprodukt, die dualen Variablen befinden sich im Dualraum.

Schwache und starke Dualität

Die schwache Dualität gilt auch für die beiden allgemeineren Formulierungen. Für den Beweis in der Hilbertraumformulierung nutzt man aus, 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 } ist, 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 \succcurlyeq_{K^D} 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 b \preccurlyeq_{K}} gilt (für Ordnungskegel erhält man 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 \in K^D , \, b \in -K \implies \langle a ; b \rangle \leq 0 } ). In normierten Räumen gelten analoge Aussagen mit dem Unterschied, 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 a } ein Element des Dualraumes ist: 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 a \in K^*, b \in - K } , so 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 a(b)\leq 0 } .

Die starke Dualität wird in den allgemeineren Fällen identisch zum gewöhnlichen Fall definiert. Auch im verallgemeinerten Fall existieren Regularitätsvoraussetzungen wie die Slater-Bedingung, die starke Dualität garantieren.

Literatur

Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
Stephan Boyd, Lieven Vandenberghe: Convex Optimization. Cambridge University Press, 2004, ISBN 978-0-521-83378-3 (online).
C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002, ISBN 3-540-42790-2.
Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.

Anonym

Suche

Lagrange-Dualität

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Lagrange-Funktion, duales Problem

Beispiel

Eigenschaften des dualen Problems

Schwache Dualität

Starke Dualität

Komplementärer Schlupf

Sattelpunkte

Allgemeinere Formulierungen

Formulierung für Hilberträume

Formulierung für normierte Räume

Schwache und starke Dualität

Literatur

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Lagrange-Dualität

Lagrange-Funktion, duales Problem

Beispiel

Eigenschaften des dualen Problems

Schwache Dualität

Starke Dualität

Komplementärer Schlupf

Sattelpunkte

Allgemeinere Formulierungen

Formulierung für Hilberträume

Formulierung für normierte Räume

Schwache und starke Dualität

Literatur

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien