Lagrange-Dualität

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Duales Problem)
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

Gegeben sei folgendes Optimierungsproblem:

Dabei kann die abstrakte Restriktion beispielsweise Forderungen wie (Ganzzahligkeit) oder für einen Kegel aufnehmen. Die auftretenden Funktionen müssen weder konvex noch differenzierbar sein.

Die Funktion

heißt dann die zu dem obigen Optimierungsproblem gehörende Lagrange-Funktion. Gelegentlich werden die Funktionen sowie die Skalare zu Vektoren und zusammengefasst. Die Lagrange-Funktion vereinfacht sich dann zu

werden duale Variablen oder Lagrange-Multiplikatoren genannt. Die Funktion

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

heißt das duale Problem des obigen Optimierungsproblems. Dabei ist 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 annehmen. Man definiert dann

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 gilt.

Betrachtet man als Beispiel ein lineares Optimierungsproblem in Ungleichungsform:

Dabei ist und . Der Vollständigkeit halber setzt man , was in diesem Fall keine Einschränkung bedeutet. Die Lagrange-Funktion ist dann

.

Ist , so ist unabhängig von und damit ist . Ist aber , so ist in eine Richtung nach unten unbeschränkt und demnach gilt . Somit lautet die duale Funktion:

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

Dies ist genau ein lineares Optimierungsproblem in Standardform.

Eigenschaften des dualen Problems

[Bearbeiten | Quelltext bearbeiten]
  • Die Definitionsmenge der dualen Funktion ist konvex.
  • Die duale Funktion ist konkav. Für fixiertes ist eine affine Funktion und damit ist 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

[Bearbeiten | Quelltext bearbeiten]

Sei die Restriktionsmenge des primalen Problems und die Definitionsmenge des dualen Problems. Dann gilt für alle und

Der Wert heißt dann die Dualitätslücke (des zulässigen Punktes ). 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 die Wertemenge des primalen Problems und die des dualen Problems, so gilt

.

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 heißt dann die optimale Dualitätslücke.

Diese Aussagen folgen direkt aus

Dabei folgt die letzte Ungleichung, da und (Zulässigkeit von ) und (Zulässigkeit von ) und damit und . Da die Ungleichung für beliebige und gilt, folgen die beiden obigen Aussagen.

Starke Dualität

[Bearbeiten | Quelltext bearbeiten]

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

.

Dieser Fall wird dann starke Dualität genannt. Gilt starke Dualität und ist der Optimalwert endlich und wird in bzw. angenommen, so gilt:

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

[Bearbeiten | Quelltext bearbeiten]

Gilt die starke Dualität, sind und primal bzw. dual optimal und ist der Optimalwert endlich, so gilt die complementary slackness, auch komplementärer Schlupf genannt:

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

Dies folgt aus und . Es muss also stets mindestens einer der beiden Faktoren null sein.

Ein Punkt heißt ein Sattelpunkt der Lagrange-Funktion, wenn für alle mit

gilt. Äquivalent dazu ist

Dies bedeutet, dass ein Maximum der Lagrange-Funktion für fixiertes und ein Minimum der Lagrange-Funktion für fixiertes ist.

Es lässt sich zeigen, dass genau dann ein Sattelpunkt der Lagrange-Funktion ist, wenn 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

gelten muss, da nach der Sattelpunktcharakterisierung 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

[Bearbeiten | Quelltext bearbeiten]

Formulierung für Hilberträume

[Bearbeiten | Quelltext bearbeiten]

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:

Hierbei sind die Zielfunktion, die Ungleichungsrestriktionsfunktionen und die Gleichheitsrestriktionsfunktionen. Die seien mit dem echten Kegel ausgestattet, der die verallgemeinerte Ungleichung induziert. Das zum Vektorraum gehörende Skalarprodukt sei mit bezeichnet. Man setzt dann . Dabei gilt und . Dann ist die Lagrange-Funktion von der Form

und die duale Funktion lautet

Das duale Problem lautet dann:

,

Dabei ist der duale Kegel von .

Alternative Formulierungen fassen alle Ungleichungsrestriktionen und Gleichheitsrestriktionen zusammen:

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 zu fordern, definiert man einen Kegel . Dann gilt genau dann, wenn . 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 bzw., wenn nur eine duale Variable verwendet wird, von der Form .

Primales Problem Lagrange-Funktion Duales Problem

Dabei ist die Zielfunktion, , wobei auf ein Kegel ausgezeichnet ist, der im ersten Fall ein echter Kegel ist, im zweiten und dritten Fall ein konvexer Kegel ist. Es ist und .

Formulierung für normierte Räume

[Bearbeiten | Quelltext bearbeiten]

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

gegeben, wobei die Zielfunktion, die Ungleichungsrestriktionsfunktionen und die Gleichungsrestriktionsfunktion sind. sei ein Ordnungskegel auf und es seien Banachräume. Die Lagrange-Funktion lautet dann

Dabei ist aus dem Dualraum und aus dem Dualraum Die duale Funktion ist dann wieder

und damit lautet das duale Problem:

Dabei ist der duale Kegel, der in diesem Fall aber eine Teilmenge von 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

[Bearbeiten | Quelltext bearbeiten]

Die schwache Dualität gilt auch für die beiden allgemeineren Formulierungen. Für den Beweis in der Hilbertraumformulierung nutzt man aus, dass ist, wenn und gilt (für Ordnungskegel erhält man ). In normierten Räumen gelten analoge Aussagen mit dem Unterschied, dass ein Element des Dualraumes ist: Gilt , so folgt .

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.

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