Metody i algorytmy optymalizacji dr Helena Spyra Wykład 5
Ekstremum funkcji jednej i wielu zmiennych Niech f(x) jest funkcją rzeczywistą klasy C 2 dla x € R W punkcie x* , w którym funkcja osiąga minimum, spełnione są warunki : f '(x*) = 0 f " (x*) ≥ 0 Po określeniu punktów stacjonarnych następuje wybór punktu minimalizującego funkcję f ( x ).
Jeżeli rozwiązanie równania:
g(x) = f'(x)= 0
jest możliwe w praktyce tylko jako jego przybliżenie, które uznajemy za dostatecznie dobre, stosujemy procedury iteracyjne, w których generujemy ciąg { xk } zbieżny do rozwiązania i taki, że dane są :
l. punkt startowy x0 2. reguła generowani ciągu { xk }
3. kryterium zakończenia obliczeń
Elementem, który wyznacza cechy charakterystyczne algorytmów, jest sposób generowania ciągu { xk },
który jest na ogół nieskończony i spełnia warunek:
Wykorzystywane w obliczeniach kryteria można podzielić na trzy grupy określające:
- stopień przybliżenia do rozwiązania
- ilość iteracji
- czas pracy
Algorytm Newtona- Raphsona
Załóżmy, że f (x) jest klasy C2 Zadanie poszukiwania minimum zastępujemy zadaniem wyznaczania punktów stacjonarnych.
Po określeniu punktów stacjonarnych następuje sprawdzenie, który z nich jest punktem minimalizującym.
1) punkt startowy - dowolny x0 , f "(x0) ≠ 0.
2) reguła generowania ciągu {xk}
znamy punkt xk 3) kryterium zakończenia obliczeń.
Teoretycznym kryterium jest: zakończyć obliczenia w x*, w którym f '(x*) = 0.
{xk} jest na ogół nieskończonym ciągiem, za dostatecznie dobre przybliżenie punktu x* uznajemy punkt xn dla którego | f ' (xn) | 0
Przykład
f (x) = x3 - 9x2 + 20x - 12 f '(x) = 3x2 - 18x + 20 f ''(x) = 6x - 18
Przyjmijmy x0 = 4 f /(x0) = - 4 f // (x0) = 6 x 1 = 4 + 4/6 = 4,6666, f'(x1)=1,3325 f"(x1) = 9,9996
x2= 4,6666 - 1,3325/9,9996 = 4,5334
f'(x2)= 0,0539 f ''(x2) = 9,2004
x3= 4,5334 - 0,0539/9,2004 = 4,5276
f '(x3) = 0,008, f"(x3) = 9,1656
Jeżeli ε = 0,01 to |f '(x3) |
(…)
… znajdujemy po
wykonaniu jednego kroku. x* = x1 (metoda Newtona-stycznych) Algorytm Newtona
Szukamy punktu X* minimum funkcji f(X), X € RN,
która ma ciągłe wszystkie pochodne cząstkowe do drugiego rzędu włącznie i jest funkcją ściśle wypukłą. Punkt Xk jest pewnym przybliżeniem punktu X*.
Na podstawie wzoru Taylora funkcję f (X) możemy aproksymować w otoczeniu punktu Xk funkcją kwadratową
hesjan dodatnio…
… kroku)
1. Punkt startowy - dowolny punkt X0, Hf(X0) dodatnio określona
2. Reguła generowania ciągu {Xk}
przy czym tk* jest liczbą, dla której
3. Kryterium zakończenia obliczeń: |Gn| < ε
W klasie alg. analog.do zmodyf. alg.Newtona-Raphsona w poszczególnych punktach hesjan można zastąpić dodatnio określoną macierzą a nawet macierzą jednostkową.
- metoda najszybszego spadku
spośród wszystkich kierunków…
…,... muszą być dodatnie i tak dobrane, aby zapewniły zbieżność do punktu X* ciągu punktów generowanych przez algorytm. Wektor określa w punkcie x(k) kierunek najszybszego spadku wartości funkcji f(x).
Kolejne przybliżenie X(k+l) punktu X* wyznaczamy w kierunku prostopadłym do warstwicy w punkcie X(k) , w kierunku najszybszego spadku wartości funkcji. Algorytm gradientu możemy traktować jako N algorytmów…
… wektorem przestrzeni RN.
Zbiór wszystkich punktów X, takich że
X= Xk+αk ξk αk € < 0, + ∞) tworzy półprostą wychodzącą z punktu Xk w kierunku wektora ξk . Wyznaczanie na tej półprostej punktu, w którym
funkcja kryterialna f (X) osiąga minimum, polega na znalezieniu takiego dodatniego współczynnika αk* że
czyli minimum funkcji jednej zmiennej αk , αk> 0.
Wykresem funkcji F(αk) jest krzywa, która powstaje…
... zobacz całą notatkę
Komentarze użytkowników (0)