Методи виключення інтервалів

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

Етап встановлення границь інтервалу. Вибирається вихідна точка, а потім на основі правила виключення будується відносно широкий інтервал, що містить точку оптимуму. Для цього, зазвичай, використовується евристичний метод, наприклад, метод Свенна, де (k+1) пробна точка визначається за рекурентною формулою

x_k+1 = x_k + 2^k D, k =0,1,2...

де x_o – довільно обрана початкова точка, а D – величина кроку, що підбирається. При цьому знак D визначається шляхом порівняння значень W (x), W (x_o   | D |) і W (x_o -| D |):

- якщо W (x_o -| D |) ³ W (x) ³ W (x_o + | D|), то D має позитивне значення;

- якщо W (x_o -| D |) £ W (x) £ W (x_o + | D |), то D має негативне значення;

- якщо W (x_o -| D |) ³ W (x) £ W (x_o + | D |), то точка мінімуму лежить в інтервалі x_o -| D | і x_o + | D | і пошук граничних точок завершений,

- якщо W (x_o -| D |) £ W (x) ³ W (x_o + | D |), то маємо протиріччя припущенню про унімодальність.

Приклад 5.1. W (x)=(100- x)², x_o =30, | D | =5.

Визначимо знак D:

W (30)=4900;

W (30+5)=4225;

W (30-5)=5625.

Виконується умова W (x_o -| D |) ³ W (x) ³ W (x_o + | D |), отже, D має позитивне значення; x^* =30.

x₁=x_o +2^0D = 35;

x₂=x₁ +2^1D = 45, W (45)=3025 < W (x₁) Þ x^* >35;

x₃=x₂ +2^2D = 65, W (65)=1225 < W (x₂) Þ x^* >45;

x₄=x₃ +2^3D = 105, W (105)=25 < W (x₃) Þ x^* >65;

x₅=x₄ +2^4D = 185, W (185)=7225 > W (x₄) Þ x^* <185.

Шуканий інтервал 65< x^* <185.

Етап зменшення інтервалу. Після того, як встановлені границі інтервалу, що містить точку оптимуму, можна застосовувати більш складну процедуру зменшення інтервалу пошуку з метою отримання уточнених оцінок координат оптимуму. Значення підінтервалу, що вилучають, на кожному кроці, залежить від розміщення проб­них точок х₁ та х₂ усередині інтервалу пошуку.

Оскільки місце знаходження точки оптимуму апріорі невідоме, доцільно припустити, що розміщення пробних точок повинно забезпечувати зменшення інтервалу в одному і тому ж відношенні. Крім того, з метою підвищення ефективності алгоритму слід вимагати, щоб це відношення було максимальним (мінімаксна стратегія пошуку).