Lagrange-Multiplikator

Visualisierung der Methode der Lagrange-Multiplikatoren. Die rote Linie stellt die Menge dar, auf der $g(x,y)=c$ erfüllt ist. Die blauen Linien sind Höhenlinien $f(x,y)=d$ für verschiedene Werte von $d$. An dem Punkt, an dem $f$ unter der Nebenbedingung $g=c$ maximal ist, verläuft $g=c$ tangential zur Höhenlinie $f(x,y)=d_{1}$. Dort sind die Gradienten der Funktionen $f$ und $g$, dargestellt durch blaue bzw. rote Pfeile, kollinear.

Dasselbe Problem wie oben, wobei die Funktionswerte von $f$ auf der Höhenachse abgetragen sind.

Das Verfahren der Lagrange-Multiplikatoren (nach Joseph-Louis Lagrange) ist in der mathematischen Optimierung eine Methode, Optimierungsprobleme mit Nebenbedingungen umzuformulieren. Ein Optimierungsproblem mit Nebenbedingungen ist die Aufgabe, ein lokales Extremum einer Funktion in mehreren Veränderlichen mit einer oder mehreren Nebenbedingungen zu finden, wobei die Nebenbedingungen durch Setzen von Funktionen auf gegebene Werte definiert seien. Diese Methode führt eine neue unbekannte skalare Variable für jede Nebenbedingung ein, einen Lagrange-Multiplikator, und definiert eine Linearkombination, die die Multiplikatoren als Koeffizienten einbindet. Die Lösungen der ursprünglichen Optimierungsaufgabe können dann unter gewissen Voraussetzungen als kritische Punkte dieser sogenannten Lagrange-Funktion bestimmt werden.

Beschreibung

Zum Verständnis der Funktionsweise betrachten wir den zweidimensionalen Fall mit einer Nebenbedingung. Nehmen wir an, wir wollen eine Funktion $f(x,y)$ maximieren, wobei für eine Konstante $c$ eine Nebenbedingung $g(x,y)=c$ einzuhalten ist. Beim Verfolgen der Nebenbedingung $g=c$ berühren oder kreuzen wir Höhenlinien von $f$. Ein gemeinsamer Punkt $(x,y)$ der Nebenbedingung $g(x,y)=c$ und einer Höhenlinie $f(x,y)=d$ kann nur dann Lösung des Optimierungsproblems sein, wenn unsere Bewegung auf der Höhenlinie $g(x,y)=c$ tangential zu $f(x,y)=d$ verläuft: Andernfalls könnten wir durch Vorwärts- oder Rückwärtsbewegung auf der vorgegebenen $g$-Höhenlinie den Funktionswert von $f$ vergrößern oder verkleinern, ohne die Nebenbedingung zu verletzen.

Was wird hier betrachtet? Trajektorien? Isoklinen? Das Anfangsproblem ist nicht formuliert! Hier wird nichts optimiert! Höhenlinien für Temperaturen existieren nicht. Drucklinien schon! Was ist also die "Tangentenkurve" an die Isobare? Schlimm dieser Artikel! Es sollte komplett überarbeitet werden. Schreibe einen Artikel über Anwendung der Lagrangesche Multiplikatoren in der Optimierung.

Ein bekanntes Beispiel kann man den Wetterkarten mit ihren Höhenlinien für Temperaturen und Druck entnehmen. Die Extrema unter der Nebenbedingung treten dort auf, wo sich beim Überlagern der Karten Linien berühren. Geometrisch übersetzen wir die Tangentenbedingung, indem wir sagen, dass die Gradienten von $f$ und $g$ beim Maximum parallele Vektoren sind, wobei der Gradient von $g$ nicht verschwinden darf.

Wir suchen also Punkte $(x,y)$ mit $g(x,y)=c$, an denen $\nabla _{x,y}g\neq 0$ und

$\nabla _{x,y}f=-\lambda \nabla _{x,y}g$.

Dabei wurden die folgenden Abkürzungen, bzw. Definitionen für die zugehörigen Gradienten benutzt:

$\nabla _{x,y}f:=\left({\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}}\right)$

und

$\nabla _{x,y}g:=\left({\frac {\partial g}{\partial x}},{\frac {\partial g}{\partial y}}\right)$

Der konstante Lagrange-Multiplikator $\lambda$ wird dabei benötigt, weil die beiden Gradienten zwar parallel sein sollen, aber als Vektoren unterschiedlich lang sein können. Um alle genannten Bedingungen zu einer Gleichung zusammenzufassen, ist es nützlich, die folgende Lagrangefunktion zu verwenden:

$\Lambda (x,y,\lambda ):=f(x,y)+\lambda \cdot {\Big (}g(x,y)-c{\Big )}$

Die Lösung des oben beschriebenen Optimierungsproblems mit einer Nebenbedingung entspricht jetzt einem lokalen Extremum der Lagrangefunktion. Dieses Extremum kann über den Gradienten der Lagrangefunktion berechnet werden:

$\nabla _{x,y,\lambda }\Lambda (x,y,\lambda )=0.$

Die ersten beiden Komponenten dieser Gleichung entsprechen dabei der Forderung nach Parallelität der zwei ursprünglichen Gradienten und die dritte Komponente $\nabla _{\lambda }\Lambda (x,y,\lambda )=0$ ist identisch mit $g(x,y)=c$.

Punkte, bei denen der Gradient der Lagrangefunktion oder der Nebenbedingung $g$ verschwindet, werden auch kritische Punkte der Lagrangefunktion genannt. Letztere werden hinzugezogen, weil das Verfahren der Lagrange-Multiplikatoren über sie keine Aussage treffen kann und sie daher als mögliche Kandidaten für Extrema in Betracht kommen. Da im Allgemeinen nicht jeder kritische Punkt der Lagrangefunktion das ursprüngliche Optimierungsproblem löst, liefert dieses Verfahren nur eine notwendige Bedingung für die Lösung des Optimierungsproblems.

Beispiele

Darstellung eines Optimierungsproblems mit einer Nebenbedingung

Beispiel mit Nebenbedingung ohne verschwindenden Gradienten

In diesem Beispiel soll die Funktion $f(x,y)=x+y$ unter der Nebenbedingung $x^{2}+y^{2}=1$ optimiert werden. Die Nebenbedingung entspricht also dem Einheitskreis. Mit Hilfe der Grafik kann das Maximum bei $({\sqrt {2}}/2,{\sqrt {2}}/2)$ sehr leicht bestimmt werden. Das Minimum des Optimierungsproblems liegt bei $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$.

Zunächst überprüfen wir, an welchen Punkten des Einheitskreises der Gradient der Nebenbedingungsfunktion $g(x,y)=x^{2}+y^{2}$ verschwindet. Wir berechnen also

$\nabla _{x,y}g=(2x,2y)$

und sehen, dass dies nur im Ursprung gleich $(0,0)$ ist. Jedoch liegt dieser Punkt nicht auf dem Einheitskreis, erfüllt also nicht die Nebenbedingung und wird somit nicht in die Liste der kritischen Punkte aufgenommen.

Um die Methode der Lagrange-Multiplikatoren anwenden zu können, sei $g(x,y)-c=x^{2}+y^{2}-1$ und

$\Lambda (x,y,\lambda )=f(x,y)+\lambda (g(x,y)-c)=x+y+\lambda (x^{2}+y^{2}-1)=x+y+\lambda x^{2}+\lambda y^{2}-\lambda$.

Die Bedingung $d\Lambda =0$ ergibt die folgenden drei Gleichungen:

${\begin{aligned}{\frac {\partial \Lambda }{\partial x}}&=1+2\lambda x&&=0,\qquad {\text{(i)}}\\{\frac {\partial \Lambda }{\partial y}}&=1+2\lambda y&&=0,\qquad {\text{(ii)}}\\{\frac {\partial \Lambda }{\partial \lambda }}&=x^{2}+y^{2}-1&&=0.\qquad {\text{(iii)}}\end{aligned}}$

Die dritte Gleichung (iii) entspricht dabei wie immer der geforderten Nebenbedingung. Mit $\lambda \neq 0$ kann (i) nach $x$ aufgelöst werden. Dasselbe macht man für Gleichung (ii) und $y$. Man erhält somit $x=-1/(2\lambda )=y$. Wird das in (iii) eingesetzt, erhält man $2\lambda ^{2}=1$, also $\lambda =\pm 1/{\sqrt {2}}$. Die kritischen Punkte berechnen sich damit zu $({\sqrt {2}}/2,{\sqrt {2}}/2)$ und $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$. Die zu optimierende Funktion f hat an diesen zwei Punkten die Werte ${\sqrt {2}}$, bzw. $-{\sqrt {2}}$.

Beispiel mit Nebenbedingung mit verschwindendem Gradienten

Wir betrachten die Funktion $f:\mathbb {R} _{0}^{+}\times \mathbb {R} _{0}^{+}\to \mathbb {R}$ mit $f(x,y)=e^{-(x+y)}$. Untersucht man die Funktion nun auf Extrema, so kann man mithilfe des hinreichenden Kriteriums für lokale Extremstellen alle Extrema im Inneren des Definitionsbereiches bestimmen. Die Randextrema werden jedoch mithilfe des Lagrange-Multiplikator gefunden. Dabei bildet der Rand des Definitionsbereiches die Nebenbedingung. Hier sind es die beiden positiven Koordinatenachsen und der Ursprung. Wir finden also die Nebenbedingung $g:\mathbb {R} _{0}^{+}\times \mathbb {R} _{0}^{+}\to \mathbb {R}$ mit $g(x,y)=xy=c=0$.

Wir stellen zunächst die Lagrange-Funktion auf:

$\Lambda (x,y,\lambda )=f(x,y)+\lambda (g(x,y)-c)=e^{-(x+y)}+\lambda xy$

Die Gleichung

$\nabla _{x,y,\lambda }\Lambda =0$

führt uns auf das Gleichungssystem

${\begin{aligned}{\frac {\partial \Lambda }{\partial x}}&=-e^{-(x+y)}+\lambda y&&=0,\qquad {\text{(i)}}\\{\frac {\partial \Lambda }{\partial y}}&=-e^{-(x+y)}+\lambda x&&=0,\qquad {\text{(ii)}}\\{\frac {\partial \Lambda }{\partial \lambda }}&=xy&&=0.\qquad {\text{(iii)}}\end{aligned}}$

Die dritte Gleichung besagt, dass $x=0$ oder $y=0$. Angenommen es wäre $x=0$, dann führt dies – in die zweite Gleichung eingesetzt – auf einen Widerspruch, denn die Gleichung

$-e^{-y}=0$

hat keine Lösung, da die $e$-Funktion keine Nullstellen besitzt. Analog führt man den Fall $y=0$ mit der ersten Gleichung auf einen Widerspruch. Der Lagrange-Multiplikator liefert also keine kritischen Punkte.

Jedoch haben wir nicht überprüft, an welchen Stellen der Gradient der Nebenbedingung verschwindet. Es gilt

$\nabla _{x,y}g=(y,x)=(0,0)\Leftrightarrow (x,y)=(0,0)$

Im Ursprung verschwindet also der Gradient der Nebenbedingung, und dieser liegt auch auf dem Rand des Definitionsbereiches von $f$ (er erfüllt die Nebenbedingung). Wie oben beschrieben, müssen diese Punkte auch als Kandidaten für Extrema in Betracht gezogen werden. Und in der Tat ist $f(0,0)=e^{0}=1$ und $f(x,y)=e^{-(x+y)}<1$ für alle $(x,y)\neq (0,0)$. Der Ursprung ist also das globale Maximum der Funktion.

Das Vorhandensein von kritischen Punkten sagt jedoch nichts über das Vorhandensein von Extrema aus. Würde man in diesem Beispiel die Definitionsbereiche von $f$ und $g$ durch $\mathbb {R} \times \mathbb {R}$ ersetzen, so würde man zwar denselben einzigen kritischen Punkt erhalten, jedoch wäre der Ursprung kein globales (und auch kein lokales) Maximum von $f$ (z. B. divergiert die Funktion im 3. Quadranten). In der Tat besäße dieses $f$ keine lokalen Maxima oder Minima.

Mehrere Nebenbedingungen

Es sei $f$ eine in einer offenen Teilmenge $U\subseteq \mathbb {R} ^{n}$ definierte Funktion. Wir definieren $s$ voneinander unabhängige Nebenbedingungen $g_{k}(x)=0$, $k=1,\ldots ,s$. D. h. die Gradienten der Nebenbedingungen sind für jeden Punkt $x\in U$, mit $g_{k}(x)=0$ für alle $k=1,\ldots ,s$, linear unabhängig. Insbesondere bedeutet dies, dass keiner der Gradienten verschwindet. Sollten die Gradienten doch an einer Stelle linear abhängig sein, so wird dieser Punkt in die Liste der kritischen Punkte aufgenommen. Nun setzen wir

$\Lambda (x,\lambda )=f(x)+\sum _{k=1}^{s}\lambda _{k}g_{k}(x),$

wobei $x=(x_{1},\dots ,x_{n})$ und $\lambda =(\lambda _{1},\dots ,\lambda _{s})$ ist.

Wir schauen uns nun den kritischen Punkt von $\Lambda$ an

${\frac {\partial \Lambda }{\partial x_{i}}}=0,$

was äquivalent ist zu

${\frac {\partial f}{\partial x_{i}}}=-\sum _{k=1}^{s}\lambda _{k}{\frac {\partial g_{k}}{\partial x_{i}}}.$

Wir ermitteln die unbekannten Multiplikatoren $\lambda _{k}$ mit Hilfe unserer Nebenbedingungsgleichungen und haben damit einen kritischen Punkt (d. h. ${\frac {\partial \Lambda }{\partial x_{i}}}=0$) von $\Lambda$ gefunden. Dies ist eine notwendige Bedingung dafür, dass $f$ ein Extremum auf der Menge der Punkte, welche die Nebenbedingungen erfüllen, hat. D. h. auch hier müssen die Extrema aus der Liste der kritischen Punkte mit anderen Mitteln herausgefiltert werden.

Man beachte, dass es deshalb insbesondere falsch ist, davon zu sprechen, die "Lagrangefunktion zu maximieren". Die Lagrangefunktion ist unbeschränkt und besitzt deshalb keine globalen Extrema und kann somit nicht maximiert werden. Lediglich die kritischen Stellen der Lagrangefunktion geben Punkte an, an denen die Zielfunktion bezüglich der Nebenbedingungen möglicherweise ein Maximum annimmt.

Hinreichende Bedingungen

Dieses Verfahren liefert nur eine notwendige Bedingung für Extremstellen. Um die Extremstellen nachzuweisen und ihre Art zu bestimmen gibt es verschiedene Kriterien. Generell wird die geränderte Hesse-Matrix gebildet und deren Determinante bzw. bestimmte Unterdeterminanten berechnet. Dieser Ansatz führt aber nicht immer zu einer Aussage. Alternativ kann man auch auf eine Visualisierung bzw. geometrische Überlegungen zurückgreifen, um die Art der Extremstelle festzustellen.

Bedeutung der Lagrange-Multiplikatoren in der Physik

Die Bedeutung der Lagrange-Multiplikatoren in der Physik wird bei der Anwendung in der klassischen Mechanik sichtbar. Hierfür wurden sie von Lagrange auch (etwa 1777?) eingeführt. Die Bewegungsgleichungen der klassischen Mechanik lassen sich im Lagrange-Formalismus mit Hilfe der Euler-Lagrange-Gleichung aus der Bedingung gewinnen, dass die Wirkung - bei Variation der Koordinaten und ihrer Zeitableitungen unabhängig voneinander - ein Extremum annimmt. Eine physikalische Zwangsbedingung, die die Bewegung einschränkt, erscheint als Nebenbedingung des Extremums. Der Lagrange-Multiplikator, mit dem die Zwangsbedingung in die Lagrangefunktion eingefügt wird, stellt sich als die physikalische Zwangskraft heraus, mit der das durch die Bewegungsgleichung beschriebene Objekt zur Einhaltung der Zwangsbedingung gebracht wird. Das folgende Beispiel einer freien Punktmasse $m$, die sich in zwei Dimensionen auf einer Bahn mit konstantem Radius $R$ bewegt, macht dieses klar:

Lagrangefunktion (kinetische Energie in Polarkoordinaten):

$L={\frac {1}{2}}m\left({\dot {r}}^{2}+r^{2}{\dot {\varphi }}^{2}\right)$

Zwangsbedingung:

$g=r-R=0$

neue Lagrangefunktion:

$L^{\prime }=L+\lambda g$

Euler-Lagrange-Gleichung (hier nur für die radiale Koordinate formuliert, da die Zwangsbedingung von dieser abhängt; die Winkelkoordinate ergibt die Drehimpulserhaltung für diese Bewegung):

${\frac {d}{dt}}{\frac {\partial L^{\prime }}{\partial {\dot {r}}}}-{\frac {\partial L^{\prime }}{\partial r}}=0$

$m{\ddot {r}}-mr{\dot {\varphi }}^{2}-\lambda =0$

mit ${\ddot {r}}=0$ und $r=R$, sowie ${\dot {\varphi }}=\omega$ (Winkelgeschwindigkeit).

$\lambda =-mR\omega ^{2}$

Das entspricht der in Polarkoordinaten formulierten Zentripetalkraft, die die Punktmasse zur Bewegung auf eine Kreisbahn zwingt.

Verallgemeinerungen

Die Karush-Kuhn-Tucker-Bedingungen und die Fritz-John-Bedingungen sind eine Verallgemeinerung der Lagrange-Multiplikatoren für Nebenbedingungen, die auch durch Ungleichungen beschrieben werden. Beide spielen eine wichtige Rolle in der nichtlinearen Optimierung. Für konvexe Optimierungsprobleme, bei denen die Funktionen nicht stetig differenzierbar sind, gibt es außerdem die Sattelpunktkriterien der Lagrange-Funktion.

Literatur

• Otto Forster: Analysis 2. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0575-1. S.110ff
• Michael Sauer: Operations Research kompakt 1. Auflage, Oldenbourg, München 2009, ISBN 978-3-486-59082-1.
• Heinrich Rommelfanger: Mathematik für Wirtschaftswissenschaftler II Band 2 (2. Auflage, 1992), BI Wissenschaftsverlag , ISBN 9783860259818. S. 238ff

Weblinks

• Konzeptuelle Einleitung (englisch)
• Studienarbeit Lagrangeoptimierung (inklusive Beispielrechnung und Literaturverweisen; PDF; 474 kB)