Metoda quasi-Newtona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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}),

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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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