Optymalizacja, jeden z elementarnych problemów fizyki matematycznej, ekonomii, inżynierii i wielu innych dziedzin matematyki stosowanej, jest problemem znalezienia maksymalnej lub minimalnej wartości funkcji, zwanej funkcją celu, a także wartości zmiennych wejściowych, przy których ta wartość optymalna występuje. W elementarnym rachunku jednej zmiennej jest to bardzo prosty problem, który sprowadza się do znalezienia wartości x, dla których df/dx wynosi zero.
Problemy optymalizacji wielozmiennej są bardziej skomplikowane, ponieważ możemy nakładać ograniczenia. Rozważamy ograniczenia, które mogą być wyrażone w postaci g(x,y,z)=c dla pewnej funkcji g i stałej c. Nazywamy je ograniczeniami równościowymi, a zbiór punktów spełniających te ograniczenia nazywamy zbiorem wykonalnym, który oznaczamy przez S. Na przykład, jeśli mamy znaleźć maksymalną wartość f(x,y) na okręgu jednostkowym, to g(x,y)=x²+y², ponieważ okrąg jednostkowy jest określony przez x²+y²=1.
Standardową techniką rozwiązywania tego typu problemów jest metoda mnożników Lagrange’a. W tym artykule wyprowadzę tę metodę i podam kilka demonstracji jej zastosowania.
Motywacja i wyprowadzenie
Funkcja f ma ekstremum lokalne (maksimum lub minimum) w punkcie P, gdy pochodna cząstkowa f jest równa zero dla każdej ze zmiennych niezależnych i gdy punkt ten nie jest punktem siodłowym (sytuacja, którą nie będziemy się tutaj zajmować). Możemy to zapisać w postaci zwartej jako ∇f=0, gdzie ∇ oznacza operator gradientu:
W optymalizacji ograniczonej, jednak tylko dlatego, że f ma lokalne maksimum lub minimum w punkcie na zbiorze wykonalnym, nie wynika z tego, że f przyjmuje optymalną wartość na zbiorze wykonalnym w tym punkcie.
Jako przykład, rozważmy następujący problem optymalizacyjny:
Wypisując gradient, możemy zobaczyć, że f ma lokalne minimum, gdy x=0 i y=1:
Ponadto, f(0,1)=0, ale f(0,-1)=-4, więc chociaż (0,1) jest lokalnym minimum f(x,y), to nie jest minimum f(x,y) na okręgu jednostkowym.
Jako inny przykład, zmaksymalizujmy f(x,y)=y na okręgu jednostkowym. Gradient f(x,y)=y jest wektorem stałym, więc f(x,y) nie ma lokalnych maksimów ani minimów, ale na okręgu jednostkowym f ma maksimum o wartości 1, występujące w punkcie (0,1).
Powodem tego niepowodzenia jest to, że gradient mierzy szybkość zmiany f(x,y,z) w odniesieniu do pozycji w przestrzeni trójwymiarowej, ale my chcemy mierzyć szybkość zmiany f(x,y,z) w odniesieniu do pozycji w zbiorze wykonalnym. Dla problemu trójwymiarowego, S będzie albo krzywą albo powierzchnią, i ogólnie dla problemów z n zmiennymi, S będzie hiperpowierzchnią o wymiarze ściśle mniejszym niż n.
Najbardziej naturalnym podejściem jest rozważenie krzywych w S. Niech P będzie punktem w S, dla którego f(P) przyjmuje lokalnie optymalną wartość w S, ale ∇f(P) niekoniecznie jest równa zero, i niech r(t) będzie parametryzacją każdej krzywej w S, która przechodzi przez P, czyli:
Jeśli S jest krzywą, to r(t) jest po prostu parametryzacją S. Ponadto, niech r(T)=P, r′(T)≠0, i niech h(t) = f(r(t)) tak, że h′(T)=0. Rozwińmy h′(t) korzystając z reguły łańcuchowej:
Ponieważ r(t) jest zawsze w S, wektor prędkości r′(t) musi być zawsze styczny do powierzchni lub krzywej S, ponieważ gdyby r′(t) miał składową prostopadłą do powierzchni, czyli skierowaną na zewnątrz od powierzchni, to istniałyby punkty, w których r(t) opuszcza S. Ponieważ jest to prawdą dla każdej krzywej r(t) przechodzącej przez punkt P, wynika z tego, że ∇f(P) jest prostopadła do dowolnego wektora stycznego do powierzchni w punkcie P. Jeśli więc P jest punktem, w którym f przyjmuje wartość maksymalną lub minimalną względem położenia w S, to ∇f(P) jest prostopadła do S.
Prawda jest też odwrotna: Ponieważ r′(T) nigdy nie jest równe zero i zawsze jest równoległe do S, to jeśli ∇f(P) jest prostopadła do S, to h′(T)=∇f(P)∙r′(T)=0.
Jak jednak znaleźć punkty, w których ∇f jest prostopadła do S? Oto odpowiedź: Zbiór S jest zbiorem wszystkich punktów, w których g(x,y,z)=c, czyli S jest zbiorem poziomym g. Oznacza to, że ∇g jest prostopadłe do S dla wszystkich punktów w S, zatem ∇f i ∇g są równoległe w punktach w S, w których f przyjmuje wartości optymalne. Oznacza to, że f przyjmuje swoje wartości optymalne w S dokładnie wtedy, gdy ∇f=λ∇g dla pewnej stałej λ. Stała λ jest nazywana niezdeterminowanym mnożnikiem Lagrange’a i stąd pochodzi nazwa metody. Problem optymalizacji f może być teraz rozwiązany przez znalezienie czterech niewiadomych x, y, z i λ, które rozwiązują te cztery równania:
Ujmując to inaczej, naszym celem jest teraz optymalizacja funkcji f-λg względem x, y, i z bez ograniczeń poprzez znalezienie miejsca, w którym ∇(f-λg)=0.
A co jeśli jest więcej niż jedno ograniczenie? Załóżmy teraz, że musimy zoptymalizować f(x,y,x) z zastrzeżeniem g(x,y,z)=c i h(x,y,z)=d. Oto co zrobimy. Aby zoptymalizować f pod warunkiem g(x,y,z)=c, optymalizujemy f-λg bez ograniczenia, więc pierwsze ograniczenie jest załatwione przez zastąpienie f przez f-λg, i pozostaje zoptymalizować f-λg pod warunkiem h(x,y,z)=d. Jest to problem z tylko jednym ograniczeniem, więc po prostu dodajemy kolejny mnożnik Lagrange’a μ, a problemem jest teraz optymalizacja f-λg-μh bez ograniczenia.
Przyjrzyjrzyjmy się teraz kilku przykładom.
Maksymalne pole prostokąta
Dla danego obwodu, jakie jest największe możliwe pole prostokąta o tym obwodzie? Możemy to sformułować jako problem z mnożnikiem Lagrange’a. Jeśli szerokość i wysokość są równe x i y, to chcemy zmaksymalizować f(x,y)=xy dla g(x,y)=2x+2y=c. Otrzymany układ równań to:
Pierwsze dwa równania mówią nam od razu, że x=y, więc maksymalna powierzchnia występuje, gdy prostokąt jest kwadratem. Wstawiając to do trzeciego równania, widzimy, że x=y=c/4, więc maksymalne pole prostokąta o obwodzie c wynosi c²/16.
Zmodyfikowany problem Putnama
Konkurs matematyczny Putnama to konkurs w formie egzaminu, organizowany w grudniu każdego roku dla studentów studiów licencjackich. Studenci mają sześć godzin na rozwiązanie 12 niezwykle trudnych zadań. Egzamin jest tak trudny, że na 120 możliwych do zdobycia punktów, średni wynik w większości lat wynosi 0 lub 1. Dzisiaj przyjrzymy się zmodyfikowanej wersji (dla uproszczenia i w celu uniknięcia problemów z prawami autorskimi) problemu A3 z egzaminu 2018:
Pojawiają się dwa problemy. Pierwszym z nich jest to, że funkcja celu ma bardzo niepożądaną cechę: jest sumą cosinusów, a sumy funkcji trygonalnych mogą być trudne do poradzenia sobie z nimi. Drugim jest to, że nie ma sposobu, aby funkcja ograniczenia pojawiła się w sposób czysty i wyraźny w funkcji celu, nawet jeśli na pierwszy rzut oka mogłoby się wydawać, że powinno to być możliwe. Problemy Putnama często zawierają „pułapki” takie jak ta, gdzie możesz zostać zwabiony do marnowania czasu na podejście, które nie doprowadzi do rozwiązania, jeśli nie zatrzymasz się, aby pomyśleć o tym, co robisz. Jest to pułapka, która byłaby szczególnie niebezpieczna dla zawodnika z doświadczeniem w konkursach matematycznych w szkołach średnich, gdzie tożsamości trygonalne kładą silny nacisk.
Ale kiedy widzimy problem, który mówi „zmaksymalizuj f z zastrzeżeniem g=0”, powinniśmy natychmiast pomyśleć o mnożnikach Lagrange’a. Skonfigurujmy nasz układ równań:
Teraz możemy użyć naszych tożsamości trygonowych, aby ograniczenie pojawiło się jawnie. Przepisz układ równań używając wzoru na podwójny kąt:
Wynikiem jest:
Teraz anuluj funkcję sinus z każdej strony, i dodaj równania:
A to oznacza, że λ=0, więc zgodnie z równaniami mnożnika Lagrange’a oznacza to, że:
Więc w, x, y i z są całkowitymi wielokrotnościami liczby π/2. Dla parzystych całkowitych wielokrotności π/2, powiedzmy m=2k dla jakiejś liczby całkowitej k:
Ale jeśli m jest liczbą całkowitą nieparzystą, to cos(mπ/2)=0. Oznacza to, że mamy trzy możliwości, w jaki sposób możemy spełnić równanie ograniczenia. Po pierwsze, możemy ustawić w, x, y i z jako nieparzyste wielokrotności liczby całkowitej π/2, powiedzmy k, l, m i n, a następnie:
Pierwszy wiersz pokazuje, że równanie ograniczenia jest spełnione, a druga linia to wynik wprowadzenia tych wartości do funkcji celu, co daje nam -4.
Druga możliwość jest taka, że możemy ustawić dwie zmienne na nieparzyste liczby całkowite będące wielokrotnością π/2, powiedzmy k i l, a pozostałe dwie na parzyste liczby całkowite, powiedzmy 2m i 2n, gdzie m jest parzyste, a n nieparzyste. Wynikiem wstawienia tego do równania ograniczenia jest:
Więc równanie ograniczenia jest spełnione. Oto wynik wprowadzenia ich do funkcji celu:
Ostatnią opcją jest to, że możemy ustawić wszystkie zmienne na parzyste liczby całkowite będące wielokrotnością π/2, powiedzmy 2k, 2l, 2m i 2n, gdzie k i l są parzyste, a m i n są nieparzyste. Wynikiem wstawienia tego do równania ograniczenia jest:
Więc warunek jest spełniony. Teraz wstawiamy je do funkcji celu, aby otrzymać:
Więc odpowiedzią jest 4, co przypadkowo okazuje się być globalną maksymalną wartością funkcji celu.
Sprawdź ten inny artykuł, który napisałem, aby omówić inny problem Putnama.
Twierdzenie Thomsona
Teraz zamiast optymalizować funkcję, użyjmy metody mnożników Lagrange’a do optymalizacji funkcji: obiektu, który przyjmuje funkcję i zwraca liczbę. Kluczowym przykładem są całki definitywne. Ta ostatnia demonstracja pokaże, jak metoda mnożników Lagrange’a może być użyta do znalezienia funkcji, która minimalizuje wartość całki definitywnej.
Jako demonstrację rozważymy podstawowy fakt z elektrostatyki, badania systemów podlegających siłom elektrycznym w równowadze mechanicznej, tak że żaden z ładunków nie jest w ruchu. Pokażemy, że gdy przewodnik, czyli ciało, w którym ładunek elektryczny może się swobodnie poruszać, jest w równowadze z dowolnym układem sił elektrycznych, to wewnątrz ciała przewodnika nie ma pola elektrycznego. Jest to twierdzenie Thomsona. Twierdzenie to jest zwykle podawane w kategoriach podstawowego faktu fizycznego, że energia układu w stabilnej równowadze mechanicznej jest minimalna:
Twierdzenie Thomsona: Energia elektrostatyczna ciała przewodzącego o stałym rozmiarze i kształcie jest zminimalizowana, gdy ładunki są rozmieszczone w taki sposób, że potencjał ϕ jest stały w ciele tak, że E=-∇ϕ=0.
Pozwól ρ(r) być funkcją rozkładu ładunku, a ϕₑₓₜ potencjałem spowodowanym przez dowolne źródła zewnętrzne w stosunku do ciała przewodzącego. Całkowitą energię elektrostatyczną można wyrazić jako funkcję U z ρ(r):
Są to całki objętościowe po ciele przewodnika. Pierwsza całka jest całką podwójną przeprowadzoną najpierw przez współrzędne zagruntowane, a następnie przez współrzędne niezagruntowane. Chcemy zminimalizować U jako funkcję ρ(r) biorąc pod uwagę, że ładunek całkowity jest niezależny od rozkładu ładunku:
Na szczęście, metoda mnożników Lagrange’a działa dla funkcji z ograniczeniami. Wprowadzamy nieokreślony mnożnik Lagrange’a, a następnie zamiast optymalizacji ograniczonej na U, wykonujemy optymalizację nieograniczoną na następującej funkcji:
Przez analogię do pochodnych funkcji, celem jest znalezienie takiego rozkładu ładunku ρ, że gdy ρ zmienia się o niewielką zmianę δρ, zmiana I, δI, jest równa zeru:
To. nie jest całkiem pochodną, ponieważ δρ jest funkcją, a nie liczbą, więc nie ma sensu mówić o granicy, ponieważ δρ idzie do zera, ale podstawowa intuicja jest taka sama.
Zacznijmy od rozwinięcia U:
To może wyglądać źle, ale możemy to znacznie uprościć. Po pierwsze, ponieważ δρ jest bardzo małe, (δρ)² jest tak małe, że możemy je zignorować, więc przyjmijmy, że δρ(r)δρ(r′)=0. Następnie, zmieniając kolejność całkowania widzimy, że:
Widzimy też, że U pojawia się w rozwinięciu. To daje nam wystarczająco dużo, aby uprościć U:
Teraz możemy rozwinąć δI:
Teraz możemy wyfaktorować całkę po δρ(r):
Aby to było prawdziwe dla dowolnego wyboru wariancji δρ(r), człon w nawiasie musi być równy zero, więc:
Ale ta. całka to tylko potencjał w punkcie r wynikający z ładunków wewnątrz przewodnika, więc lewa strona tego równania daje całkowity potencjał w każdym punkcie r wewnątrz przewodnika, więc ρ(r) jest rozkładem, który sprawia, że całkowity potencjał wewnątrz przewodnika jest stały. To kończy dowód.
To byłoby również ważne, gdyby energia elektrostatyczna przewodnika była maksymalna, w tym przypadku przewodnik jest w równowadze niestabilnej. W praktyce nigdy nie spotyka się przewodników w stanie równowagi niestabilnej, ponieważ przypadkowy ruch termiczny elektronów w przewodniku szybko, rzędu 10-¹⁴ sekund dla przewodników metalowych, wyprowadza układ z równowagi niestabilnej i wprowadza go w stan równowagi stabilnej.
Dowód ten kończy dowód.