Metoda quasi-Newtona

W zagadnieniach optymalizacji, Metody quasi-Newtonowskie (nazywane również metodami zmiennej metryki) są dobrze znanymi algorytmami 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 minimym funkcji $f(x)$. Rozwinięcie w szereg Taylora funkcji $f(x)$ wyraża się wzorem:

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

gdzie ($\nabla f$) jest gradientem $f$ a $B$ jej hesjanem. Szereg Taylora samego gradientu:

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

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

$\Delta x_0=-B^{-1}\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ą $min_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}$

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

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

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

Najpopularniejsze metody obliczania przybliżeń:

Metoda	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
DFP	$\left (I-\frac {y_k \Delta x_k^T} {y_k^T \Delta x_k} \right ) B_k \left (I-\frac {\Delta x_k y_k^T} {y_k^T \Delta x_k} \right )+\frac {y_k y_k^T} {y_k^T \Delta x_k}$	$H_k + \frac {\Delta x_k \Delta x_k^T}{y_k^{T} \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} \Delta x_k} - \frac {B_k \Delta x_k (B_k \Delta x_k)^T} {\Delta x_k^{T} B_k \Delta x_k}$	$\left (I-\frac {y_k \Delta x_k^T} {y_k^T \Delta x_k} \right )^T H_k \left (I-\frac { y_k \Delta x_k^T} {y_k^T \Delta x_k} \right )+\frac {\Delta x_k \Delta x_k^T} {y_k^T \Delta x_k}$
Broyden	$B_k+\frac {y_k-B_k \Delta x_k}{\Delta x_k^T\Delta x_k} \Delta x_k^T$
Broyden Family	$(1-\varphi_k) B_{k+1}^{BFGS}+ \varphi_k B_{k+1}^{DFP}$, $\varphi\in[0,1]$
SR1	$B_{k}+\frac {(y_k-B_k \Delta x_k) (y_k-B_k \Delta x_k)^T}{(y_k-B_k \Delta x_k)^T \Delta x_k}$	$H_{k}+\frac {(\Delta x_k-H_k y_k) (\Delta x_k-H_k y_k)^T}{(\Delta x_k-H_k y_k)^T y_k}$

Zobacz też

• optymalizacja
• metoda gradientu prostego
• metoda Newtona

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. ISBN 0-387-98793-2.
• Edwin K.P.Chong and Stanislaw H.Zak, An Introduction to Optimization 2ed, John Wiley & Sons Pte. Ltd. August 2001.