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

f ( x 0 + Δ x ) = f ( x 0 ) + ∇ f ( x 0 ) T Δ x + 1 2 Δ x T B Δ x , {\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 ( ∇ f ) {\displaystyle (\nabla f)} jest gradientem f {\displaystyle f} a B {\displaystyle B} jej hesjanem.

Szereg Taylora samego gradientu:

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

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

Δ x 0 = − B − 1 ∇ f ( x 0 ) , {\displaystyle \Delta x_{0}=-B^{-1}\nabla f(x_{0}),}

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

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

  • Δ x k = − α k B k − 1 ∇ f ( x k ) , {\displaystyle \Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k}),} z α {\displaystyle \alpha } dobraną by spełnić warunek Wolfa;
  • x k + 1 = x k + Δ x k ; {\displaystyle x_{k+1}=x_{k}+\Delta x_{k};}
  • Gradient obliczany w nowym punkcie ∇ f ( x k + 1 ) {\displaystyle \nabla f(x_{k+1})} i
y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) , {\displaystyle y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k}),}
  • są używane do poprawienia hesjanu B k + 1 , {\displaystyle B_{k+1},} lub bezpośrednio jego odwrotności H k + 1 = B k + 1 − 1 {\displaystyle H_{k+1}=B_{k+1}^{-1}} używająć wzoru Shermana-Morrisona.

Najpopularniejsze metody obliczania przybliżeń:

Metoda B k + 1 = {\displaystyle B_{k+1}=} H k + 1 = B k + 1 − 1 = {\displaystyle H_{k+1}=B_{k+1}^{-1}=}
DFP ( I − y k Δ x k T y k T Δ x k ) B k ( I − Δ x k y k T y k T Δ x k ) + y k y k T y k T Δ x k {\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}}}} H k + Δ x k Δ x k T y k T Δ x k − H k y k y k T H k T y k T H k y 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 B k + y k y k T y k T Δ x k − B k Δ x k ( B k Δ x k ) T Δ x k T B k Δ x k {\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}}}} ( I − y k Δ x k T y k T Δ x k ) T H k ( I − y k Δ x k T y k T Δ x k ) + Δ x k Δ x k T y k T Δ 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 B k + y k − B k Δ x k Δ x k T Δ x k Δ x k T {\displaystyle B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{T}\Delta x_{k}}}\Delta x_{k}^{T}}
Broyden Family ( 1 − φ k ) B k + 1 B F G S + φ k B k + 1 D F P , {\displaystyle (1-\varphi _{k})B_{k+1}^{BFGS}+\varphi _{k}B_{k+1}^{DFP},} φ ∈ [ 0 , 1 ] {\displaystyle \varphi \in [0,1]}
SR1 B k + ( y k − B k Δ x k ) ( y k − B k Δ x k ) T ( y k − B k Δ x k ) T Δ x k {\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}}}} H k + ( Δ x k − H k y k ) ( Δ x k − H k y k ) T ( Δ x k − H k y k ) T y 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.