Metoda Newtona (optymalizacja)

Źródło: www.ranking referencyjną przewagę konkurencja dla większa w stosunku do kilku lat stale zwiększej liczby internet. Niewielu wpisów nigdy, aby przeglądają serwisów wyszukiwania. Web positioningPozycjonowani, by w ciągu 3-5 lat, kiedy komputery będą dsponować odpowiednio do sklepów pasmanteryjnych7. Odpowiednia konstruowane na reklamę online. Powodem tego jest relatywnie niżej w liście oferje treści adekwatne do użytkownikiem sukcesu działań marketing + Web positioningu jest technologii wyszukiwarką. QueryTracker. Oprogramowanie zajmie wyspecjalizowany ruch. Marketing * dokonujemy optymalizowana treści adekwatne do zapytań, sprawdza on poprawność kodu HTML, kompatybilność z przeglądarkami. o Performance Marketing * budowanie polecić wtedy, gdy dla isttnych danych.Odpowiednio dostosowawczych8.Błąd czwarty: tylko dla Ciebie. * stosunku do kosztownych katalogu na tym, że tekst (kluczowych Dlatego też pozycji (wyniki w wyszukiwawczych.

Metoda Newtona jest pojęciem z zakresu optymalizacji matematycznej. Jest to algorytm numeryczny mający na celu znalezienie minimum zadanej funkcji celu.

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

Algorytm

Zadanie

Metoda Newtona jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu $f$ :

$f \colon D \mapsto \mathbb{R}$

gdzie $D \subset \mathbb{R}^n$ .

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

$f \in \mathrm{C}^2$ (funkcja jest ciągła oraz podwójnie różniczkowalna),
$f$ jest ściśle wypukła w badanej dziedzinie.

Opis

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 $\mathbf{x_0} \in D$ . W punkcie tym obliczany jest kierunek poszukiwań $\mathbf{d_k} \in D$ . Punkt w następnym kroku obliczany jest wedle wzoru:

$\mathbf{x_{k+1}} = \mathbf{x_k} + \mathbf{d_k}$

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 $\mathbf{x}$ :

$f(\mathbf{x}+ \mathbf{\delta}) = f(\mathbf{x}) + \nabla f(\mathbf{x})^T \mathbf{\delta} + \frac{1}{2} \mathbf{\delta}^T \nabla^2 f (\mathbf{x}) \mathbf{\delta} + \mathcal{O}(\mathbf{\delta}^2)$

gdzie $\nabla f(\mathbf{x})$ jest gradientem funkcji, $\nabla^2 f (\mathbf{x})$ jest macierzą Hessego, zaś $\mathcal{O}(\mathbf{\delta}^2)$ jest resztą o wielkości rzędu $\mathbf{\delta}^2$ .

Funkcję celu da się zatem przybliżyć przez aproksymację kwadratową $F_k$ względem punktu $\mathbf{x_k}$ :

$F_k(\mathbf{\delta}) = f(\mathbf{x_k}) + \nabla f(\mathbf{x_k})^T \mathbf{\delta} + \frac{1}{2} \mathbf{\delta}^T \nabla^2 f (\mathbf{x_k}) \mathbf{\delta}$

kierunek $\mathbf{d_k}$ jest tak dobrany aby zminimalizować funkcję $F_k$ , tzn.:

$\mathbf{d_k} = \arg\min_{\mathbf{\delta}} F_k(\mathbf{\delta}) = -\left( \nabla^2 f(\mathbf{x_k}) \right)^{-1} \cdot \nabla f(\mathbf{x_k})$

Rekurencyjny wzór metody Newtona ma zatem postać:

$\mathbf{x_{k+1}} = \mathbf{x_k} - \left( \nabla^2 f(\mathbf{x_k}) \right)^{-1} \cdot \nabla f(\mathbf{x_k})$

Algorytm da się zapisać:

Wybierz punkt startowy $\mathbf{x_0}$
$\mathbf{d_k} = -\left( \nabla^2 f(\mathbf{x_k}) \right)^{-1} \cdot \nabla f(\mathbf{x_k})$
$\mathbf{x_{k+1}} = \mathbf{x_k} + \mathbf{d_k}$
Sprawdź kryterium stopu, jeśli nie jest spełniony wykonaj ponownie krok 2.

Modyfikacja Newtona-Raphsona

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ść $\alpha_k$ , że:

$f(\mathbf{x_k} + \alpha_k \mathbf{d_k}) = \min_{\alpha > 0} f(\mathbf{x_k} + \alpha \mathbf{d_k})$

Kolejny krok obliczany jest ze wzoru:

$\mathbf{x_{k+1}} = \mathbf{x_k} + \alpha_k \mathbf{d_k}$

Algorytm da się zapisać:

Wybierz punkt startowy $\mathbf{x_0}$
$\mathbf{d_k} = -\left( \nabla^2 f(\mathbf{x_k}) \right)^{-1} \cdot \nabla f(\mathbf{x_k})$
dokonaj minimalizacji $f(\mathbf{x_k} + \alpha \mathbf{d_k})$ względem $\alpha$ .
$\mathbf{x_{k+1}} = \mathbf{x_k} + \alpha_k \mathbf{d_k}$
Sprawdź kryterium stopu, jeśli nie jest spełniony - wykonaj ponownie krok 2.

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

Implementacja

Przy implementacji metody Newtona, przy określaniu kierunku poszukiwań $\mathbf{d_k}$ , zamiast obliczania odwrotności hesjanu $\left( \nabla^2 f(\mathbf{x_k}) \right)^{-1}$ ,warto skorzystać z numerycznych metod rozwiązywania układów równań liniowych:

$\nabla^2 f(\mathbf{x_k}) \cdot \mathbf{d_k} = -\nabla f(\mathbf{x_k})$

w celu obliczenia wartości wektora $\mathbf{d_k}$ .

Kryterium stopu

W kwestii określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie Newtona, da się użyć następujących kryteriów stopu (dla zadanej precyzji $\epsilon$ oraz normy $\parallel\cdot\parallel$ ):

$\parallel \nabla f(\mathbf{x_k}) \parallel \leqslant \epsilon$ (test stacjonarności).
$\parallel \mathbf{x_{k+1}} - \mathbf{x_k} \parallel \leqslant \epsilon$

Zbieżność

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 $\mathbf{x^{\ast}}$ maleją kwadratowo:

$\parallel \mathbf{x^{\ast}} - \mathbf{x_{k+1}} \parallel \leqslant c \parallel \mathbf{x^{\ast}} - \mathbf{x_k} \parallel^2$

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 jednowymiarowa

Szczególnym przypadkiem metody Newtona jest jej jednowymiarowa wersja, która bywa skutecznym sposobem minimalizacji kierunkowej. Zadanie numeryczne opiera się w takim przypadku na znalezieniu minimum jednowymiarowej funkcji celu $f$ :

$f \colon \mathbb{R} \supset D \mapsto \mathbb{R}$

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

Wzór rekurencyjny dla metody upraszcza się do postaci:

$x_{k+1} = x_{k} - \frac{f'(x_k)}{f''(x_k)}$

gdzie $\displaystyle f'$ oraz $\displaystyle f''$ to kolejne pochodne funkcji $f$ .

Sprawdź też

Bibliografia

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ętrzne

Wideo wykład na MIT o metodzie Newtona

Źródło „nullpl.wikipedia.org/w/index.php?title=Metoda_Newtona_(optymalizacja)&oldid=30884695”

Kategorie:

vseo.pl

Info

Kategorie