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 ${\displaystyle f(x).}$ Rozwinięcie w szereg Taylora funkcji ${\displaystyle f(x)}$ wyraża się wzorem:

${\displaystyle 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 ${\displaystyle (\nabla f)}$ jest gradientem ${\displaystyle f}$ a ${\displaystyle B}$ jej hesjanem.

Szereg Taylora samego gradientu:

${\displaystyle \nabla f(x_{0}+\Delta x)=\nabla f(x_{0})+B\Delta x.}$

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

${\displaystyle \Delta x_{0}=-B^{-1}\nabla f(x_{0}),}$

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

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

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

${\displaystyle 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}=}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
DFP	${\displaystyle \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}}}}$	${\displaystyle 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	${\displaystyle 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}}}}$	${\displaystyle \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	${\displaystyle B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{T}\Delta x_{k}}}\Delta x_{k}^{T}}$
Broyden Family	${\displaystyle (1-\varphi _{k})B_{k+1}^{BFGS}+\varphi _{k}B_{k+1}^{DFP},}$ ${\displaystyle \varphi \in [0,1]}$
SR1	${\displaystyle 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}}}}$	${\displaystyle 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ż

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