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{matrix} Minimiere & f (x) \\ unter den Nebenbedingungen & g_{i} (x) \leq 0 & i = 1, \dots, p \\ h_{j} (x) = 0 & j = 1, \dots, q \\ x \in X \end{matrix}

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

Die Funktion

L (x, λ, μ) := f (x) + \sum_{i = 1}^{p} λ_{i} g_{i} (x) + \sum_{j = 1}^{q} μ_{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 $λ_{i}, μ_{j}$ zu Vektoren $g (x) = (g_{1} (x), \dots, g_{p} (x))^{T}, h (x) = (h_{1} (x), \dots, h_{q} (x))^{T}$ und $λ = (λ_{1}, \dots, λ_{p})^{T}, μ = (μ_{1}, \dots, μ_{q})^{T}$ zusammengefasst. Die Lagrange-Funktion vereinfacht sich dann zu

L (x, λ, μ) := f (x) + λ^{T} g (x) + μ^{T} h (x) .

$(λ, μ)$ werden duale Variablen oder Lagrange-Multiplikatoren genannt. Die Funktion

q (λ, μ) = inf_{x \in X} L (x, λ, μ)

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

\begin{matrix} Maximiere & q (λ, μ) \\ unter den Nebenbedingungen & λ \geq 0 \end{matrix}

heißt das duale Problem des obigen Optimierungsproblems. Dabei ist $λ \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

{dom}_{q} := {(λ, μ) \in ℝ^{p} \times ℝ^{q} | λ \geq 0, q (λ, μ) > - \infty}

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

Beispiel

Betrachtet man als Beispiel ein lineares Optimierungsproblem in Ungleichungsform:

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

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

L (x, λ) = c^{T} x + λ^{T} (A x - b) = (c^{T} + λ^{T} A) x - λ^{T} b

.

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

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

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

\begin{matrix} Maximiere & - λ^{T} b \\ unter den Nebenbedingungen & A^{T} λ + c = 0 \\ λ \geq 0 \end{matrix}

Dies ist genau ein lineares Optimierungsproblem in Standardform.

Eigenschaften des dualen Problems

Die Definitionsmenge ${dom}_{q}$ der dualen Funktion ist konvex.
Die duale Funktion ist konkav. Für fixiertes $\tilde{x}$ ist $L (\tilde{x}, λ, μ)$ eine affine Funktion und damit ist $q (λ, μ)$ 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 $R_{P}$ die Restriktionsmenge des primalen Problems und ${dom}_{q}$ die Definitionsmenge des dualen Problems. Dann gilt für alle $x \in R_{P}$ und $(λ, μ) \in {dom}_{q}$

q (λ, μ) \leq f (x) .

Der Wert $f (x) - q (λ, μ)$ heißt dann die Dualitätslücke (des zulässigen Punktes $(x, λ, μ)$ ). 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 $P = f (R_{P})$ die Wertemenge des primalen Problems und $D = q ({dom}_{q})$ die des dualen Problems, so gilt

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 $inf (P) - sup (D)$ heißt dann die optimale Dualitätslücke.

Diese Aussagen folgen direkt aus

\begin{matrix} q (λ, μ) & = inf_{x \in X} L (x, λ, μ) \leq L (\tilde{x}, λ, μ) \\ = f (\tilde{x}) + \sum_{i = 1}^{p} λ_{i} g_{i} (\tilde{x}) + \sum_{j = 1}^{q} μ_{j} h_{j} (\tilde{x}) \leq f (\tilde{x}) für alle (λ, μ) \in {dom}_{q} und \tilde{x} \in R_{P} . \end{matrix}

Dabei folgt die letzte Ungleichung, da $g_{i} (\tilde{x}) \leq 0$ und $h_{j} (\tilde{x}) = 0$ (Zulässigkeit von $\tilde{x}$ ) und $λ_{i} \geq 0$ (Zulässigkeit von $λ$ ) und damit $λ_{i} g_{i} (\tilde{x}) \leq 0$ und $μ_{i} h_{i} (\tilde{x}) = 0$ . Da die Ungleichung für beliebige $(λ, μ) \in d o m_{q}$ und $\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

sup (D) = inf (P)

.

Dieser Fall wird dann starke Dualität genannt. Gilt starke Dualität und ist der Optimalwert endlich und wird in $x^{*}$ bzw. $(λ^{*}, μ^{*})$ angenommen, so gilt:

sup (D) = inf (P) = f (x^{*}) = q (λ^{*}, μ^{*}) = L (x^{*}, λ^{*}, μ^{*})

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 $x^{*}$ und $(λ^{*}, μ^{*})$ primal bzw. dual optimal und ist der Optimalwert endlich, so gilt die complementary slackness, auch komplementärer Schlupf genannt:

λ_{i} g_{i} (x^{*}) = 0 für alle i = 1, \dots, p

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

\begin{matrix} λ_{i} > 0 ⟹ g_{i} (x^{*}) = 0 \\ g_{i} (x^{*}) < 0 ⟹ λ_{i} = 0 \end{matrix}

Dies folgt aus $λ_{i} \geq 0$ und $g_{i} (x^{*}) \leq 0$ . Es muss also stets mindestens einer der beiden Faktoren null sein.

Sattelpunkte

Ein Punkt $(x^{*}, λ^{*}, μ^{*})$ heißt ein Sattelpunkt der Lagrange-Funktion, wenn für alle $(x, λ, μ)$ mit $λ \geq 0$

L (x^{*}, λ, μ) \leq L (x^{*}, λ^{*}, μ^{*}) \leq L (x, λ^{*}, μ^{*})

gilt. Äquivalent dazu ist

inf_{x \in X} sup_{(λ, μ) \in d o m_{q}} L (x, λ, μ) = L (x^{*}, λ^{*}, μ^{*}) = sup_{(λ, μ) \in d o m_{q}} inf_{x \in X} L (x, λ, μ) .

Dies bedeutet, dass $(λ^{*}, μ^{*})$ ein Maximum der Lagrange-Funktion für fixiertes $x^{*}$ und $x^{*}$ ein Minimum der Lagrange-Funktion für fixiertes $(λ^{*}, μ^{*})$ ist.

Es lässt sich zeigen, dass $(x^{*}, λ^{*}, μ^{*})$ genau dann ein Sattelpunkt der Lagrange-Funktion ist, wenn $x^{*}$ primal optimal ist, $(λ^{*}, μ^{*})$ 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 $x^{*}$

\nabla_{x} L (x^{*}, λ^{*}, μ^{*}) = 0

gelten muss, da $x^{*}$ nach der Sattelpunktcharakterisierung $L (x, λ^{*}, μ^{*})$ 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:

\begin{matrix} Minimiere & f (x) \\ unter den Nebenbedingungen & g_{i} (x) ≼_{K_{i}} 0 & i = 1, \dots, p \\ h_{j} (x) = 0 & j = 1, \dots, q \\ x \in X \end{matrix}

Hierbei sind $f : V_{0} \mapsto ℝ$ die Zielfunktion, $g_{i} : V_{0} \mapsto V_{i}$ die Ungleichungsrestriktionsfunktionen und $h_{j} : V_{0} \mapsto V_{j}$ die Gleichheitsrestriktionsfunktionen. Die $V_{i}$ seien mit dem echten Kegel $K_{i}$ ausgestattet, der die verallgemeinerte Ungleichung $≼_{K_{i}}$ induziert. Das zum Vektorraum $V_{s}$ gehörende Skalarprodukt sei mit $⟨ \cdot; \cdot ⟩_{s}$ bezeichnet. Man setzt dann $λ := (λ_{1}, \dots, λ_{p})^{T}, μ := (μ_{1}, \dots, μ_{q})^{T}$ . Dabei gilt $λ_{i} \in V_{i}$ und $μ_{j} \in V_{j}$ . Dann ist die Lagrange-Funktion von der Form

L (x, λ, μ) := f (x) + \sum_{i = 1}^{p} ⟨ λ_{i}; g_{i} (x) ⟩_{i} + \sum_{j = 1}^{q} ⟨ μ_{j}; h_{j} (x) ⟩_{j}

und die duale Funktion lautet

q (λ, μ) = inf_{x \in X} L (x, λ, μ) .

Das duale Problem lautet dann:

\begin{matrix} Maximiere & q (λ, μ) \\ unter den Nebenbedingungen & λ_{i} ≽_{K^{D}} 0 & i = 1, \dots, p \end{matrix}

,

Dabei ist $K^{D}$ der duale Kegel von $K$ .

Alternative Formulierungen fassen alle Ungleichungsrestriktionen und Gleichheitsrestriktionen zusammen:

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 $g (x) \in - K, h (x) = 0$ zu fordern, definiert man einen Kegel $K^{'} = K \times {0}$ . Dann gilt $(g (x), h (x)) \in - K^{'}$ genau dann, wenn $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 $q (λ, μ) = inf_{x \in X} L (x, λ, μ)$ bzw., wenn nur eine duale Variable verwendet wird, von der Form $q (λ) = inf_{x \in X} L (x, λ)$ .

Primales Problem	Lagrange-Funktion	Duales Problem
$\begin{matrix} Minimiere & f (x) \\ unter den Nebenbedingungen & g (x) ≼_{K} 0 \\ h (x) = 0 \\ x \in X \end{matrix}$	$L (x, λ, μ) = f (x) + ⟨ λ; g (x) ⟩_{1} + ⟨ μ; h (x) ⟩_{2}$	$\begin{matrix} Maximiere & q (λ, μ) \\ unter den Nebenbedingungen & λ ≽_{K^{D}} 0 \end{matrix}$
$\begin{matrix} Minimiere & f (x) \\ unter den Nebenbedingungen & g (x) \in - K \\ h (x) = 0 \\ x \in X \end{matrix}$	$L (x, λ, μ) = f (x) + ⟨ λ; g (x) ⟩_{1} + ⟨ μ; h (x) ⟩_{2}$	$\begin{matrix} Maximiere & q (λ, μ) \\ unter den Nebenbedingungen & λ \in K^{D} \end{matrix}$
$\begin{matrix} Minimiere & f (x) \\ unter den Nebenbedingungen & g (x) \in - K \\ x \in X \end{matrix}$	$L (x, λ) = f (x) + ⟨ λ; g (x) ⟩_{1}$	$\begin{matrix} Maximiere & q (λ) \\ unter den Nebenbedingungen & λ \in K^{D} \end{matrix}$

Dabei ist $f : V_{0} \mapsto ℝ$ die Zielfunktion, $g : V_{0} \mapsto V_{1}$ , wobei auf $V_{1}$ ein Kegel $K$ ausgezeichnet ist, der im ersten Fall ein echter Kegel ist, im zweiten und dritten Fall ein konvexer Kegel ist. Es ist $h : V_{0} \mapsto V_{2}$ und $λ \in V_{1}, μ \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

\begin{matrix} Minimiere & f (x) \\ unter den Nebenbedingungen & g (x) \in - K \\ h (x) = 0 \\ x \in X \end{matrix}

gegeben, wobei $f : V_{0} \mapsto ℝ$ die Zielfunktion, $g_{i} : V_{0} \mapsto V_{1}$ die Ungleichungsrestriktionsfunktionen und $h_{j} : V_{0} \mapsto V_{2}$ die Gleichungsrestriktionsfunktion sind. $K$ sei ein Ordnungskegel auf $V_{1}$ und es seien $V_{0}, V_{1}, V_{2}$ Banachräume. Die Lagrange-Funktion lautet dann

L (x, u, v) = f (x) + u (g (x)) + v (h (x)) .

Dabei ist $u$ aus dem Dualraum $V_{1}^{*}$ und $v$ aus dem Dualraum $V_{2}^{*} .$ Die duale Funktion ist dann wieder

q (u, v) = inf_{x \in X} L (x, u, v)

und damit lautet das duale Problem:

\begin{matrix} Maximiere & q (u, v) \\ unter den Nebenbedingungen & u \in K^{*} \end{matrix}

Dabei ist $K^{*}$ der duale Kegel, der in diesem Fall aber eine Teilmenge von $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 $⟨ a; b ⟩ \leq 0$ ist, wenn $a ≽_{K^{D}} 0$ und $b ≼_{K}$ gilt (für Ordnungskegel erhält man $a \in K^{D}, b \in - K ⟹ ⟨ a; b ⟩ \leq 0$ ). In normierten Räumen gelten analoge Aussagen mit dem Unterschied, dass $a$ ein Element des Dualraumes ist: Gilt $a \in K^{*}, b \in - K$ , so folgt $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.