Metoda Quasi-Newtona (zmiennej metryki)

Metoda Quasi-Newtona może być używana, gdy obliczenie Hessianu (macierzy drugich pochodnych funkcji) wymaganego przez metodę Newtona jest trudne lub czasochłonne. Idea metody polega na przybliżeniu Hessianu lub jego odwrotności za pomocą pierwszych pochodnych.

W każdym kroku algorytmu przybliżenie Hessianu (H) lub jego odwrotności (B) jest uaktualniane przy pomocy informacji o gradiencie. Informacje o krzywiźnie funkcji są gromadzone w trakcie wykonywania obliczeń.

Oznaczenia:

H – Hessian

B – odwrotność macierzy H –

x₀ – pierwsze przybliżenie rozwiązania (punkt startowy)

x_i – i-te przybliżenie rozwiązania

H₀, B₀ – macierze początkowe

H_i, B_i – i-te macierze przybliżone

H_i^u, B_i^u – i-te poprawki wartości macierzy H_i, B_i

ε – wymagana dokładność

Metody przybliżania wartości H i B:

Istnieją różne metody obliczania przybliżeń, z których dwie najpopularniejsze to:

• DFP (Davidon-Fletcher-Powell)

  

• BFGS (Broyden-Fletcher-Goldfarb-Shanno)

co po odwróceniu daje

Ponadto istnieje cała rodzina metod znana jako Broyden family

, gdzie Φ jest dowolną liczbą rzeczywistą

Algorytm:

1. Ustal i = 0, x₀, B₀ oraz kryterium zatrzymania ε.

, gdzie macierz początkowa H₀ może być dowolną symetryczną, dodatnie określoną macierzą. W szczególności .

2. Sprawdź, czy punkt x_i spełnia kryterium stopu – np. jeślito x_i jest rozwiązaniem

3. Wyznacz kierunek poprawy

4. Wyznacz kolejne przybliżenie rozwiązania , gdzieto długość kroku minimalizująca jednowymiarową funkcję

5. Wyznacz poprawkęzgodnie z wybraną metodą (DFP, BFGS), używając wartości , oraz

6. Uaktualnij

7. i = i+1

8. Idź do punkt 2.