Розділ 9. Числове розв’язання задач оптимізації

Короткі теоретичні відомості

 

Нехай функція f (x ₁, x ₂,..., x_n) — неперервно диференційована в області D. Нехай відомо, що в D існує точка , в якій виконуються співвідношення:

(9.1)

Розв’язання системи (9.1) дозволяє визначити невідомі характеристичні точки. Потім, використовуючи достатні умови мінімуму, варто виділити ті точки області D, у яких досягається локальний мінімум. Порівнявши значення цільової функції в точках локального мінімуму, треба вибрати точку з мінімальним значенням локального мінімуму, тобто визначити глобальний мінімум f (x ₁, x ₂,..., x_n) у області D. Однак надійні й одночасно економні методи пошуку глобального мінімуму на цей час невідомі.

Необхідну умову екстремуму (9.1) – умову стаціонарності можна записати у вигляді

,

де – градієнт цільової функції в точці .

Слід відзначити, що на відміну від нелінійних рівнянь f (x) = 0, які можна розв’язати з точністю e, задачу можна тільки з точністю .

 

Методи одновимірного пошуку

Нехай f (x) – дійсна функція одного аргументу, визначена на відрізку [ a, b ]. Припустимо, що існує єдине значення c, таке, що f (c) – мінімум f (x) на відрізку [ a, b ], і що f (x) строго спадає для x < c і строго зростає для x > c. Така функція називається унімодальною.

Метод золотого перерізу полягає в розбитті інтервалу [ a, b ] точкою x ₁ на дві частини таким чином, щоб відношення довжини всього інтервалу до більшої частини дорівнювало відношенню більшої частини до меншої:

Легко перевірити, що золотий переріз утворюють дві точки

x ₁ = a + (1 – d)(b – a);

x ₂ = a + d(b – a),

де .

Точка x ₁ утворює золотий переріз відрізка [ a, x ₂], а точка x ₂ – інтервалу [ x ₁, b ]. Тому на інтервалі, що залишився, потрібно визначити тільки одну точку, що утворює золотий переріз. На кожному кроці довжина першого інтервалу невизначеності дорівнює приблизно 0,618 довжини попереднього інтервалу.

Алгоритм методу золотого перерізу:

1. Обчислити:

x ₁ := a + (1 – d)(b – a);

x ₂ := a + d(b – a).

2. Обчислити f(x1), f(x2).

3. Якщо f (x ₁) < f (x ₂), то покласти b:= x ₂, x ₂ := x ₁, f (x ₂):= f (x ₁),
x ₁ := a + (1 – d)(b – a) і обчислити f (x ₁), інакше покласти a:= x ₁, x ₁ := x ₂, f (x ₁):= f (x ₂), x ₂ := a + d(b – a) і обчислити f (x ₂).

4. Якщо , то перейти до кроку 3, інакше .

Наприклад: Знайти мінімум цільової функції методом золотого перерізу.

Легко бачити, що точним розв’язком цієї задачі оптимізації є точка x =1.

Оберемо інтервал пошуку x Î[0,3], тобто a = 0, b = 3. Обчислимо x ₁ та x ₂.

;

.

Знайдемо значення цільової функції в точках x ₁ та x ₂.

,

.

Оскільки , то . Таким чином інтервал пошуку звузився до x Î[0, 1,85410].

Для нового інтервалу значення x ₂ та обчислювати не треба. Їх можна взяти з попередньої ітерації:

, .

Обчислимо нове значення x ₁ та :

;

.

Оскільки , то . Тобто інтервал пошуку звузився до x Î[0,708204, 1,85410]. Таким чином з кожною ітерацією інтервал пошуку звужується в околі точного розв'язку.