Lagrange Multiplier Demystified

Have you ever wondered why we use the Lagrange multiplier to solve constrained optimization problems?

Is it just a clever technique?

ponieważ jest bardzo łatwy w użyciu, uczymy się go jak podstawowej arytmetyki, ćwicząc go, dopóki nie będziemy mogli zrobić tego na pamięć.

ale czy zastanawialiście się kiedyś dlaczego to działa? Czy to zawsze działa? Jeśli nie, to dlaczego?

Jeśli chcesz poznać odpowiedzi na te pytania, jesteś we właściwym miejscu.

ja ci to wytłumaczę.

przykładowy problem z optymalizacją z ograniczeniami

Jeśli nie wiesz, czym są ograniczone optymalizacje, napisałem artykuł, który to wyjaśnia. W przeciwnym razie czytaj dalej.

Załóżmy, że mamy górę, która wygląda jak poniżej:

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:

oznacza to, że krawędź erupcji jest podana w następujący sposób:

więc krawędź wygląda tak.

przypuśćmy, że chcemy poznać najwyższą pozycję erupcji na tej górze.

oznacza to, że Najwyższa pozycja musi znajdować się na linii krawędzi erupcji, którą możemy wyrazić w następujący sposób:

Dowolna lokalizacja (x, y) spełniający g(x, y)=0 znajduje się na krawędzi erupcji.

dlatego problemem z optymalizacją jest znalezienie maksimumf(x, y) spełniającegog(x, y) = 0.

intuicja o tym, jak rozwiązać problem ograniczonej optymalizacji

intuicyjnie wiemy, że maksymalna wysokość erupcji jest wokół miejsca, w którym wskazuje niebieska strzałka.

szukamy najwyższej linii konturu, która dotyka krawędzi erupcji.

zdefiniujmy równanie linii konturu:

f(x, y) = H

H jest wartością stałą określającą wysokość konturu.

dla danej wartości H istnieje zestaw(x, y) wartości spełniającychf(x, y) = H.

gradient f(x, y) wskazuje kierunek, w którym rośnie wysokość, który jest prostopadły do linii konturu.

The gradient is a vector of partial derivatives.

Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.

najwyższa linia konturu, która dotyka krawędzi erupcji, musi mieć gradientf(x, y) równolegle do gradientg(x, y).

Jeśli gradient linii konturu nie jest równoległy do gradientu krawędzi erupcji, pojawi się pewien obszar erupcji, który jest znajduje się wyżej niż linia konturu.

musimy znaleźć taki punkt(x, y) gdzie gradientf(x, y) jest równoległy do gradientug(x, y).

mnożnik Lagrange 'a i Lagrangian’ a

umieśćmy nasz cel we wzorze matematycznym.

gradientf(x, y) I gradientg(x, y) powinny być równoległe, ale mogą mieć inny rozmiar i kierunek.

grad f(x, y) = λ grad g(x, y)

Tenλ jest nazywany mnożnikiem Lagrange 'a od nazwiska matematyka, który wprowadził mechanikę Lagrange’ a w 1788 roku.

na tym etapie nie znamy wartości λ, które może być coś w stylu 2.5, -1, lub inaczej. Oznacza to po prostu fakt, że dwa gradienty muszą być równoległe.

możemy zmienić równanie w następujący sposób:

grad { f(x, y) - λ g(x, y) } = 0

zero oznacza tutaj wektor z zerami: (0,0).

i nazywamy wnętrze nawiasów klamrowych LagrangianemL.

L = f(x, y) - λ g(x, y)

więc mówimy, że wymagany warunek jest następujący.

grad L = 0

gradient Lagrangiana daje nam dwa równania.

ale mamy Trzy niewiadomexy Iλ. Jak możemy rozwiązać te równania?

właściwie mamy jeszcze jedno równanie, które jest g(x, y) = 0.

tak więc, możemy rozwiązać trzy równania, aby znaleźć najwyższą lokalizację (x, y), która spełnia ograniczenie.

problem staje się teraz ćwiczeniem arytmetycznym.

odpowiedź brzmi f(x, y) = 2 where x = 1 and y = 1.

możesz zweryfikować wartości za pomocą równań.

równieżλ = -4/5, co oznacza, że te gradienty są w przeciwnych kierunkach, zgodnie z oczekiwaniami.

ogólnie rzecz biorąc, mnożnik Lagrange ’ a jest przydatny do rozwiązywania problemów związanych z optymalizacją ograniczeń.

znajdujemy punkt(x, y) gdzie gradient funkcji, którą optymalizujemy i gradient funkcji ograniczającej jest równoległy przy użyciu mnożnikaλ.

w podsumowaniu wykonaliśmy następujące kroki:

• Zidentyfikuj funkcję, aby zoptymalizować (zmaksymalizować lub zminimalizować):f(x, y)
• Zidentyfikuj funkcję dla ograniczenia: g(x, y) = 0
• Zdefiniuj LagrangianL = f(x, y) - λ g(x, y)
• Rozwiążgrad L = 0 spełnianie ograniczenia

jest tak mechaniczne jak powyżej i teraz wiesz, dlaczego to działa.

ale jest jeszcze kilka rzeczy do omówienia.

kiedy to nie działa

zrobiłem kilka założeń wyjaśniając mnożnik Lagrange ’ a.

przede wszystkim założyłem, że wszystkie funkcje mają gradienty (pierwsze pochodne), co oznacza, że funkcje f(x, y)I g(x, y) są ciągłe i płynne.

Po Drugie, zakładam również, że f(x, y) ma drugie pochodne, dzięki czemu możemy sprawdzić, czy rozwiązanie (x, y) jest w rzeczywistości maksimum, czy nie.

te dwa założenia są prawdziwe w tym przykładzie, ale w rzeczywistych problemach powinieneś to sprawdzić, aby móc użyć mnożnika Lagrange ’ a do rozwiązania problemu optymalizacji ograniczeń.

Po Trzecie, uprościłem pytanie tak, że musimy zająć się tylko jednym maksimum.

innymi słowy, kształt góry jest zdefiniowany w taki sposób, że istnieje tylko jedno rozwiązanie problemu ograniczonej optymalizacji.

w rzeczywistych problemach góra może mieć bardziej skomplikowane kształty z wieloma szczytami i dolinami.

w takim przypadku musielibyśmy poradzić sobie z globalnym problemem optymalizacji (tj.

zamiast tego, przykład w tym artykule dotyczy tylko jednego lokalnego maksimum, które jest również maksimum globalnym.

mam nadzieję, że Twoje zrozumienie mnożnika Lagrange ’ a jest teraz optymalne.