Lagrange-Multiplikator

Grundidee und Definition

Das Verfahren der Lagrange-Multiplikatoren ist eine Methode der mathematischen Optimierung. Es dient dazu, lokale Extremwerte einer Funktion in mehreren Veränderlichen zu finden, wenn zusätzlich eine oder mehrere Nebenbedingungen erfüllt sein müssen. Eine Nebenbedingung wird dabei als Gleichung beschrieben, zum Beispiel als Nullstelle einer Funktion: g(x,y)=0. Manche Darstellungen verwenden stattdessen g(x,y)=c mit einer Konstante c.

Die zentrale Idee ist geometrisch: Man betrachtet die Punkte, die die Nebenbedingung erfüllen. Im zweidimensionalen Fall bilden sie eine Kurve in der x-y-Ebene. Auf dieser Kurve soll eine Funktion f(x,y) maximiert oder minimiert werden. Ein Extremum unter der Nebenbedingung kann nur dort auftreten, wo die Kurve der Nebenbedingung eine Höhenlinie von f tangential berührt. Wäre dies nicht der Fall, könnte man sich auf der Kurve noch in eine Richtung bewegen und den Wert von f weiter vergrößern oder verkleinern, ohne die Nebenbedingung zu verletzen.

Diese Tangentenbedingung wird mit Gradienten beschrieben. Der Gradient einer Funktion ist der Vektor ihrer partiellen Ableitungen. Für f gilt ∇{x,y}f := (∂f/∂x, ∂f/∂y), für g gilt ∇{x,y}g := (∂g/∂x, ∂g/∂y). Am gesuchten Punkt müssen die Gradienten von f und g parallel sein, und der Gradient von g darf dort nicht verschwinden. Man schreibt deshalb ∇{x,y}f = -λ ∇{x,y}g. Die Zahl λ heißt Lagrange-Multiplikator. Sie ist nötig, weil die beiden Gradienten zwar parallel, aber unterschiedlich lang sein können.

Dazu bildet man die Lagrange-Funktion Λ(x,y,λ) := f(x,y)+λ·g(x,y). Ein möglicher Lösungspunkt der ursprünglichen Optimierungsaufgabe ist ein kritischer Punkt dieser Lagrange-Funktion, also ein Punkt mit ∇_{x,y,λ}Λ(x,y,λ)=0. Die Gleichungen nach x und y drücken die Parallelität der Gradienten aus; die Gleichung nach λ liefert wieder die Nebenbedingung g(x,y)=0. Das Verfahren liefert aber nur eine notwendige Bedingung: Nicht jeder kritische Punkt der Lagrange-Funktion ist tatsächlich ein Maximum oder Minimum. Punkte, an denen ∇g=0 ist, müssen gesondert untersucht werden, weil das Verfahren über sie keine Aussage macht.

Mehrere Nebenbedingungen

Das Verfahren lässt sich auf mehrere Veränderliche und mehrere Nebenbedingungen erweitern. Sei f eine reellwertige Funktion auf einer offenen Teilmenge U⊆R^n. Es gebe s voneinander unabhängige Nebenbedingungen g_k(x)=0, k=1,…,s. Unabhängig bedeutet hier: Die Gradienten der Nebenbedingungen sind an jedem zulässigen Punkt linear unabhängig. Insbesondere darf keiner dieser Gradienten verschwinden. Sind die Gradienten an einer Stelle doch linear abhängig, wird dieser Punkt zusätzlich in die Liste der kritischen Punkte aufgenommen.

Für mehrere Nebenbedingungen lautet die Lagrange-Funktion Λ(x,λ)=f(x)+∑_{k=1}^{s} λ_k g_k(x), wobei x=(x_1,…,x_n) und λ=(λ_1,…,λ_s) ist. Zu jeder Nebenbedingung gehört also ein eigener Lagrange-Multiplikator λ_k.

Aus der Bedingung für einen kritischen Punkt folgt für jede Koordinate x_i: ∂Λ/∂x_i=0, was äquivalent ist zu ∂f/∂x_i = -∑{k=1}^{s} λ_k ∂g_k/∂x_i. Damit entsteht ein lineares Gleichungssystem für die unbekannten Multiplikatoren λ_1,…,λ_s. Die Koeffizientenmatrix (∂g_k/∂x_i){1≤i≤n,1≤k≤s} hat unter der Unabhängigkeitsvoraussetzung maximalen Spaltenrang s und damit einen trivialen Nullraum. Falls das Gleichungssystem lösbar ist, sind die Lagrange-Multiplikatoren eindeutig bestimmt. Es kann jedoch auch innerhalb der Nebenbedingungen widersprüchlich sein und keine Lösung besitzen.

Auch bei mehreren Nebenbedingungen gilt: Ein kritischer Punkt der Lagrange-Funktion ist nur eine notwendige Bedingung für ein Extremum von f auf der Menge der zulässigen Punkte. Die tatsächlichen Extrema müssen aus der Liste der Kandidaten mit weiteren Mitteln bestimmt werden. Es ist daher falsch zu sagen, man müsse die Lagrange-Funktion „maximieren“. Die Lagrange-Funktion ist unbeschränkt und besitzt keine globalen Extrema; ihre kritischen Stellen zeigen nur mögliche Extrempunkte der ursprünglichen Zielfunktion unter den Nebenbedingungen an.

Nachweis von Extremstellen

Da die Methode der Lagrange-Multiplikatoren nur notwendige Bedingungen liefert, braucht man zusätzliche Kriterien, um zu entscheiden, ob ein gefundener Kandidat wirklich ein Maximum oder Minimum ist. Außerdem muss bestimmt werden, um welche Art von Extremstelle es sich handelt.

Ein übliches Verfahren besteht darin, die geränderte Hesse-Matrix zu bilden. Eine Hesse-Matrix enthält zweite partielle Ableitungen; bei Nebenbedingungen wird sie in angepasster, „geränderter“ Form verwendet. Anschließend untersucht man ihre Determinante oder bestimmte Unterdeterminanten. Dieser Ansatz führt jedoch nicht immer zu einer eindeutigen Aussage.

Alternativ kann man die Situation geometrisch oder durch eine Visualisierung untersuchen. Das ist besonders bei einfachen Beispielen hilfreich, etwa wenn die Nebenbedingung eine Kurve wie einen Kreis oder eine Ellipse beschreibt.

Beispiele mit einer Nebenbedingung

Ein einfaches Beispiel optimiert f(x,y)=x+y unter der Nebenbedingung x^2+y^2=1. Die Nebenbedingung beschreibt den Einheitskreis. Man setzt g(x,y)=x^2+y^2−1 und erhält ∇_{x,y}g=(2x,2y). Dieser Gradient verschwindet nur im Ursprung (0,0), der aber nicht auf dem Einheitskreis liegt. Deshalb kann die Methode angewendet werden.

Die Lagrange-Funktion lautet Λ(x,y,λ)=x+y+λx^2+λy^2−λ. Aus dΛ=0 folgt das Gleichungssystem 1+2λx=0, 1+2λy=0, x^2+y^2−1=0. Mit λ≠0 erhält man x=−1/(2λ)=y. Einsetzen in die Nebenbedingung ergibt 2λ^2=1, also λ=±1/√2=±√2/2. Die kritischen Punkte sind (√2/2,√2/2) und (−√2/2,−√2/2). Die Funktionswerte sind √2 beziehungsweise −√2. Damit liegt das Maximum bei (√2/2,√2/2), das Minimum bei (−√2/2,−√2/2).

Ein Anwendungsbeispiel betrachtet ein Grundstück in Form einer Ellipse mit Schwerpunkt im Ursprung und Achsen parallel zur x- und y-Achse. Die Fläche A=πab soll möglichst klein sein, und die Ellipse soll durch einen gegebenen Punkt (x,y) gehen. Die Nebenbedingung lautet x^2/a^2 + y^2/b^2 = 1. Die Lagrange-Funktion ist Λ(a,b,λ)=πab+λ(x^2/a^2+y^2/b^2−1), mit λ≠0 und unter der Voraussetzung a>x>0 und b>y>0. Aus den Ableitungen nach a, b und λ folgt nach Umformen die Lösung a=√2x, b=√2y und λ=πab=2πxy≠0. Der Gradient der Nebenbedingungsfunktion ∇g(a,b)=(-2x^2/a^3, -2y^2/b^3) verschwindet für x=y=0. Da der Punkt (0,0) nicht auf der Ellipse liegt, ist (a,b)=(√2x,√2y) das gesuchte Minimum. Im Einzelfall soll dies grafisch überprüft werden, weil die Lagrange-Multiplikatoren allein nur ein notwendiges Kriterium liefern.

Verschwindender Gradient

Ein wichtiges Beispiel zeigt, warum Punkte mit verschwindendem Gradienten der Nebenbedingung gesondert betrachtet werden müssen. Gegeben ist f: R_0^+ × R_0^+ → R mit f(x,y)=e^{-(x+y)}. Der Rand des Definitionsbereiches besteht aus den beiden positiven Koordinatenachsen und dem Ursprung. Er wird durch die Nebenbedingung g(x,y)=xy=0 beschrieben.

Die Lagrange-Funktion lautet Λ(x,y,λ)=e^{-(x+y)}+λxy. Aus ∇_{x,y,λ}Λ=0 erhält man −e^{-(x+y)}+λy=0, −e^{-(x+y)}+λx=0, xy=0. Die dritte Gleichung bedeutet x=0 oder y=0. Setzt man x=0 in die zweite Gleichung ein, entsteht −e^{-y}=0, was keine Lösung hat, weil die e-Funktion keine Nullstellen besitzt. Der Fall y=0 führt entsprechend ebenfalls zu einem Widerspruch. Die Lagrange-Multiplikatoren liefern also keine kritischen Punkte.

Nun prüft man den Gradienten der Nebenbedingung: ∇_{x,y}g=(y,x). Er verschwindet genau im Ursprung (0,0), und dieser Punkt erfüllt die Nebenbedingung. Deshalb muss er als Kandidat betrachtet werden. Tatsächlich ist f(0,0)=e^0=1, und für alle (x,y)≠(0,0) im Definitionsbereich gilt f(x,y)=e^{-(x+y)}<1. Der Ursprung ist also das globale Maximum.

Eine Variante zeigt zugleich die Grenze solcher Kandidatenlisten: Ersetzt man die Definitionsbereiche von f und g durch R×R, erhält man denselben einzigen kritischen Punkt, aber der Ursprung ist dann kein globales und auch kein lokales Maximum von f. Zum Beispiel divergiert die Funktion im 3. Quadranten. In diesem Fall besitzt f keine lokalen Maxima oder Minima.

Physik und Verallgemeinerungen

In der Physik spielen Lagrange-Multiplikatoren besonders in der klassischen Mechanik eine Rolle. Lagrange führte sie um das Jahr 1777 ein. Im Lagrange-Formalismus werden Bewegungsgleichungen mit Hilfe der Euler-Lagrange-Gleichung aus der Bedingung gewonnen, dass die Wirkung ein Extremum annimmt. Eine physikalische Zwangsbedingung, die die Bewegung einschränkt, erscheint dabei als Nebenbedingung. Der zugehörige Lagrange-Multiplikator steht in engem Zusammenhang mit der Zwangskraft, die das Objekt zur Einhaltung der Zwangsbedingung bringt.

Das Beispiel im Artikel betrachtet eine freie Punktmasse m, die sich in zwei Dimensionen auf einer Bahn mit konstantem Radius R bewegt. Die Lagrange-Funktion, also hier die kinetische Energie in Polarkoordinaten, lautet L=1/2 m(ṙ^2+r^2 φ̇^2). Die Zwangsbedingung ist g=r−R=0, und die neue Lagrange-Funktion lautet L′=L+λg. Für die radiale Koordinate ergibt die Euler-Lagrange-Gleichung m r̈ − mr φ̇^2 − λ = 0. Mit r̈=0, r=R und φ̇=ω folgt λ=−mRω^2. Dies entspricht der in Polarkoordinaten formulierten Zentripetalkraft, die die Punktmasse auf der Kreisbahn hält.

Verallgemeinerungen der Lagrange-Multiplikatoren sind die Karush-Kuhn-Tucker-Bedingungen und die Fritz-John-Bedingungen. Sie behandeln Nebenbedingungen, die auch durch Ungleichungen beschrieben werden, und sind wichtig in der nichtlinearen Optimierung. Für konvexe Optimierungsprobleme, bei denen die Funktionen nicht stetig differenzierbar sind, gibt es außerdem Sattelpunktkriterien der Lagrange-Funktion.