Newton's method in optimization

Newton’s method is a basic tool in numerical analysis and numerous applications, including operations research anddata mining. We survey the history of the method, its main ideas, convergence results and modifications. We also lay out on methods, which are focuse on approximation of Hessian matrix. It makes Newtons Method works better and has wider applications. Newtons Method role in optimization cannotbe overestimated: the method is the basis forthe most effective procedures in linear and nonlinearprogramming.

Metoda Newtona jest jednym z fundamentalnych narzedzi analizy numerycznej,metod operacyjnych, optymalizacji i sterowania optymalnego. Ma wielezastosowan w zarzadzaniu, przemysle, pracach naukowych z dziedziny finansówi eksploracji danych. Rola metody Newtona w dziedzinie optymalizacji jest nieoszacowana:metoda jest podstawa dla najbardziej efektywnych procedur programowanialiniowego i nieliniowego.Niniejsza praca została podzielona na piec rozdziałów. W pierwszym przedstawimyogólna idee metody oraz jej interpretacje graficzna. Opiszemy historierozwoju metody oraz przedstawimy kryteria zatrzymania algorytmu.Drugi rozdział poswiecony jest metodzie Newtona dla funkcji jednej zmiennej.Zaprezentujemy tu konstrukcje algorytmu wykorzystujaca aproksymacje kwadratowabadanej funkcji. Poniewaz metoda jest zbiezna lokalnie, poszukiwaniaoptimum funkcji ograniczymy do obszarów jej zbieznosci. Wyznaczaniem tychobszarów zajmuja sie inne, lepiej do tego przystosowane metody. Zasygnalizujemyrówniez problemy zilustrowane przykładami, wynikajace z nieodpowiedniegowyboru punktu startowego ciagu iteracyjnego.Metoda Newtona w pewnym otoczeniu rozwiazania jest kontrakcja, dlatego poszukiwania optimum sprowadzaja sie do wyznaczania punktów stałych funkcji.Duza role odgrywa tu twierdzenie Banacha o punkcie stałym. Twierdzenia i wnioskiz tym zwiazane opisujemy w podrozdziale 2.3. Mozna równiez okreslic bładprzyblizenia rozwiazania w pewnym etapie działania algorytmu, jesli zostanieon zatrzymany zanim osiagnie punkt optymalizujacy funkcje. Sposób szacowaniabłedu wykorzystujacy wzór Taylora oraz twierdzenie Lagrange’a o wartoscisredniej przedstawimy w podrozdziale 2.4.W rozdziale trzecim opiszemy aplikacje metody Newtona do wypukłychfunkcji wielu zmiennych. Przedstawimy konstrukcje algorytmu oraz wykazemy,ze algorytm charakteryzuje sie zbieznoscia drugiego rzedu. Wprowadzimy równiezrozszerzenie pierwotnego algorytmu uwzgledniajace gradient optymalizowanejfunkcji jako kierunek poszukiwan. Modyfikacja ta sprawia, ze metoda jestzbiezna niezaleznie od wyboru punktu startowego algorytmu.W kazdym kroku metody Newtona niezbedne jest wyznaczenie macierzydrugich pochodnych. Jest to uciazliwe i wymaga duzego nakładu obliczen, szczególniew przypadku funkcji o duzej liczbie zmiennych. Istnieja natomiast metody,które w dobry sposób przyblizaja hesjan funkcji lub jego odwrotnosc bez koniecznoscibezposredniego wyznaczania jego wartosci. W rozdziale czwartym zaprezentujemynajpopularniejsze metody quasi-newtonowskie. Czyli takie, którewykorzystuja aproksymacje odwrotnosci hesjanu rozpatrywanej funkcji.Głównymi pozycjami literatury niniejszej pracy sa pozycje [8] oraz [9]. Rozdziałpierwszy oparty jest na artykule B. T. Polyaka pt. „Newton’s method andits use in optimization” [7]. Rozdział drugi został przygotowany na podstawieksiazki R. Wita „Metody programowania nieliniowego” [9] oraz artykułu R. M.Brooks’a, K. Schmitt’a „The contraction mapping principle and some applications”[1]. Zamieszczone w tym rozdziale przykłady wraz z ilustracjami stanowiaopracowanie własne. W rozdziale trzecim została wykorzystana po raz kolejnypozycja [9] oraz W. Findeisen, J. Szymanowski, A. Wierzbicki „Teoria i metodyobliczeniowe optymalizacji” [5]. Rozdział ostatni oparty jest na ksiazce J. Seidlera,A. Badacha, W. Molisza „Metody rozwiazywania zadan optymalizacji”.