WYKŁAD 8
METODA NEWTONA-RAPHSONA
Znajdowanie minimum nieliniowej funkcji celu za pomocą metody Newtona opiera się na
równoważności rozwiązywania układu n równań liniowych
(8.1)
oraz minimalizacji funkcji kwadratowej n zmiennych
(8.2)
macierz [ J ] jest nazywana macierzą Jacobiego i wynosi
(8.3)
Hesjan [ H ] funkcji f
Q
jest równy
(8.4)
Hesjan jest więc dodatnio określony, jeżeli tylko macierz Jacobiego nie jest osobliwa.
Kierunek d=x
0
-x łączący punkt startowy x z minimum funkcji f
Q
(x
0
) wynosi za (7.12)
(8.5)
Dla funkcji kwadratowej optimum x
0
jest po prostu sumą x+d natomiast dla ogólnego
przypadku, kiedy badana funkcja f(x) jest tylko zbliżona do funkcji kwadratowej f
Q
(x)
otrzymujemy schemat iteracyjny
(8.6)
skalar oznacza długość kroku, dla którego wyznaczono minimum f(x) wzdłuż d. Wyrażenie
(8.6) opisuje podstawowy algorytm metody Newtona-Raphsona, w którym podstawowy
nakład obliczeń wynika z konieczności wyznaczenia kolejno: gradientu funkcji f
Q
(x
k
), jej
hesjanu i odwróceniu go bądź rozwiązaniu układu równań [H(x
k
)](x
0
-x
k
)= -
f
Q
(x
k
).
Najczęściej mamy do czynienia z sytuacją, kiedy postać funkcji celu i w konsekwencji jej
pochodne nie są dane w postaci jawnej. Zachodzi więc potrzeba numerycznej estymacji,
zarówno wektora gradientu jak i macierzy hesjanu. Wykonuje się to najczęściej za pomocą
metody aproksymacji parabolicznej w otoczeniu punktu x
k
Jej algorytm (dla funkcji jednej zmiennej) jest następujący:
1. Ustawiamy początek lokalnego układu współrzędnych w danym punkcie;
2. Wyznaczamy trzy wartości funkcji w punktach f(- )=m, f(x=0)=o, f(+ )=p;
3. Zakładamy paraboliczny przebieg funkcji f( )=
0
+
1
x +
2
x
2
, co oznacza
(8.7)
4. Nieznane współczynniki
1
,
2
wynoszą
(8.8)
5. Gradient funkcji f(x) jest więc równy
1
a hesjan H(x)=2
2
.
W celu uogólnienia na funkcję n zmiennych wprowadza się oznaczenia f(x-
i
)=m
i
, f(x+
i
)=p
i
,
gdzie wektor
i
ma wszystkie składniki równe zeru za wyjątkiem i-tego równego .
Rozpatrzmy dowolny przekrój (0, x
i
, x
j
) pola funkcji f(x) pokazany na rys.8.1.
Rys.8.1. Schemat przekroju pola funkcji f(x) płaszczyzną (0 x
i
x
j
)
Składowe gradientu f(x) w punkcie (x
i
=0, x
j
=0) wynoszą
(8.9)
m
i
p
i
p
j
m
j
q
ij
r
ij
s
ij
t
ij
x
i
x
j
Diagonalne składniki hesjanu są równe
(8.10)
Wyznaczenie pozadiagonalnych składników hesjanu wymaga wprowadzenia dodatkowych
wartości funkcji f(x).
(8.11)
W wyniku otrzymuje się
(8.12)
Przybliżone wyznaczenie w danym punkcie hesjanu minimalizowanej funkcji n zmiennych
wymaga (2n+2n
2
) obliczeń funkcji w bezpośrednim otoczeniu tego punktu.
W analizie rzeczywistych funkcji celu mamy zazwyczaj do czynienia z dodatnimi ich
wartościami w całej dopuszczalnej przestrzeni optymalizacji, co wynika z ich sensu
fizycznego np. koszt, masa, pobór mocy. Wynika z tego, że diagonalne elementy hesjanu są
również dodatnie, a macierz z nich utworzona jest dodatnio określona
(8.13)
Fakt ten wykorzystuje modyfikacja Levenberga-Marquarta metody Newtona, której algorytm
jest następujący
1. W punkcie x
k
oblicz gradient f(x
k
) oraz hesjan [H(x
k
)];
2. Sprawdź czy hesjan jest dodatnio określony, jeśli tak to =
jeśli nie =1
3. Wyznacz kierunek d
k
spełniający [H(x
k
)+ diag[H(x
k
)]]d
k
= - f(x
k
);
4. Wykonaj minimalizację (określenie dodatniej liczby ) w kierunku d;
(8.14)
5. Sprawdź kryterium zatrzymania, jeśli nie jest spełnione to powrót do p.1.