Metoda quasi-Newtona

Metody quasi-Newtonowskie (nazywane również metodami zmiennej metryki) – algorytmy znajdowania ekstremów lokalnych funkcji. Metody quasi-Newtonowskie bazują na metodzie Newtona znajdowania punktów stacjonarnych funkcji. Metoda Newtona zakłada, że funkcja może być lokalnie aproksymowana funkcją kwadratową w otoczeniu optimum, oraz używają pierwszych i drugich pochodnych (gradient i hesjan) w celu znalezienia punktów stacjonarnych.

W metodzie Quasi-Newtona hesjan (macierz drugich pochodnych) minimalizowanej funkcji nie musi być obliczany. Hesjan jest przybliżany przez analizowanie kolejnych wektorów gradientu. Metody Quasi-Newtona są uogólnieniem metody siecznych znajdowania pierwiastków pierwszej pochodnej na problem wielowymiarowy. W przypadku wielowymiarowym równanie siecznej jest wyznaczane w trakcie działania algorytmu. Metody quasi-Newtonowskie różnią się między sobą sposobem ograniczeń rozwiązania, zazwyczaj przez dodawanie nieznacznej poprawki do przybliżanego w każdym kroku hesjanu.

Pierwszy algorytm quasi-Newtonowski został zaproponowany przez W.C. Davidon, fizyka z Argonne National Laboratory.

Opis metody

Jak w metodzie Newtona, stosujemy aproksymacje drugiego stopnia w celu znalezienia minimum funkcji $f(x).$ Rozwinięcie w szereg Taylora funkcji $f(x)$ wyraża się wzorem:

$f(x_0+\mathrm{\Delta }x)=f(x_0)+\mathrm{\nabla }f(x_0{)}^T\mathrm{\Delta }x+\frac{1}{2}\mathrm{\Delta }{x}^{T}B\mathrm{\Delta }x,$

gdzie $(\mathrm{\nabla }f)$ jest gradientem $f$ a $B$ jej hesjanem.

Szereg Taylora samego gradientu:

$\mathrm{\nabla }f(x_0+\mathrm{\Delta }x)=\mathrm{\nabla }f(x_0)+B\mathrm{\Delta }x.$

rozwiązanie równania $\mathrm{\nabla }f(x_0+\mathrm{\Delta }{x}_0)=0$ daje pierwszy krok:

$\mathrm{\Delta }{x}_0=-B^{-1}\mathrm{\nabla }f(x_0),$

jednak $B$ jest nieznana. W jednowymiarowym problemie znajdowanie $B$ i wykonywanie newtonowskiego kroku z zaktualizowaną wartością jest równoważne metodzie siecznych. W problemie wielowymiarowym $B$ jest wyznaczana.

Stosuje się wiele metod do wyznaczania rozwiązania równania siecznej, które jest symetryczne $(B^T=B)$ i najbliższe aktualnie aproksymowanej wartości $B_k$ zgodnie z pewną metryką $mi{n}_B||B-B_k||.$ Aproksymowana wartość początkowa $B_0=I$ jest zazwyczaj wystarczająca do osiągnięcia szybkiej zbieżności. nieznany $x_k$ jest aktualizowana przez stosowanie newtonowskiego kroku obliczanego przy użyciu hesjanu $B_k$

• $\mathrm{\Delta }{x}_k=-{\alpha }_k{B}_k^{-1}\mathrm{\nabla }f(x_k),$ z $\alpha$ dobraną by spełnić warunek Wolfa;
• $x_{k+1}=x_k+\mathrm{\Delta }{x}_k;$
• Gradient obliczany w nowym punkcie $\mathrm{\nabla }f(x_{k+1})$ i

$y_k=\mathrm{\nabla }f(x_{k+1})-\mathrm{\nabla }f(x_k),$

• są używane do poprawienia hesjanu $B_{k+1},$ lub bezpośrednio jego odwrotności $H_{k+1}=B_{k+1}^{-1}$ używająć wzoru Shermana-Morrisona.

Najpopularniejsze metody obliczania przybliżeń:

Metoda	$B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
DFP	$(I-\frac{y_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k})B_k(I-\frac{\mathrm{\Delta }{x}_k{y}_k^T}{y_k^T\mathrm{\Delta }{x}_k})+\frac{y_k{y}_k^T}{y_k^T\mathrm{\Delta }{x}_k}$	$H_k+\frac{\mathrm{\Delta }{x}_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k}-\frac{H_k{y}_k{y}_k^T{H}_k^T}{y_k^T{H}_k{y}_k}$
BFGS	$B_k+\frac{y_k{y}_k^T}{y_k^T\mathrm{\Delta }{x}_k}-\frac{B_k\mathrm{\Delta }{x}_k(B_k\mathrm{\Delta }{x}_k{)}^T}{\mathrm{\Delta }{x}_k^T{B}_k\mathrm{\Delta }{x}_k}$	${(I-\frac{y_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k})}^T{H}_k(I-\frac{y_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k})+\frac{\mathrm{\Delta }{x}_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k}$
Broyden	$B_k+\frac{y_k-B_k\mathrm{\Delta }{x}_k}{\mathrm{\Delta }{x}_k^T\mathrm{\Delta }{x}_k}\mathrm{\Delta }{x}_k^T$
Broyden Family	$(1-{\phi }_k)B_{k+1}^{BFGS}+{\phi }_k{B}_{k+1}^{DFP},$ $\phi \in [0,1]$
SR1	$B_k+\frac{(y_k-B_k\mathrm{\Delta }{x}_k)(y_k-B_k\mathrm{\Delta }{x}_k{)}^T}{(y_k-B_k\mathrm{\Delta }{x}_k{)}^T\mathrm{\Delta }{x}_k}$	$H_k+\frac{(\mathrm{\Delta }{x}_k-H_k{y}_k)(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^T}{(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^T{y}_k}$

Zobacz też

• metoda gradientu prostego
• optymalizacja

Bibliografia

• Eventually W.C. Davidon’s paper published. William C. Davidon, Variable Metric Method for Minimization, SIOPT Volume 1 Issue 1, Pages 1-17, 1991.
• Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. Szablon:ISBN.
• Edwin K.P.Chong and Stanislaw H.Zak, An Introduction to Optimization 2ed, John Wiley & Sons Pte. Ltd. August 2001.