Understanding why it works
Have you ever wondered why we use the Lagrange multiplier to solve constrained optimization problems?
Is it just a clever technique?
Da es sehr einfach zu bedienen ist, lernen wir es wie eine grundlegende Arithmetik, indem wir es üben, bis wir es auswendig können.
Aber haben Sie sich jemals gefragt, warum es funktioniert? Funktioniert es immer? Wenn nicht, warum nicht?
Wenn Sie die Antworten auf diese Fragen wissen möchten, sind Sie hier richtig.
Ich werde es für Sie entmystifizieren.
Ein Beispiel für ein Problem mit eingeschränkter Optimierung
Falls Sie nicht wissen, was eingeschränkte Optimierungen sind, habe ich einen Artikel geschrieben, der es erklärt. Ansonsten lesen Sie bitte weiter.
Angenommen, wir haben einen Berg, der wie folgt aussieht:
The height of a location (x, y) is given as follows (in kilometers):
Further suppose, the mountain has an eruption:
From the top, it looks like below:
The eruption area is given as follows:
Dies bedeutet, dass der Rand des Ausbruchs wie folgt angegeben ist:
Die Kante sieht also so aus.
Angenommen, wir wollen die höchste Position des Ausbruchs auf diesem Berg wissen.
Dies bedeutet, dass die höchste Position auf der Randlinie des Ausbruchs liegen muss, was wir wie folgt ausdrücken können:
Beliebiger Ort (x, y) der g(x, y)=0 befindet sich am Rande des Ausbruchs.
Daher besteht das Problem der eingeschränkten Optimierung darin, das Maximum zu finden f(x, y) befriedigend g(x, y) = 0.
Intuition zur Lösung des Problems der eingeschränkten Optimierung
Intuitiv wissen wir, dass die maximale Höhe des Ausbruchs dort liegt, wo der blaue Pfeil anzeigt.
Wir suchen nach der höchsten Konturlinie, die den Rand des Ausbruchs berührt.
Definieren wir die Konturliniengleichung:
f(x, y) = H
H ist ein konstanter Wert, der die Höhe der Kontur angibt.
Für einen gegebenen Wert von H gibt es eine Menge von (x, y) Werten, die f(x, y) = H .
Der Gradient von f(x, y) gibt die Richtung an, in der die Höhe zunimmt, die senkrecht zur Konturlinie steht.
The gradient is a vector of partial derivatives.
Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.
Die höchste Konturlinie, die den Rand des Ausbruchs berührt, muss den Gradienten von f(x, y) parallel zum Gradienten von g(x, y).
Wenn der Gradient der Konturlinie nicht parallel zum Gradienten der Eruptionskante ist, gibt es einen Eruptionsbereich, der höher als die Konturlinie liegt.
Wir müssen also einen solchen Punkt finden (x, y) wo der Gradient von f(x, y) ist parallel zum Gradienten von g(x, y).
Der Lagrange-Multiplikator und der Lagrange-Multiplikator
Setzen wir unser Ziel in eine mathematische Formel.
Der Gradient von f(x, y) und der Gradient von g(x, y) sollten parallel sein, aber sie können unterschiedliche Größe und Richtung haben.
grad f(x, y) = λ grad g(x, y)
Dieser λ heißt Lagrange-Multiplikator nach dem Namen des Mathematikers, der 1788 die Lagrange-Mechanik einführte.
Zu diesem Zeitpunkt kennen wir den Wert von λ was so etwas wie 2.5 , -1 oder sonst sein könnte. Es bedeutet nur die Tatsache, dass die beiden Gradienten parallel sein müssen.
Wir können die Gleichung wie folgt neu anordnen:
grad { f(x, y) - λ g(x, y) } = 0
Die Null bedeutet hier den Vektor mit Nullen: (0,0).
Und wir nennen das Innere der geschweiften Klammern als Lagrange L .
L = f(x, y) - λ g(x, y)
Wir sagen also, dass Folgendes die erforderliche Bedingung ist.
grad L = 0
Der Gradient des Lagrange gibt uns zwei Gleichungen.
Aber wir haben drei Unbekannte xy und λ. Wie können wir diese Gleichungen lösen?
Tatsächlich haben wir eine weitere Gleichung, die g(x, y) = 0 .
Wir können also die drei Gleichungen lösen, um die höchste Position (x, y) zu finden, die die Einschränkung erfüllt.
Das Problem wird nun zu einer Rechenaufgabe.
Die Antwort lautet f(x, y) = 2 where x = 1 and y = 1.
Sie können die Werte mit den Gleichungen überprüfen.
Auch λ = -4/5 was bedeutet, dass diese Gradienten wie erwartet in die entgegengesetzten Richtungen verlaufen.
Alles in allem ist der Lagrange-Multiplikator nützlich, um Constraint-Optimierungsprobleme zu lösen.
Wir finden den Punkt (x, y) wo der Gradient der Funktion, die wir optimieren, und der Gradient der Einschränkungsfunktion parallel sind, indem wir den Multiplikator λ .
Zusammenfassend haben wir die folgenden Schritte ausgeführt:
- Identifizieren Sie die zu optimierende Funktion (maximieren oder minimieren):
f(x, y) - Identifizieren Sie die Funktion für die Einschränkung:
g(x, y) = 0 - Definiere den Lagrange
L = f(x, y) - λ g(x, y) - Löse
grad L = 0Befriedigung der Einschränkung
Es ist so mechanisch wie oben und Sie wissen jetzt, warum es funktioniert.
Aber es gibt noch ein paar Dinge zu erwähnen.
Wenn es nicht funktioniert
Ich habe einige Annahmen getroffen, als ich den Lagrange-Multiplikator erklärte.
Zunächst nahm ich an, dass alle Funktionen Gradienten haben (die ersten Ableitungen), was bedeutet, dass die Funktionen f(x, y) und g(x, y) kontinuierlich und glatt sind.
Zweitens gehe ich auch davon aus, dass f(x, y) die zweite Ableitung hat, damit wir überprüfen können, ob die Lösung (x, y) tatsächlich das Maximum ist oder nicht.
Diese beiden Annahmen sind in diesem Beispiel zutreffend, aber bei realen Problemen sollten Sie dies überprüfen, um den Lagrange-Multiplikator zur Lösung Ihres Einschränkungsoptimierungsproblems verwenden zu können.
Drittens habe ich die Frage so vereinfacht, dass wir uns nur mit einem Maximum befassen müssen.Mit anderen Worten, die Form des Berges ist so definiert, dass es nur eine Lösung für das eingeschränkte Optimierungsproblem gibt.
Bei realen Problemen könnte der Berg kompliziertere Formen mit mehreren Gipfeln und Tälern haben.
In einem solchen Fall müssten wir uns mit dem globalen Optimierungsproblem (dh mehreren lokalen Maxima) befassen.
Stattdessen behandelt das Beispiel in diesem Artikel nur ein lokales Maximum, das auch das globale Maximum ist.
Ich hoffe, dass Ihr Verständnis des Lagrange-Multiplikators jetzt optimal ist.