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

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.

Beispiel

Bearbeiten

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

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

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

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.

Sattelpunkte

Bearbeiten

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

Formulierung für Hilberträume

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

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

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.

Literatur

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