Optymalizacja jednowymiarowa (metody eliminacji)

Zadanie:

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.

Idea rozwiązania:

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 .

Metoda dychotomii

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).

Metoda złotego podziału

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ń.

Metoda Fibonacci

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, ...

  1. Znajdź n takie, że

  2. Oblicz i

  3. Jeżelito podstaw:

    W przeciwnym przypadku:

  1. Idź do kroku 3. jeśli i