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

У методі покоординатного спуску в області D задають початкове наближення Х ₀ = і послідовно проводять одновимірні пошуки вздовж різних напрямів, паралельних координатним осям.

Для цього розглядають функцію однієї змінної і методом одновимірного пошуку знаходять Значення х ₁, що відповідає мінімуму, позначають через :

Далі розглядають функцію однієї змінної і знаходять Значення , що відповідає мінімуму функції, позначають через . При цьому

Після n кроків одержують

У результаті n кроків покоординатного спуску відбувається перехід із точки Х ₀ у точку Х ₁ =

Якщо f (Х ₀) = f (Х ₁), то Х ₀ є точкою мінімуму f (Х). Якщо f (Х ₀) > f (Х ₁), то виконують наступний крок покоординатного спуску, в якому за початкову точку взято Х ₁. У результаті знаходять точку Х ₂ і так далі. Цей процес продовжують доти, доки не виконають умову закінчення ітерацій, наприклад:

,

де e – задана відносна точність розв’язку.

Координати нової точки знаходять за виразом

де h – крок пошуку; A _i – випадковий напрямок.

Точка X _{i +1} вважається обчисленою, якщо . Інакше роблять спробу досягти успіху або за рахунок зміни кроку, або за рахунок зміни напряму на протилежний. Якщо всі спроби виявляються невдалими, то вибирають новий випадковий напрям пошуку. Випадковий напрям пошуку знаходять за допомогою випадкової точки A = [ a ₁, a ₂,…, a_n ], компоненти якої є випадковим значенням, рівномірно розподіленим на відрізку [–1, 1].

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

(9.2)

методом покоординатного спуску.

Легко бачити, що цільова функція (9.2) досягає мінімуму в точці .

Оберемо початкове наближення та розглянемо функцію однієї змінної

.

Знайдемо мінімум функції використовуючи один із методів одномірного пошуку, наприклад метод золотого перетину. Результатом є . Тепер розглянемо функцію

.

Мінімум цієї функції є . В результаті першої ітерації отримуємо наступне наближення: . Легко впевнитись, що , а також в тому, що точка X ₁ ближче розташована до c ніж X ₀.

Проведемо ще одну ітерацію.

.

.

.

Тоді

Як видно, точка X ₂ ще більш наблизилась до c.

 

Градієнтні методи

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

Усі градієнтні методи використовують указані особливості поведінки градієнта, а стратегія їх пошуку будується на рекурентному виразі типу:

де h – величина кроку; а S _i – одиничний вектор напряму пошуку на i- му кроці.

Спосіб вибирання кроку, напряму чи того й другого одночасно визначає сутність методу.

У разі пошуку мінімуму цільової функції потрібно рухатися в напрямі, протилежному градієнту функції точки f (X). Тому напрям

дозволяє одержати таку рекурентну формулу для методу градієнтного спуску:

. (9.3)

Особливістю методу найшвидшого спуску є рух з оптимальним кроком, розрахованим за допомогою одновимірної мінімізації цільової функції по h уздовж антиградієнтного напряму. Дійсно, якщо в точці X _i напрям пошуку визначений, то значення цільової функції в наступній точці X _{i +1} є функцією кроку спуску:

.

Тому крок h можна вибрати так, щоб максимально зменшила своє значення:

.

Вибір оптимального кроку зводиться до розв’язання одновимірної оптимізації функції g (h).

Алгоритм методу найшвидшого градієнтного спуску:

1. Обчислити всі частинні похідні цільової функції.

2. Знайти один з методів одновимірного пошуку оптимального кроку уздовж антиградієнтного напряму. Крок h визначають з умови мінімуму функції по h.

3. Обчислити координати нової точки за формулою (9.3).

4. Якщо умова припинення пошуку не виконується, то перейти до кроку 1.

Наприклад: Знайти мінімум цільової функції (9.2) методом найшвидшого градієнтного спуску.

Знайдемо градієнт цільової функції

. (9.4)

Оберемо початкове наближення .

Тоді

Знайдемо мінімум функції використовуючи один із методів одномірного пошуку, наприклад метод золотого перетину. Результатом є . Тоді

.

Виконаємо ще одну ітерацію.

;

;

;

.

Таким чином

.

 

Контрольні завдання

1. Вибрати одновимірну цільову функцію відповідно до свого варіанта.

2. Знайти інтервали унімодальності цільової функції.

3. В межах інтервалу унімодальності знайти мінімум функції методом золотого перетину.

Варіанти завдань

1.	.	2.	.
3.	.	4.	.
5.	.	6.	.
7.	.	8.	.
9.	.	10.	.
11.	.	12.	.
13.	.	14.	.
15.	.	16.	.
17.	.	18.	.
19.	.	20.	.
21.	.	22.	.
23.	.	24.	.
25.	.	26.	.
27.	.	28.	.
29.	.	30.	.

 

4. Вибрати двовимірну цільову функцію відповідно до свого варіанта.

5. Знайти мінімум функції методом покоординатного спуску.

6. Знайти мінімум функції методом градієнтного спуску.

7. Порівняти результати.

Варіанти завдань

1.	.	2.	.
3.	.	4.	.
5.	.	6.	.
7.	.	8.	.
9.	.	10.	.
11.	.	12.	.
13.	.	14.	.
15.	.	16.	.
17.	.	18.	.
19.	.	20.	.
21.	.	22.	.
23.	.	24.	.
25.	.	26.	.
27.	.	28.	.
29.	.	30.	.