Metoda Newtona w optymalizacji - Newton's method in optimization

Porównanie opadania gradientu (zielony) i metody Newtona (czerwony) w celu minimalizacji funkcji (z małymi krokami). Metoda Newtona wykorzystuje informacje o krzywiźnie (tj. druga pochodna), aby obrać bardziej bezpośrednią drogę.

W rachunku , metoda Newtona jest iteracyjna metoda celu znalezienia korzenie o różniczkowej funkcji F , które są do rozwiązania w równaniu F ( x ) = 0 . Jako taka metoda Newtona mogą być stosowane do pochodnej f ' o dwukrotnie różniczkowalną funkcją f znaleźć korzenie pochodnych (roztwory do F ' ( x ) = 0 ), znany również jako krytyczne punkty z F . Tymi rozwiązaniami mogą być minima, maksima lub punkty siodłowe; patrz rozdział "Kilka zmiennych" w punkcie Krytyczny (matematyka) oraz rozdział "Interpretacja geometryczna" w tym artykule. Ma to znaczenie w optymalizacji , której celem jest znalezienie (globalnych) minimów funkcji f .

Metoda Newtona

Głównym problemem optymalizacji jest minimalizacja funkcji. Rozważmy najpierw przypadek funkcji jednowymiarowych, tj. funkcji pojedynczej zmiennej rzeczywistej. Później rozważymy bardziej ogólny i bardziej praktyczny przypadek wielowymiarowy.

Mając podwójną różniczkowalną funkcję , staramy się rozwiązać problem optymalizacji ${\ Displaystyle f: \ mathbb {R} \ do \ mathbb {R}}$

${\ Displaystyle \ min _ {x \ w \ mathbb {R}} f (x).}$

Metoda Newtona próby rozwiązania tego problemu przez skonstruowanie sekwencję od początkowej przypuszczenie (punkt początkowy) , że zbiega się w kierunku do Minimizer o stosując sekwencję drugiego rzędu Taylor przybliżeń wokół iteruje. Drugiego rzędu rozwinięcie Taylora z f WOKÓł jest ${\ Displaystyle \ {x_ {k} \}}$${\displaystyle X_{0}\w \mathbb {R}}$${\displaystyle x_{*}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x_{k}}$

${\ Displaystyle f (x_ {k} + t) \ ok. f (x_ {k}) + f '(x_ {k}) t + {\ Frac {1} {2}} f ''(x_ {k}) t^{2}.}$

Kolejna iteracja jest zdefiniowana tak, aby zminimalizować to przybliżenie kwadratowe w i ustawienie . Jeśli druga pochodna jest dodatnia, przybliżenie kwadratowe jest funkcją wypukłą , a jej minimum można znaleźć, ustawiając pochodną na zero. Odkąd ${\displaystyle x_{k+1}}$${\displaystyle t}$${\ Displaystyle x_ {k + 1} = x_ {k} + t}$${\displaystyle t}$

${\ Displaystyle \ Displaystyle 0 = {\ Frac {\ rm {d}} {{\ rm {d}} t}} \ lewo (f (x_ {k}) + f '(x_ {k}) t + {\ frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

minimum jest osiągane dla

${\ Displaystyle t = - {\ Frac {f '(x_ {k})} {f ''(x_ {k})}}.}$

Składając wszystko razem, metoda Newtona wykonuje iterację

${\ Displaystyle x_ {k + 1} = x_ {k} + t = x_ {k} - {\ Frac {f '(x_ {k})} {f ''(x_ {k})}}.}$

Interpretacja geometryczna

Interpretacja geometryczna metody Newtona jest taka, że ​​w każdej iteracji sprowadza się to do dopasowania paraboli do wykresu o wartości próby , mającej takie samo nachylenie i krzywiznę jak wykres w tym punkcie, a następnie przejście do maksimum lub minimum tej paraboli (w wyższych wymiarach może to być również punkt siodłowy ), patrz poniżej. Zauważ, że jeśli zdarza się być funkcją kwadratową, a następnie dokładne ekstremum znajduje się w jednym etapie. ${\displaystyle f(x)}$${\displaystyle x_{k}}$${\displaystyle f}$

Wyższe wymiary

Powyższy iteracyjny schemat może być uogólnione do wymiarów zastępując pochodna z gradientem (inni autorzy stosują różne zapisu gradientu, łącznie ) i wzajemne drugiej pochodnej z odwrotności z Heskiego matrycy (inni autorzy stosują różne notację Heski, w tym ). W ten sposób otrzymujemy schemat iteracyjny ${\displaystyle d>1}$${\ Displaystyle f '(x) = \ nabla f (x) = g_ {f} (x) \ w \ mathbb {R} ^ {d}}$${\ Displaystyle f ''(x) = \ nabla ^ {2} f (x) = H_ {f} (x) \ w \ mathbb {R} ^ {d \ razy d}}$

${\ Displaystyle x_ {k + 1} = x_ {k} - [f ''(x_ {k})] ^ {-1} f” (x_ {k}), \ qquad k \ geq 0.}$

Często metoda Newtona jest modyfikowana, aby uwzględnić mały rozmiar kroku zamiast : ${\ Displaystyle 0<\gamma \leq 1}$${\ Displaystyle \ gamma = 1}$

${\ Displaystyle x_ {k + 1} = x_ {k} - \ gamma [f ''(x_ {k})] ^ {-1} f” (x_ {k}).}$

Jest to często wykonywane, aby zapewnić spełnienie warunków Wolfe'a lub znacznie prostszego i wydajniejszego warunku Armijo na każdym etapie metody. W przypadku stopni o rozmiarach innych niż 1, metoda ta jest często określana jako metoda zrelaksowanego lub wytłumionego Newtona.

Konwergencja

Jeśli f jest mocno wypukła funkcja Lipschitz z juty, i pod warunkiem, że znajduje się wystarczająco blisko aby sekwencja generowanych metodą Newtona, będą zbliżać się do (koniecznie unikalne) Minimizer z kwadratu szybko. To jest, ${\displaystyle x_{0}}$${\ Displaystyle x_ {*} = \ arg \ min f (x)}$${\displaystyle x_{0},x_{1},x_{2},\kropki}$${\displaystyle x_{*}}$${\displaystyle f}$

${\ Displaystyle \ | x_ {k + 1} -x_ {*} \ | \ leq {\ Frac {1} {2}} \ | x_ {k}-x_ {*} \ | ^ {2}, \ qquad \forall k\geq 0.}$

Obliczanie kierunku Newtona

Znalezienie odwrotności hessu w dużych wymiarach w celu obliczenia kierunku Newtona może być kosztowną operacją. W takich przypadkach, zamiast bezpośrednio odwracać hes, lepiej obliczyć wektor jako rozwiązanie układu równań liniowych${\ Displaystyle h = - (f ''(x_ {k})) ^ {-1} f '(x_ {k})}$${\ Displaystyle h}$

${\ Displaystyle [f ''(x_ {k})] h = - f '(x_ {k})}$

które można rozwiązać za pomocą różnych faktoryzacji lub w przybliżeniu (ale z dużą dokładnością) przy użyciu metod iteracyjnych . Wiele z tych metod ma zastosowanie tylko do niektórych typów równań, na przykład faktoryzacja Cholesky'ego i gradient sprzężony będą działać tylko wtedy, gdy jest dodatnią określoną macierzą. Chociaż może się to wydawać ograniczeniem, często jest to przydatny wskaźnik, że coś poszło nie tak; na przykład, jeśli podchodzi się do problemu minimalizacji, który nie jest określony dodatnio, iteracje zbiegają się do punktu siodłowego, a nie do minimum. ${\displaystyle f''(x_{k})}$${\displaystyle f''(x_{k})}$

Z drugiej strony, jeśli zostanie wykonana optymalizacja z ograniczeniami (na przykład z mnożnikami Lagrange'a ), problemem może być znalezienie punktu siodłowego, w którym to przypadku Hessian będzie symetryczny nieskończony, a rozwiązanie woli będzie musiało być wykonane za pomocą metoda, która będzie działać dla takich, jak wariant faktoryzacji Cholesky'ego lub sprzężona metoda rezydualna . ${\displaystyle x_{k+1}}$${\ Displaystyle LDL ^ {\ góra}}$

Istnieją również różne metody quasi-Newtona , w których przybliżenie hessu (lub jego odwrotność bezpośrednio) jest budowane na podstawie zmian w gradiencie.

Jeśli hesjan jest bliski macierzy nieodwracalnej , odwrócony hesjan może być numerycznie niestabilny, a rozwiązanie może się różnić. W tym przypadku w przeszłości wypróbowano pewne obejścia, które przyniosły różne sukcesy z pewnymi problemami. Można na przykład zmodyfikować hesjan, dodając macierz korekcji tak, aby była określona dodatnio. Jednym z podejść jest diagonalizacja hesjanu i wybór tak, aby miał takie same wektory własne jak hes, ale z każdą ujemną wartością własną zastąpioną przez . ${\ Displaystyle B_ {k}}$${\ Displaystyle f ''(x_ {k}) + B_ {k}}$${\ Displaystyle B_ {k}}$${\ Displaystyle f ''(x_ {k}) + B_ {k}}$${\ Displaystyle \ epsilon > 0}$

Podejście wykorzystywane w algorytmie Levenberga-Marquardta (który wykorzystuje przybliżony hes) polega na dodaniu skalowanej macierzy tożsamości do Hessian , ze skalą dostosowywaną w każdej iteracji w razie potrzeby. W przypadku dużych i małych hesjan iteracje będą się zachowywać jak zejście gradientowe z rozmiarem kroku . Powoduje to wolniejszą, ale bardziej niezawodną zbieżność, w której hes nie dostarcza użytecznych informacji. ${\ Displaystyle \ mu I}$${\ Displaystyle \ mu}$${\displaystyle 1/\mu}$

Niektóre zastrzeżenia

Metoda Newtona w swojej pierwotnej wersji ma kilka zastrzeżeń:

1. Nie działa, jeśli hes nie jest odwracalny. Wynika to jasno z samej definicji metody Newtona, która wymaga przyjęcia odwrotności hessu.
2. Może wcale nie być zbieżne, ale może wejść w cykl mający więcej niż 1 punkt. Zobacz rozdział "Analiza awarii" w metodzie Newtona .
3. Może zbiegać się do punktu siodłowego zamiast do lokalnego minimum, zobacz sekcję „Interpretacja geometryczna” w tym artykule.

Popularne modyfikacje metody Newtona, takie jak wspomniane powyżej metody quasi-Newtona czy algorytm Levenberga-Marquardta, również mają swoje zastrzeżenia:

Na przykład, zwykle wymagane jest, aby funkcja kosztu była (silnie) wypukła, a hesj był globalnie ograniczony lub ciągły Lipschitz, na przykład jest to wspomniane w sekcji „Zbieżność” w tym artykule. Jeśli spojrzy się na prace Levenberga i Marquardta w referencji do algorytmu Levenberga–Marquardta , które są oryginalnymi źródłami wspomnianej metody, to można zauważyć, że w pracy Levenberga w zasadzie nie ma analizy teoretycznej, natomiast praca Marquardta analizuje jedynie sytuację lokalną i nie udowadnia globalnego wyniku konwergencji. Można porównać z metodą wyszukiwania linii z nawrotem dla gradientu opadania, która ma dobrą gwarancję teoretyczną przy bardziej ogólnych założeniach i może być zaimplementowana i dobrze sprawdza się w praktycznych problemach dużej skali, takich jak głębokie sieci neuronowe.

Zobacz też

• Metoda quasi-Newtona
• Zejście gradientowe
• Algorytm Gaussa-Newtona
• Algorytm Levenberga-Marquardta
• Region zaufania
• Optymalizacja
• Metoda Nelder-Mead

Uwagi

Bibliografia

• Avriel, Mordechaj (2003). Programowanie nieliniowe: analiza i metody . Wydawnictwo Dover. Numer ISBN 0-486-43227-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optymalizacja numeryczna: Aspekty teoretyczne i praktyczne . Universitext (drugie poprawione wydanie tłumaczenia z 1997 r. wyd. francuskie). Berlin: Springer-Verlag. doi : 10.1007/978-3-540-35447-5 . Numer ISBN 3-540-35445-X. MR  2265882 .
• Fletcher, Roger (1987). Praktyczne metody optymalizacji (wyd. 2). Nowy Jork: John Wiley i Synowie . Numer ISBN 978-0-471-91547-8.
• Givens, Geof H.; Hoeting, Jennifer A. (2013). Statystyka obliczeniowa . Hoboken, New Jersey: John Wiley & Sons. s. 24-58. Numer ISBN 978-0-470-53331-4.
• Nocedal, Jorge; Wright, Stephen J. (1999). Optymalizacja numeryczna . Springer-Verlag. Numer ISBN 0-387-98793-2.
• Kowaliow, Dmitrij; Miszczenko, Konstantin; Richtárik, Piotr (2019). „Stochastyczne metody Newtona i sześcienne Newtona z prostymi lokalnymi wskaźnikami liniowo-kwadratowymi”. arXiv : 1912.01597 [ cs.LG ].

Zewnętrzne linki

• Korenblum, Daniel (29.08.2015). "Wizualizacja Newtona-Raphsona (1D)" . Bloki . ffe9653768cb80dfc0da.