Metoda Newtona (optymalizacja)

Metoda Newtonaalgorytm numeryczny mający na celu znalezienie minimum zadanej funkcji celu.

Metodą Newtona nazywana jest również metoda rozwiązywanie równań nieliniowych. Oba pojęcia pomimo takiej samej nazwy odnoszą się do dwóch różnego rodzaju zadań numerycznych.

AlgorytmEdytuj

ZadanieEdytuj

Metoda Newtona jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu  

 

gdzie  

Założenia dla metody są następujące:

  •   (funkcja jest ciągła i podwójnie różniczkowalna),
  •   jest ściśle wypukła w badanej dziedzinie.

OpisEdytuj

 
Porównanie metody najszybszego spadku (linia zielona) z metodą Newtona (linia czerwona). Na rysunku widać linie poszukiwań minimum dla zadanej funkcji celu. Metoda Newtona używa informacji o krzywiźnie w celu zoptymalizowania ścieżki poszukiwań.

Na samym początku algorytmu wybierany jest punkt startowy   W punkcie tym obliczany jest kierunek poszukiwań   Punkt w następnym kroku obliczany jest według wzoru

 

jeśli obliczony punkt nie spełni warunku stopu algorytmu, całe postępowanie jest powtarzane.

Do obliczenia kierunku poszukiwań w metodzie Newtona wykorzystywane jest rozwinięcie Taylora funkcji celu względem danego punktu  

 

gdzie   jest gradientem funkcji,   jest macierzą Hessego, zaś   jest resztą o wielkości rzędu  

Funkcję celu można zatem przybliżyć przez aproksymację kwadratową   względem punktu  

 

kierunek   jest tak dobrany aby zminimalizować funkcję   tzn.

 

Rekurencyjny wzór metody Newtona ma zatem postać

 

Algorytm można zapisać:

  1. Wybierz punkt startowy  
  2.  
  3.  
  4. Sprawdź kryterium stopu, jeśli nie jest spełniony wykonaj ponownie krok 2.

Modyfikacja Newtona-RaphsonaEdytuj

Istnieje modyfikacja optymalizacyjnej metody Newtona, nazwana metodą Newtona-Raphsona polegającą na uwzględnieniu w kolejnych krokach minimalizacji kierunkowej, przez co zwiększony zostaje obszar zbieżności metody.

Algorytm w tym przypadku polega, analogicznie jak w pierwszej metodzie, na wyborze punktu startowego. Dla danego punktu obliczany jest kierunek poszukiwań oraz dokonywana jest na jego podstawie minimalizacja kierunkowa, tzn. obliczana jest taka wartość   że

 

Kolejny krok obliczany jest ze wzoru

 

Algorytm można zapisać:

  1. Wybierz punkt startowy  
  2.  
  3. dokonaj minimalizacji   względem  
  4.  
  5. Sprawdź kryterium stopu, jeśli nie jest spełniony – wykonaj ponownie krok 2.

Minimalizacja kierunkowa może być dokonana przez dowolną numeryczną metodę optymalizacji jednowymiarowej. Przykładowymi algorytmami mogą być: metoda złotego podziału, metoda dychotomii, metoda punktu środkowego.

ImplementacjaEdytuj

Przy implementacji metody Newtona, przy określaniu kierunku poszukiwań   zamiast obliczania odwrotności hesjanu   warto skorzystać z numerycznych metod rozwiązywania układów równań liniowych

 

w celu obliczenia wartości wektora  

Kryterium stopuEdytuj

W celu określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie Newtona, można użyć następujących kryteriów stopu (dla zadanej precyzji   oraz normy  )

  •   (test stacjonarności),
  •  

ZbieżnośćEdytuj

Metoda Newtona jest metodą o zbieżności kwadratowej. Oznacza to, iż przy spełnieniu założeń metody, odległości pomiędzy kolejnymi przybliżeniami a minimum funkcji   maleją kwadratowo

 

Warto wspomnieć, iż metoda Newtona dla funkcji kwadratowych znajduje minimum już w pierwszym kroku – wynika to z faktu iż w metodzie funkcja celu jest lokalnie aproksymowana właśnie funkcją kwadratową.

Optymalizacja jednowymiarowaEdytuj

Szczególnym przypadkiem metody Newtona jest jej jednowymiarowa wersja, która może być skutecznym sposobem minimalizacji kierunkowej. Zadanie numeryczne polega w takim przypadku na znalezieniu minimum jednowymiarowej funkcji celu  

 

Funkcja   musi być podwójnie różniczkowalna i ściśle wypukła w badanej dziedzinie.

Wzór rekurencyjny dla metody upraszcza się do postaci

 

gdzie   oraz   to kolejne pochodne funkcji  

Zobacz teżEdytuj

BibliografiaEdytuj

  • Fortuna Z., Macukow B., Wąsowski J.: Metody numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.
  • Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.

Linki zewnętrzneEdytuj