Методи прямого пошуку для оптимізації унімодальних функцій якості без обмежень

      у якій щодо функції f: [a, b]® R передбачається тільки, що на цьому відрізку вона має єдиний мінімум x*, причому зліва від x* функція монотоно спадає, а праворуч — зростає (такі функції називаються унімодальными). Безперервність f не передбачається.

      Основна властивість унімодальних функцій така. Якщо ми знаємо значення f у точках x¹ і x² відрізка [a, b], x¹ < x², то ми можемо виразно сказати на якому з відрізків [a, x²], [x¹, x²], [x¹, b] лежить мінімум x* функції f (див. рис. 1).

 
Рис. 1

      У реальності ми не можемо розташовувати  пробні точки, тобто  точки, у яких ми обчислюємо значення функції, на як завгодно близькій відстані один від одної. Тому ми будемо припускати, що ця відстань не менша фіксованого числа e > 0.

      Всі описувані нижче методи вказують на відрізок, на якому гарантовано лежить точка x*. Цей відрізок називають відрізком (чи інтервалом) невизначеності Таким чином, якщо як наближене значення x* узяти центр цього відрізка, то похибка методу є половина довжини відрізка невизначеності.

 

3. Опис методів  розв’язку задачі

1. Метод дихотомії

Цей метод  є аналогом відомого методу дихотомії (половинного розподілу) пошуку рішення рівняння F(x) = 0 на відрізку і виглядає так. Позначимо через Lⁿ = [aⁿ, bⁿ] відрізок, що виходить на n-ому кроці (природно, L⁰ = [a, b]). Перехід від Lⁿ до Lⁿ⁺¹ зводиться до розміщення на Lⁿ двох пробних точок xⁿ і yⁿ так, щоб відстань між ними була рівна e і вони були симетричні щодо центра відрізка:

і вибору в якості Lⁿ⁺¹ відрізка [aⁿ, yⁿ], якщо f(xⁿ) £ f(yⁿ) і [xⁿ, bⁿ] у противному випадку. Таким чином, кожен крок вимагає двох обчислень функції і за n обчислень (n парне) ми одержуємо відрізок невизначеності довжини

де  l = b - a — довжина початкового відрізка.

Наприклад, якщо l = 1 і e << 1, то для одержання відрізка довжини 10^-6 потрібно порядку 40 обчислень функції.

2. Методи  золотого перетину і  Фібоначчі.

Ці методи ґрунтуються на тому самому алгоритмі  переходу до наступної пробної точки і відрізняються лише способом вибору першої точки. У результаті кожного кроку (додавання однієї пробної точки) ми одержуємо відрізок Lⁿ = [aⁿ, bⁿ] з однієї "старою" пробною точкою xⁿ ÏÐÎ (aⁿ, bⁿ). "Нова" пробна точка yⁿ визначається як точка симетрична xⁿ щодо центра відрізка Lⁿ:

Потім, у залежності від того, яка з нерівностей f(xⁿ) £ f(yⁿ) чи f(xⁿ) > f(yⁿ) виконується, у якості Lⁿ⁺¹ вибирається відрізок [aⁿ, yⁿ], чи [xⁿ, bⁿ] (тут ми вважаємо для визначеності, що xⁿ < yⁿ), а в якості старої пробної точки xⁿ⁺¹ вибирається або xⁿ, або yⁿ.

У методі золотого перетину x⁰ поділяє відрізок [a, b] за правилом золотого перетину:

де t — позитивний корінь рівняння

(золотий перетин): t = (1 + Ö5)/2 » 1.618). Таким чином, l⁰ = l¹t. Але тоді l² = l⁰ - l¹ = l¹(t- 1) = l₁/t, т. е. l¹ = l²t.

Тому після n + 1 експерименту

Зокрема, для зменшення відрізка невизначеності в 10⁶ разів потрібно провести 29 обчислень функції (порівн. з 40 обчисленнями в методі дихотомії).

У методі Фібоначчі спочатку задається число n обчислень функції і потім перша пробна точка береться таким чином, щоб остання пара експериментів давала відрізок невизначеності найменшої довжини, тобто  щоб останні дві точки складали симетричну щодо центра відрізка пари, відстань між який дорівнює e. Таким чином,

З огляду на те, що 

одержуємо l^n-2 = 3lⁿ - e, l^n-3 = 5lⁿ- 2e, l^n-4 = 8lⁿ - 3e, l^n-5 = 13lⁿ - 5e і  т.д.  Індукцією по i легко доводиться, що

де  Fⁱ — так називані числа Фібоначчі, обумовлені співвідношеннями F⁰ = F¹ = 1, Fⁱ = F^n-1 + F^n-2, i = 2,3, ..., введені в XIII столітті Леонардом Пізанским (Фібоначчі) зовсім по іншому приводі.З (15) ми одержуємо, по-перше, довжину lⁿ відрізка невизначеності, обчислення, що виходить у результаті, f у n + 1 точках:

відкіля

і, по-друге, довжину відрізка l¹, що задає положення першої (стартової) точки:

(Fⁱ)² = F^i-1Fⁱ⁺¹ + (-1)ⁱ. Використовуючи цю тотожність, одержимо з (3) більш просте співвідношення, що визначає lⁿ:

Таким чином, щоб запустити метод Фібоначчі необхідно заздалегідь знати кількість точок, у яких буде обчислюватися функція f.

Висновки

Метод Фібоначчі є найкращим алгоритмом у класі методів прямого пошуку, зокрема, у порівнянні з методом золотого перетину, за те саме число кроків він дає відрізок невизначеності у t^2/Ö5 » 1.17 раз менший. На практиці частіше використовують перший з них, оскільки виграш у методі Фібоначчі не великий, а необхідність заздалегідь знати число n обчислень функції найчастіше обтяжна.