Znaleźć minimum funkcji
,
w przedziale
przy założeniu że funkcja f jest w tym przedziale unimodalna.
Def. (funkcji unimodalnej)
Funkcja f(x) jest unimodaln, jeżeli:
gdzie x' jest globalnym minimum funkcji.
Gdy funkcja celu nie jest unimodalna można spróbować wyznaczyć przedziały unimodalności a następnie optymalizować ją w każdym z tych przedziałów.
Działanie niżej opisanych metod
opiera się na spostrzeżeniu, że znajomość wartości funkcji w dwóch
różnych punktach
należących do przedziału poszukiwań
pozwala zawęzić ten przedział.
Jeżeli
to minimum musi znajdować się w przedziale
,
jeżeli
to minimum musi znajdować się w przedziale
,
jeżeli
to minimum musi znajdować się w przedziale
.
Zasadnicza różnica między
poszczególnymi metodami polega na wyborze punktów kolejnych
eksperymentów:
i
.
Wyznacza punkty
i
równo oddalone od środka przedziału:
zawęża przedział zgodnie z regułami:
jeżeli
,
jeżeli
i w analogiczny sposób kontynuuje poszukiwania w nowym przedziale
do czasu kiedy będzie on dostatecznie mały:
.
Można
wykazać iż długość przedziału poszukiwań po N iteracjach nie
przekracza:
,
gdzie
- początkowy przedział poszukiwań.
Zauważmy
że w metodzie dychotomii wykonujemy 2 eksperymenty w każdej iteracji,
mino iż 1 wartość funkcji wewnątrz przedziału
tak naprawdę znamy z poprzedniej iteracji (tą własność wykorzystują
niżej opisane metody).
W
metodzie złotego podziału punkty eksperymentów są dobierane na tyle
sprytnie by wykorzystać jedną z wartości funkcji celu policzoną w
poprzedniej iteracji. W tym celu wykorzystuje ona podział odcinka w
złotym stosunku. W wyniku złotego podziału odcinka otrzymuje się dwa
odcinki o tej własności, że stosunek długości dłuższego z nich do
długości krótszego jest równy stosunkowi długości dzielonego odcinka
do długości dłuższego odcinka. I tak dopóki przedział
nie osiągnie dostatecznie małego rozmiaru należy wykonywać:
Jeżeli
to wykonaj kolejno podstawienia:
w przeciwnym razie kolejno podstaw:
Przy
czym
Po N iteracjach długość
przedziału poszukiwań wynosi,
gdzie
- początkowy przedział poszukiwań.
W metodzie Fibonacci punkty eksperymentów są dobierane na tyle
sprytnie, by wykorzystać jedną z wartości funkcji celu policzoną w
poprzedniej iteracji. Do tego celu wykorzystuje się ciąg
Fibonacci’ego,
którego wyrazy zdefiniowane są następująco:
dla
.
Kilka jego pierwszych wyrazów to: 1, 1, 2, 3, 5, 8, 13, ...
Znajdź n takie, że
Oblicz
i
Jeżelito
podstaw:
W przeciwnym przypadku:
Idź do kroku 3. jeśli
i