Metoda Newtona (optymalizacja)

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 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.

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 i 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 według 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 można 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 można zapisać:

1. Wybierz punkt startowy $\mathbf{x_0}$
2. $\mathbf{d_k} = -\left( \nabla^2 f(\mathbf{x_k}) \right)^{-1} \cdot \nabla f(\mathbf{x_k})$
3. $\mathbf{x_{k+1}} = \mathbf{x_k} + \mathbf{d_k}$
4. 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 można zapisać:

1. Wybierz punkt startowy $\mathbf{x_0}$
2. $\mathbf{d_k} = -\left( \nabla^2 f(\mathbf{x_k}) \right)^{-1} \cdot \nabla f(\mathbf{x_k})$
3. dokonaj minimalizacji $f(\mathbf{x_k} + \alpha \mathbf{d_k})$ względem $\alpha$.
4. $\mathbf{x_{k+1}} = \mathbf{x_k} + \alpha_k \mathbf{d_k}$
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.

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 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 $\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 może być skutecznym sposobem minimalizacji kierunkowej. Zadanie numeryczne polega 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 i ś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$.

Zobacz też

• Optymalizacja (matematyka)
• Metoda gradientu prostego
• Metoda najszybszego spadku
• metoda złotego podziału

Bibliografia

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

Linki zewnętrzne

• Wideo wykład na MIT o metodzie Newtona