Beispiel 1
Betrachte die quadratische Zielfunktion \(f(x) = -(x-20)^2+400\) und folgende Optimierungsaufgabe
\(\begin{array}{ll}&f(x)\to_x \max,\\ \mbox{unter der Nebenbedingung:}&g(x)=10-x=0. \end{array}\)
Zu beachten: Die Nebenbedingung ist in der Form \(g(x)=0\) gegeben. Das ist
für den weiteren Lagrange-Formalismus, wie er hier dargestellt ist,
wichtig. Gegebenenfalls muss die Nebenbedingung in diese Form umgewandelt
werden.
Das ist offensichtlich ein sehr einfaches Beispiel und die optimale Lösung
ist natürlich \(x^*=10\),
mit dem optimalen Zielfunktionswert \(f(x^*=10)=-10^2+400=300\), siehe die
nebenstehende Illustration.
Aber gehen wir die Idee des Lagrange-Formalismus anhand dieses illustrativen Beispiels Schritt für Schritt durch:
-
Das unbeschränkte Maximum der Funktion \(f(x)\) ermittelt
sich durch die Bedingung erster Ordnung
\(\displaystyle{\frac{\partial f}{\partial x}}(x)=-2(x-20)=0\), woraus \(x^*=20\) folgt.
In der nebenstehenden Abbildung ist dieses unbeschränkte Maximum als schwarz-strichlierte Linie eingezeichnet.
Die Bedingung zweiter Ordnung für ein Maximum ist in \(x^*=20\) erfüllt, \(\displaystyle{\frac{\partial^2 f}{\partial x^2}}(x)=-2<0\), diese Lösung ist nicht im Einklang mit der Nebenbedingung \(x=10\).
Bei \(x=10\) ist die Steigung von \(f\) positiv, d.h., die simple Gradienten-Methode, die im unbeschränkten Fall zum Ziel führt, hilft hier nicht. -
Die Lagrange-Funktion stellt man nun auf, indem man die
Dimension des Problems um eins erhöht (weil das Problem eine
Nebenbedingung hat) und zur Zielfunktion einen Zusatzterm der Form
\(\lambda g(x)\)
addiert. Die Variable \(\lambda\) ist dabei eine neue, freie Variable.
Wir erhalten damit die Lagrange-Funktion als
\(L(\lambda,x)=f(x)+\lambda g(x)=-(x-20)^2+400+\lambda (10-x)\). -
Die interaktive, graphische Darstellung (siehe nebenan)
macht klar, wie die ursprüngliche Zielfunktion in der Lagrange-Funktion
verändert wird.
Die Lagrange-Funktion kippt die Zielfunktion. Drehpunkt ist jener Punkt, bei dem die Nebenbedingung erfüllt ist, \(g(x)=0\) gilt. Wie man aus der Lagrange-Funktion sehen kann, stimmt - unabhängig vom gewählten \(\lambda\) - bei \(g(x)=0\) der Funktionswert der Lagrange-Funktion mit dem der Zielfunktion überein.
-
Einfach ausprobieren! Mit dem Slider lassen sich
unterschiedliche Werte für \(\lambda\) einstellen.
Je größer \(\lambda\), desto weiter wird die Zielfunktion im Uhrzeigersinn gekippt. Weil sich nun die Steigung der Funktion je nach \(\lambda\) ändert, liegt auch das unbeschränkte Maximum bezüglich \(x\) je nach Wahl von \(\lambda\) an unterschiedlichen Stellen - in der interaktiven Graphik als \(x^*(\lambda)\) bezeichnet. Wählt man den Lagrange-Multiplikator richtig, (im Beispiel ist das \(\lambda=20\)), dann ist die Zielfunktion gerade so weit nach rechts gekippt, dass das unbeschränkte Maximum der Lagrange-Funktion genau dort zu liegen kommt, wo die Nebenbedingung gerade erfüllt ist. - Welches ist das richtige \(\bf{\lambda}\)? Es gibt zwei Wege, diese Frage zu beantworten.
- Betrachten wir obige Lagrange-Funktion. Wenn \(x\) die Nebenbedingung erfüllt, dann gilt \(g(x)=0\) und der Term, welcher den Lagrange-Multiplikator enthält, verschwindet. D.h., in so einem Punkt gilt \(L(\lambda,x)=f(x)\) und im Speziellen gilt dort \(\displaystyle{\frac{\partial L}{\partial \lambda}}(\lambda,x)=0\). Diese Bedingung kann als notwendige Bedingung für das richtige \(\lambda\) herangezogen werden.
- Die beiden Abbildungen rechts zeigen gut, dass das gesuchte Optimum \(\lambda^*,x^*\) in einem Sattelpunkt von \(L(\lambda,x)\) liegt. Die grünen Linien verbinden jene Punkte \(x^*(\lambda)\), an denen \(L(\lambda,x)\) für gegebenes \(\lambda\) ein Maximum annimmt. Es ist deutlich zu sehen, dass die Nebenbedingung \(g(x)=0\) genau für jenes \(\lambda\) hält, wo \(f(x^*(\lambda))\) ein Minimum annimmt. Da in einem Sattelpunkt der Gradient von \(L\) gleich 0 sein muss, folgt wieder die notwendige Bedingung \(\displaystyle{\frac{\partial L}{\partial \lambda}}(\lambda,x)=0\).
- Notwendige Optimalitätsbedingungen erster Ordnung sind dann
\(\begin{array}{rcl} \displaystyle{\frac{\partial L}{\partial \lambda}}(\lambda,x)&=&0,\\ \displaystyle{\frac{\partial L}{\partial x}}(\lambda,x)&=&0. \end{array}\)
Diese Bedingung ist identisch mit der notwendigen Bedingung erster Ordnung für einen lokalen Extremwert! D.h., nach der Erweiterung der Dimension des Problems durch die Einführung des Lagrange-Multiplikators haben wir aus einem eindimensionalen Optimierungsproblem mit Gleichheitsnebenbedingung ein zweidimensionales Problem gemacht, in dem wir einen Sattelpunkt suchen.
- Hinreichende Bedingungen für das Optimum werden hier nicht näher diskutiert, weil es auf dieser Seite um die Vermittlung von Intuition geht, wie die Mechanik hinter dem Lagrange-Ansatz funktioniert.