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