Лабораторна робота № 4. Градієнтні методи оптимізації функцій багатьох змінних

 

Мета: дослідити використання градієнтних методів для розв’язання задач багатомiрної оптимізації.

 

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

Градієнтні методи відносяться до методів першого порядку. Особливість цих методів – це використання  градієнта.

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

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

 

 

де     k – номер ітерації;

 Х(k) – поточне наближення до розв’язку;

 λ(k) – параметр, який характеризує довжину кроку;

f(Х(k)) – напрямок пошуку в n-мірному просторі керованих змінних.

Градієнтний метод є послідовністю кроків, кожний з яких складається з двох операцій:

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

2.     переміщення у вибраному напрямку на задану відстань. 

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

Метод найшвидшого спуску є модифікацією градієнтного метода. Він  відрізняється від градієнтного тим, що градієнт обчислюється тільки  в початковій точці і рух у напрямку антиградієнта продовжується до тих пір, поки зменшується значення цільової функції f(Х). Вибір кроку λ під час переходу від точки Х(k) в Х( k+1) визначається згідно умови:

 

 

тобто на кожному кроці розв’язується одномірна задача мінімізації.

Метод найшвидшого спуску має два недоліки: по-перше, методу властива поступова збіжність до точки мінімуму внаслідок малого f(Х) в околі цієї точки, по-друге, необхідно розв’язувати задачу одномірної оптимізації – обирати на кожному кроці оптимальне значення λ (k). Головна перевага цього методу полягає в тому, що йому властива стійкість та простота обчислень. Використовують цей метод тоді, коли цільову функцію можна добре апроксимувати лінійною залежністю.

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

1. Скласти схему алгоритму та розробити програму пошуку локального мінімуму функції  градієнтним методом. Вихідні дані брати з табл. 6.4 у відповідності до варіанта.

 

Таблиця 6.4. Варіанти завдань

Варіант

Цільова
функція

Початкова
точка

Початкова довжина кроку

Точність
рішення

Метод
оптимізації

1

Флетчера-Рівса

2

Найшвидшо го спуску

3

Градієнтного спуску

4

Флетчера-Рівса

5

Найшвидшо го спуску

6

Градієнтного спуску

 

2. Результати пошуку оптимуму функції представити таблицею вигляду:

Крок пошуку

Поточна точка

Значення функції

Поточна довжина кроку

Градієнт

Норма градієнта

1

 

 

 

 

 

. . .

 

 

 

 

 

 

 

 

 

 

. . .

 

 

 

 

 

 

 

 

 

 

 

3. Достовірність отриманих результатів перевірити, використовуючи математичний пакет MathCAD.

4. Зробити висновки. Оформити звіт.

 

Склад звіту

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

2.     Завдання.

3.     Блок-схема та лістинг програми.

4.     Результати оптимізації за розробленою програмою.

5.     Результати дослідження у MathCAD.

6.     Висновки.

 

 


Рис. 6.3. Приклад програми пошуку оптимуму функції двох змінних у MathCAD

 

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

1. Особливості алгоритмів оптимізації багатомірних функцій.

2. Що таке градієнт та антиградієнт?

3. У чому полягає суть градієнтних методів пошуку оптимуму?

4. Чим градієнтний метод відрізняється від методу найшвидшого спуску?

5. Суть методу Флетчера-Рівса.

 

Список використаної літератури:

1.  Методичні вказівки до виконання лабораторних робіт з курсу: «Методи оптимізації» для студентів 5-го курсу денної форми навчання спеціальності 7.091401 «Системи управління і автоматики» // fliphtml5.com/oktx/basic

2.     Методи оптимізації складних систем. Навчальний посібник. / І.В.Кузьмін, М.М.Биков, С.М.Москвіна. – Вінниця: ВДТУ, 2003. – 164 с.

3.     Банди Б. Методы оптимизации. Вводный курс. – М.:”Радио и связь”, 1988. – 128 с.

4.     Дегтярев Ю.И. Методы оптимизации: учебное пособие. – М.: Советское радио, 1980. – 272 с.

5.     Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. – М.: Наука, 1991. – 448 с.

6.     Полак Е. Чисельні методи оптимізації. – М.: Мир, 1974.