Die Lagrange Dualitat ist eine wichtige Dualitat in der mathematischen Optimierung die sowohl Optimalitatskriterien mittels der Karush Kuhn Tucker Bedingungen oder der Lagrange Multiplikatoren liefert als auch aquivalente Umformulierungen von Optimierungsproblemen moglich macht Ziel ist es das ursprungliche primale Problem in ein duales Problem zu uberfuhren Inhaltsverzeichnis 1 Lagrange Funktion duales Problem 2 Beispiel 3 Eigenschaften des dualen Problems 4 Schwache Dualitat 5 Starke Dualitat 6 Komplementarer Schlupf 7 Sattelpunkte 8 Allgemeinere Formulierungen 8 1 Formulierung fur Hilbertraume 8 2 Formulierung fur normierte Raume 8 3 Schwache und starke Dualitat 9 LiteraturLagrange Funktion duales Problem BearbeitenGegeben sei folgendes Optimierungsproblem Minimiere f x unter den Nebenbedingungen g i x 0 i 1 p h j x 0 j 1 q x X displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g i x leq 0 amp i 1 dotsc p amp h j x 0 amp j 1 dotsc q amp x in X amp end aligned nbsp Dabei kann die abstrakte Restriktion x X displaystyle x in X nbsp beispielsweise Forderungen wie x Z n displaystyle x in mathbb Z n nbsp Ganzzahligkeit oder x K displaystyle x in mathcal K nbsp fur einen Kegel K displaystyle mathcal K nbsp aufnehmen Die auftretenden Funktionen mussen weder konvex noch differenzierbar sein Die Funktion L x l m f x i 1 p l i g i x j 1 q m j h j x displaystyle L x lambda mu f x sum i 1 p lambda i g i x sum j 1 q mu j h j x nbsp heisst dann die zu dem obigen Optimierungsproblem gehorende Lagrange Funktion Gelegentlich werden die Funktionen g i h j displaystyle g i h j nbsp sowie die Skalare l i m j displaystyle lambda i mu j nbsp zu Vektoren g x g 1 x g p x T h x h 1 x h q x T displaystyle g x g 1 x dots g p x T h x h 1 x dots h q x T nbsp und l l 1 l p T m m 1 m q T displaystyle lambda lambda 1 dots lambda p T mu mu 1 dots mu q T nbsp zusammengefasst Die Lagrange Funktion vereinfacht sich dann zu L x l m f x l T g x m T h x displaystyle L x lambda mu f x lambda T g x mu T h x nbsp l m displaystyle lambda mu nbsp werden duale Variablen oder Lagrange Multiplikatoren genannt Die Funktion q l m inf x X L x l m displaystyle q lambda mu inf x in X L x lambda mu nbsp heisst dann die duale Funktion zu dem obigen Optimierungsproblem Das Optimierungsproblem Maximiere q l m unter den Nebenbedingungen l 0 displaystyle begin aligned text Maximiere amp q lambda mu text unter den Nebenbedingungen amp lambda geq 0 end aligned nbsp heisst das duale Problem des obigen Optimierungsproblems Dabei ist l 0 displaystyle lambda geq 0 nbsp komponentenweise zu verstehen Das ursprungliche Problem wird dann auch als primales Problem bezeichnet Im Allgemeinen muss die duale Funktion nicht reellwertig sein sie kann durchaus auch den Wert displaystyle infty nbsp annehmen Man definiert dann dom q l m R p R q l 0 q l m gt displaystyle operatorname dom q lambda mu in mathbb R p times mathbb R q lambda geq 0 q lambda mu gt infty nbsp als den wesentlichen Definitionsbereich der dualen Funktion Die dualen Variablen l m displaystyle lambda mu nbsp werden dual zulassig genannt wenn sie zulassig bezuglich des dualen Problems sind das heisst wenn l 0 displaystyle lambda geq 0 nbsp gilt Beispiel BearbeitenBetrachtet man als Beispiel ein lineares Optimierungsproblem in Ungleichungsform Minimiere f x c T x unter den Nebenbedingungen A x b 0 displaystyle begin aligned text Minimiere amp f x c T x text unter den Nebenbedingungen amp Ax b leq 0 end aligned nbsp Dabei ist x c R n b R m displaystyle x c in mathbb R n b in mathbb R m nbsp und A R m n displaystyle A in mathbb R m times n nbsp Der Vollstandigkeit halber setzt man X R n displaystyle X mathbb R n nbsp was in diesem Fall keine Einschrankung bedeutet Die Lagrange Funktion ist dann L x l c T x l T A x b c T l T A x l T b displaystyle L x lambda c T x lambda T Ax b c T lambda T A x lambda T b nbsp Ist c T l T A displaystyle c T lambda T A nbsp so ist L x l displaystyle L x lambda nbsp unabhangig von x displaystyle x nbsp und damit ist inf x X L x l l T b displaystyle inf x in X L x lambda lambda T b nbsp Ist aber c T l T A displaystyle c T neq lambda T A nbsp so ist L x l displaystyle L x lambda nbsp in eine Richtung nach unten unbeschrankt und demnach gilt inf x X L x l displaystyle inf x in X L x lambda infty nbsp Somit lautet die duale Funktion q l l T b falls c T l T A 0 sonst displaystyle q lambda begin cases lambda T b amp text falls c T lambda T A 0 infty amp text sonst end cases nbsp Schreibt man nun die Fallunterscheidung aus der dualen Funktion als Nebenbedingung in das duale Problem so erhalt man Maximiere l T b unter den Nebenbedingungen A T l c 0 l 0 displaystyle begin aligned text Maximiere amp lambda T b text unter den Nebenbedingungen amp A T lambda c 0 amp lambda geq 0 end aligned nbsp Dies ist genau ein lineares Optimierungsproblem in Standardform Eigenschaften des dualen Problems BearbeitenDie Definitionsmenge dom q displaystyle operatorname dom q nbsp der dualen Funktion ist konvex Die duale Funktion ist konkav Fur fixiertes x displaystyle tilde x nbsp ist L x l m displaystyle L tilde x lambda mu nbsp eine affine Funktion und damit ist q l m displaystyle q lambda mu nbsp als punktweises Infimum von affinen Funktionen konkav Somit ist das duale Problem immer ein konvexes Optimierungsproblem unabhangig 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 Dualitat BearbeitenSei R P displaystyle R P nbsp die Restriktionsmenge des primalen Problems und dom q displaystyle operatorname dom q nbsp die Definitionsmenge des dualen Problems Dann gilt fur alle x R P displaystyle x in R P nbsp und l m dom q displaystyle lambda mu in operatorname dom q nbsp q l m f x displaystyle q lambda mu leq f x nbsp Der Wert f x q l m displaystyle f x q lambda mu nbsp heisst dann die Dualitatslucke des zulassigen Punktes x l m displaystyle x lambda mu nbsp Die duale Funktion ist also immer eine untere Schranke fur die Zielfunktion des primalen Problems Somit lasst sich auch das duale Problem motivieren Es stellt die Frage nach der grossten unteren Schranke fur das primale Problem die noch zulassig ist Ist P f R P displaystyle P f R P nbsp die Wertemenge des primalen Problems und D q dom q displaystyle D q operatorname dom q nbsp die des dualen Problems so gilt sup D inf P displaystyle sup D leq inf P nbsp Der Wert der dualen Optimallosung ist also stets kleiner als der Wert der primalen Optimallosung Diese Aussage wird auch schwache Dualitat genannt Der Wert inf P sup D displaystyle inf P sup D nbsp heisst dann die optimale Dualitatslucke Diese Aussagen folgen direkt aus q l m inf x X L x l m L x l m f x i 1 p l i g i x j 1 q m j h j x f x fur alle l m dom q und x R P displaystyle begin aligned q lambda mu amp inf x in X L x lambda mu leq L tilde x lambda mu amp f tilde x sum i 1 p lambda i g i tilde x sum j 1 q mu j h j tilde x leq f tilde x quad text fur alle lambda mu in operatorname dom q text und tilde x in R P end aligned nbsp Dabei folgt die letzte Ungleichung da g i x 0 displaystyle g i tilde x leq 0 nbsp und h j x 0 displaystyle h j tilde x 0 nbsp Zulassigkeit von x displaystyle tilde x nbsp und l i 0 displaystyle lambda i geq 0 nbsp Zulassigkeit von l displaystyle lambda nbsp und damit l i g i x 0 displaystyle lambda i g i tilde x leq 0 nbsp und m i h i x 0 displaystyle mu i h i tilde x 0 nbsp Da die Ungleichung fur beliebige l m d o m q displaystyle lambda mu in operatorname dom q nbsp und x R P displaystyle tilde x in R P nbsp gilt folgen die beiden obigen Aussagen Starke Dualitat BearbeitenUnter gewissen Umstanden stimmen der Optimalwert des primalen Problems und der des dualen Problems uberein die optimale Dualitatslucke ist also Null Es gilt dann sup D inf P displaystyle sup D inf P nbsp Dieser Fall wird dann starke Dualitat genannt Gilt starke Dualitat und ist der Optimalwert endlich und wird in x displaystyle x nbsp bzw l m displaystyle lambda mu nbsp angenommen so gilt sup D inf P f x q l m L x l m displaystyle sup D inf P f x q lambda mu L x lambda mu nbsp Im Allgemeinen gilt starke Dualitat nicht sondern es mussen noch weitere Regularitatsvoraussetzungen im Englischen constraint qualifications an das Problem erfullt sein Eine der wichtigsten Voraussetzungen fur konvexe Optimierungsprobleme und fast konvexe Funktionen unter der starke Dualitat gilt ist zum Beispiel die Slater Bedingung Komplementarer Schlupf Bearbeiten Hauptartikel Komplementarer Schlupf Gilt die starke Dualitat sind x displaystyle x nbsp und l m displaystyle lambda mu nbsp primal bzw dual optimal und ist der Optimalwert endlich so gilt die complementary slackness auch komplementarer Schlupf genannt l i g i x 0 fur alle i 1 p displaystyle lambda i g i x 0 text fur alle i 1 dotsc p nbsp Ist der i displaystyle i nbsp te Lagrange Multiplikator die i displaystyle i nbsp te Ungleichungsrestriktion ungleich null so muss die i displaystyle i nbsp te Ungleichungsrestriktion der i displaystyle i nbsp te Lagrange Multiplikator gleich null sein l i gt 0 g i x 0 g i x lt 0 l i 0 displaystyle begin aligned lambda i gt 0 implies g i x 0 g i x lt 0 implies lambda i 0 end aligned nbsp Dies folgt aus l i 0 displaystyle lambda i geq 0 nbsp und g i x 0 displaystyle g i x leq 0 nbsp Es muss also stets mindestens einer der beiden Faktoren null sein Sattelpunkte BearbeitenEin Punkt x l m displaystyle x lambda mu nbsp heisst ein Sattelpunkt der Lagrange Funktion wenn fur alle x l m displaystyle x lambda mu nbsp mit l 0 displaystyle lambda geq 0 nbsp L x l m L x l m L x l m displaystyle L x lambda mu leq L x lambda mu leq L x lambda mu nbsp gilt Aquivalent dazu ist inf x X sup l m d o m q L x l m L x l m sup l m d o m q inf x X L x l m 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 nbsp Dies bedeutet dass l m displaystyle lambda mu nbsp ein Maximum der Lagrange Funktion fur fixiertes x displaystyle x nbsp und x displaystyle x nbsp ein Minimum der Lagrange Funktion fur fixiertes l m displaystyle lambda mu nbsp ist Es lasst sich zeigen dass x l m displaystyle x lambda mu nbsp genau dann ein Sattelpunkt der Lagrange Funktion ist wenn x displaystyle x nbsp primal optimal ist l m displaystyle lambda mu nbsp dual optimal ist und starke Dualitat 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 lasst sich aus dem Sattelpunktkriterium ableiten dass an einem Optimalpunkt x displaystyle x nbsp x L x l m 0 displaystyle nabla x L x lambda mu 0 nbsp gelten muss da x displaystyle x nbsp nach der Sattelpunktcharakterisierung L x l m displaystyle L x lambda mu nbsp minimiert Diese Forderung findet sich zum Beispiel in den Karush Kuhn Tucker Bedingungen zur Bestimmung eines Optimalpunktes und als notwendiges Optimalitatskriterium wieder Allgemeinere Formulierungen BearbeitenFormulierung fur Hilbertraume Bearbeiten Betrachtet man ein Optimierungsproblem mit verallgemeinerten Ungleichungen zwischen reellen Hilbertraumen also reellen vollstandigen Vektorraumen die mit einem Skalarprodukt versehen sind so ist dies meist von folgender Form Minimiere f x unter den Nebenbedingungen g i x K i 0 i 1 p h j x 0 j 1 q x X displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g i x preccurlyeq K i 0 amp i 1 dotsc p amp h j x 0 amp j 1 dotsc q amp x in X amp end aligned nbsp Hierbei sind f V 0 R displaystyle f V 0 mapsto mathbb R nbsp die Zielfunktion g i V 0 V i displaystyle g i V 0 mapsto V i nbsp die Ungleichungsrestriktionsfunktionen und h j V 0 V j displaystyle h j V 0 mapsto V j nbsp die Gleichheitsrestriktionsfunktionen Die V i displaystyle V i nbsp seien mit dem echten Kegel K i displaystyle K i nbsp ausgestattet der die verallgemeinerte Ungleichung K i displaystyle preccurlyeq K i nbsp induziert Das zum Vektorraum V s displaystyle V s nbsp gehorende Skalarprodukt sei mit s displaystyle langle cdot cdot rangle s nbsp bezeichnet Man setzt dann l l 1 l p T m m 1 m q T displaystyle lambda lambda 1 dots lambda p T mu mu 1 dots mu q T nbsp Dabei gilt l i V i displaystyle lambda i in V i nbsp und m j V j displaystyle mu j in V j nbsp Dann ist die Lagrange Funktion von der Form L x l m f x i 1 p l i g i x i j 1 q m j h j x j 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 nbsp und die duale Funktion lautet q l m inf x X L x l m displaystyle q lambda mu inf x in X L x lambda mu nbsp Das duale Problem lautet dann Maximiere q l m unter den Nebenbedingungen l i K D 0 i 1 p displaystyle begin aligned text Maximiere amp q lambda mu amp text unter den Nebenbedingungen amp lambda i succcurlyeq K D 0 amp i 1 dotsc p end aligned nbsp Dabei ist K D displaystyle K D nbsp der duale Kegel von K displaystyle K nbsp Alternative Formulierungen fassen alle Ungleichungsrestriktionen und Gleichheitsrestriktionen zusammen g x g 1 x g p x T h x h 1 x h j x T K K 1 K p 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 nbsp Dies fuhrt zu einer kompakteren Schreibweise die ohne Summenzeichen und Indizes auskommt und daher fur theoretische Betrachtungen bevorzugt wird Alternativ wird auch die Forderung nach einem echten Kegel abgeschwacht 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 K h x 0 displaystyle g x in K h x 0 nbsp zu fordern definiert man einen Kegel K K 0 displaystyle K K times 0 nbsp Dann gilt g x h x K displaystyle g x h x in K nbsp genau dann wenn g x K h x 0 displaystyle g x in K h x 0 nbsp Fur 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 l m inf x X L x l m displaystyle q lambda mu inf x in X L x lambda mu nbsp bzw wenn nur eine duale Variable verwendet wird von der Form q l inf x X L x l displaystyle q lambda inf x in X L x lambda nbsp Primales Problem Lagrange Funktion Duales ProblemMinimiere f x unter den Nebenbedingungen g x K 0 h x 0 x X displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g x preccurlyeq K 0 amp h x 0 amp x in X amp end aligned nbsp L x l m f x l g x 1 m h x 2 displaystyle L x lambda mu f x langle lambda g x rangle 1 langle mu h x rangle 2 nbsp Maximiere q l m unter den Nebenbedingungen l K D 0 displaystyle begin aligned text Maximiere amp q lambda mu amp text unter den Nebenbedingungen amp lambda succcurlyeq K D 0 end aligned nbsp Minimiere f x unter den Nebenbedingungen g x K h x 0 x X displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g x in K amp h x 0 amp x in X amp end aligned nbsp L x l m f x l g x 1 m h x 2 displaystyle L x lambda mu f x langle lambda g x rangle 1 langle mu h x rangle 2 nbsp Maximiere q l m unter den Nebenbedingungen l K D displaystyle begin aligned text Maximiere amp q lambda mu amp text unter den Nebenbedingungen amp lambda in K D end aligned nbsp Minimiere f x unter den Nebenbedingungen g x K x X displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g x in K amp x in X amp end aligned nbsp L x l f x l g x 1 displaystyle L x lambda f x langle lambda g x rangle 1 nbsp Maximiere q l unter den Nebenbedingungen l K D displaystyle begin aligned text Maximiere amp q lambda amp text unter den Nebenbedingungen amp lambda in K D end aligned nbsp Dabei ist f V 0 R displaystyle f V 0 mapsto mathbb R nbsp die Zielfunktion g V 0 V 1 displaystyle g V 0 mapsto V 1 nbsp wobei auf V 1 displaystyle V 1 nbsp ein Kegel K displaystyle K nbsp ausgezeichnet ist der im ersten Fall ein echter Kegel ist im zweiten und dritten Fall ein konvexer Kegel ist Es ist h V 0 V 2 displaystyle h V 0 mapsto V 2 nbsp und l V 1 m V 2 displaystyle lambda in V 1 mu in V 2 nbsp Formulierung fur normierte Raume Bearbeiten Fur Probleme mit Abbildungen zwischen reellen normierten Vektorraumen ist zu beachten dass kein Skalarprodukt definiert ist Man wahlt stattdessen die duale Paarung Dementsprechend sind die dualen Variablen aus dem Dualraum des Vektorraumes Ist ein Problem der Form Minimiere f x unter den Nebenbedingungen g x K h x 0 x X displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g x in K amp h x 0 amp x in X amp end aligned nbsp gegeben wobei f V 0 R displaystyle f V 0 mapsto mathbb R nbsp die Zielfunktion g i V 0 V 1 displaystyle g i V 0 mapsto V 1 nbsp die Ungleichungsrestriktionsfunktionen und h j V 0 V 2 displaystyle h j V 0 mapsto V 2 nbsp die Gleichungsrestriktionsfunktion sind K displaystyle K nbsp sei ein Ordnungskegel auf V 1 displaystyle V 1 nbsp und es seien V 0 V 1 V 2 displaystyle V 0 V 1 V 2 nbsp Banachraume Die Lagrange Funktion lautet dann L x u v f x u g x v h x displaystyle L x u v f x u g x v h x nbsp Dabei ist u displaystyle u nbsp aus dem Dualraum V 1 displaystyle V 1 nbsp und v displaystyle v nbsp aus dem Dualraum V 2 displaystyle V 2 nbsp Die duale Funktion ist dann wieder q u v inf x X L x u v displaystyle q u v inf x in X L x u v nbsp und damit lautet das duale Problem Maximiere q u v unter den Nebenbedingungen u K displaystyle begin aligned text Maximiere amp q u v amp text unter den Nebenbedingungen amp u in K end aligned nbsp Dabei ist K displaystyle K nbsp der duale Kegel der in diesem Fall aber eine Teilmenge von V 1 displaystyle V 1 nbsp ist Formulierungen fur alternative Problemstellungen laufen analog zu den Problemen fur Abbildungen zwischen Hilbertraumen Die duale Paarung ersetzt jeweils das Skalarprodukt die dualen Variablen befinden sich im Dualraum Schwache und starke Dualitat Bearbeiten Die schwache Dualitat gilt auch fur die beiden allgemeineren Formulierungen Fur den Beweis in der Hilbertraumformulierung nutzt man aus dass a b 0 displaystyle langle a b rangle leq 0 nbsp ist wenn a K D 0 displaystyle a succcurlyeq K D 0 nbsp und b K displaystyle b preccurlyeq K nbsp gilt fur Ordnungskegel erhalt man a K D b K a b 0 displaystyle a in K D b in K implies langle a b rangle leq 0 nbsp In normierten Raumen gelten analoge Aussagen mit dem Unterschied dass a displaystyle a nbsp ein Element des Dualraumes ist Gilt a K b K displaystyle a in K b in K nbsp so folgt a b 0 displaystyle a b leq 0 nbsp Die starke Dualitat wird in den allgemeineren Fallen identisch zum gewohnlichen Fall definiert Auch im verallgemeinerten Fall existieren Regularitatsvoraussetzungen wie die Slater Bedingung die starke Dualitat garantieren Literatur BearbeitenFlorian 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 Abgerufen von https de wikipedia org w index php title Lagrange Dualitat amp oldid 238447485
