Лабораторна робота
№ 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. Висновки.
![]() |
![]() |
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.