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

Рис. 2.3. Схема метода покоординатного спуска

 Припустимо необхідно знайти найменше значення цільової функції f (M) =f (x ₁, x ₂, …, x_n). На рис. 2.3 через М позначена точка n -вимірного простору з координатами x ₁, x ₂, …, x_n: M= (x ₁, x ₂ ,..., x_n).

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

1. Обираємо початкову точку М ₀ = (x ₁⁰, x ₂⁰ ,..., x_n ⁰) та обчислюємо функцію f при фіксованих значеннях усіх змінних, крім першої: f (x ₁, x ₂⁰, x ₃⁰ ,..., x_n ⁰). Тоді вона перетвориться у функцію однієї змінної x ₁.

2. Змінюючи x ₁ на величину D (при фіксованих значеннях інших координат) будемо рухатись від початкової точки x ₁ =x ₁⁰ в бік зменшення функції, поки не дійдемо до її мінімуму при x ₁ =x ₁¹, після якого вона починає збільшуватись.

3. Точку с координатами (x ₁¹, x ₂⁰, x ₃⁰ ,..., x_n ⁰) позначимо через М ₁, при цьому f (M ₀)³ f (M ₁).

4. Фіксуємо тепер змінні: x ₁ =x ₁¹, x ₃ = x ₃⁰ ,..., x_n=x_n ⁰ та розглядаємо функцію f як функцію однієї змінної x ₂: f(x ₁¹, x ₂², x ₃⁰ ..., x_n ⁰).

5. Змінюючи x ₂ на величину D (при фіксованих значеннях інших координат), будемо знову рухатись від початкового значення x₂=x₂⁰ в бік зменшення функції, поки не дійдемо до мінімуму при x₂=x₂¹.

6. Точку с координатами { x ₁¹, x ₂¹, x ₃⁰ ... x_n ⁰} позначимо через М ₂, при цьому f (M ₁)³ f (M ₂).

Аналогічні дії виконуються за всіма координатами.

Порядок виконання роботи

2.1. За П. 1.1. знайти мінімум заданої функції двох змінних виходячи з умови f ¢(x, y)=0. Дані взяти з табл. 2.1.

2.2. Побудувати графік функції з табл. 2.1 поблизу точки екстремуму.

2.3. За П. 1.2. методом покоординатного спуску знайти мінімум заданої функції двох змінних. Пошук почати з точки M ₀ (x ⁰, y ⁰). Дані взяти з табл. 2.2.

2.4. Побудувати графік функції з табл. 2.2 поблизу точки екстремуму.

2.5. Провести порівняльний аналіз вивчених методів оптимізації. Зробити висновки по роботі.

3. Звіт має містити результати розрахунків по П. 2.1, 2.3, графіки функцій поблизу точки екстремуму по П. 2.2, 2.4, висновки по роботі.

Варіанти

Таблиця 2. 1

№  варіанта	Функція f (x, y)	№  варіанта	Функція f (x, y)
1.		6.
2.		7.
3.		8.
4.		9.
5.		10.

Таблиця 2. 2

№ варіанта	Функція f (x, y)	Координати початкової точки M 0 (x 0, y 0)
1.		(1; 1)
2.		(2; 2)
3.		(2; 2)

Продовження таблиці 2.2

4.		(2; 2)
5.		(2; 2)
6.		(2; 2)
7.		(2; 2)
8.		(2; 2)
9.		(0,5; 0,5)
10.		(1; 1)

Контрольні питання

1. Назвати необхідну та достатню умову локальної оптимальності функції двох змінних.

2. Пояснити суть оптимізації методом покоординатного спуску.

3. Переваги та недоліки методу покоординатного спуску.

4. Алгоритм знаходження локального мінімуму функції двох змінних при безумовній оптимізації.

Лабораторна робота № 2.2

ДОСЛІДЖЕННЯ ЧИСЕЛЬНИХ МЕТОДІВ ОПТИМІЗАЦІЇ

Мета роботи – навчитися застосовувати чисельні методи оптимізації унімодальних функцій.

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

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

При рішенні задач використовуються наступні позначення:

Δ _i = [ a_i, b_i ] и L_i = b_i − a_i, i = 1, 2, …, − відповідно відрізок локалізації та його довжина після i обчислень значень f (x), Δ₀= [ a, b ] та L ₀= b − a; N – кількість обчислень значень f (x).

Далі розглянуто метод дихотомії, метод Фібоначчі та метод золотого перетину. Для кожного з цих методів на j -й, j =1, 2, …, ітерації розглядається пара точок  и   при цьому . Значення функції в цих точках будуть позначатися відповідно  та .