Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Методи синтезу та оптимізації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Використання градієнтних методів для дослідження задач багатопараметричної оптимізації
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 5
з курсу “Методи синтезу та оптимізації”
для студентів базового напряму 6.08.04 “Компютерні науки”
ЗАТВЕРДЖЕНО
На засіданні кафедри САПР
Протокол № 1 від 28.08.2008 р.
ЛЬВІВ 2008
Використання градієнтних методів для дослідження задач багатопараметричної оптимізації. Методичні вказівки до лабораторної роботи № 5 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р.
Укладачі: Теслюк Василь Миколайович, к. т. н., доцент; Андрійчук Михайло Іванович, к. ф.-м. н., доцент.
Відповідальний за випуск: Ткаченко С. П., к. т. н., доцент.
Рецензенти: Каркульовський В. І., к. т. н., доцент,
Стех Ю. В., к. т. н., доцент.
1. МЕТА РОБОТИ
Вивчити основні градієнтні методи для розв’язування двовимірних задач оптимізації
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Градієнтні методи пошуку екстремумів
Прямі методи дозволяють отримати розв’язок задачі оптимізації, використовуючи при обчисленнях тільки значення цільової функції. Роль цих методів безперечна, оскільки для багатьох практичних інженерних задач інформація про значення цільової функції є єдиною достовірною інформацією, якою володіє дослідник. З іншої сторони, при використанні навіть найефективніших прямих методів для отримання розв’язку інколи вимагається надзвичайно багато обчислень значень функції. Ця обставина поряд з цілком природнім прагненням реалізувавти можливості знаходження стаціонарних точок (тобто точок, які задовільняють необхідній умові першого порядку) приводить до необхідності розглядати методи, які грунтуються на використанні градієнта цільової функції.
Надалі будемо вважати, що сама функція , її перша похідна , та друга похідна існують і неперервні. Методи з використанням як перших, так і других похідних є дуже поширеними в задачах пошуку екстремумів як випуклих так і невипуклих функцій. В методах, які використовують значення першої похідної (градієнта) функції, передбачається, що компоненти градієнта можуть бути записані в аналітичному виді або з достатньо високою точністю пораховані з допомогою числових методів.
Всі описані методи грунтуються на ітераційній процедурі, яка реалізується у відповідності з формулою
, (1)
де - поточне наближення до розв’язку , - параметр, який характеризує довжину кроку; - напрямок пошуку в - вимірному просторі управляючих змінних . Метод визначення і на кожній ітерації пов’язаний з особливостями методу, що використовується. Як правило, вибір здійснюється шляхом розв’язування задачі мінімізації в напрямку . Тому при реалізації даних методів необхідно використовувати ефективні алгоритми одновимірної мінімізації.
Метод Коші
Нехай в деякій точці простору управляючих змінних необхідно визначити напрямок найшвидшого локального спуску, тобто найбільшого локального зменшення цільової функції. Розкладемо цільову функцію в околі точки в ряд Тейлора
(2)
і відкинемо члени другого порядку і вище. Зрозуміло, що локальне зменшення цільової функції визначається другим доданком, оскільки значення фіксоване. Найбільше зменшення визначається вибором такого напрямку в (1), якому відповідає найбільша від’ємна величина скалярного добутку, який міститься в другому доданку розкладу. Із властивості скалярного добутку слідує, що вказаний вибір забезпечується при
, (3)
і другий доданок приймає вигляд
.
Даний випадок відповідає найскорішому локальному спуску. Тому в основі найпростішого градієнтного методу лежить формула
, (4)
де - заданий додатній параметр. Метод має два недоліки: по-перше, виникає необхідність вибору хорошого значення , і, по-друге, метод має повільну збіжність до точки мінімуму внаслідок малості в околі цієї точки.
Таким чином, доцільно визначати на кожній ітерації
, (5)
Значення обраховується шляхом розв’язку задачі мінімізації вздовж напрямку з допомогою того чи іншого методу одномірного пошуку. Розглянутий градієнтний метод носить назву методу найшвидшого спуску або методу Коші, оскільки Коші першим використав аналогічний алгоритм для розв’язування систем лінійних рівнянь.
Приклад 1. Метод Коші.
Розглянемо функцію
і використаємо метод Коші для розв’язку задачі її мінімізації.
Розв’язування. Насамперед, вирахуємо компоненти градієнта
, .
Для того, щоб застосувати метод найшвидшого спуску, задамо початкове наближення
і з допомогою формули (5) побудуємо нове наближення
Таблиця 1. Результати обчислень по методу Коші
1
-1.2403
1.1118
24.2300
2
0.1441
0.1447
0.3540
3
-0.0181
0.0309
0.0052
4
0.0021
0.0021
0.0000
Виберемо таким чином, щоб . Отже, . Далі знайдемо точку
обчисливши градієнь в точці і провівши пошук вздовж прямої. В Табл. 1 показано дані, які отримані при проведенні ітерацій на основі одновимірного методу пошуку по методу квадратичної інтерполяції. Блок-схему алгоритму наведено на Рис. 1.
Рис. 1. Блок-схема алгоритма методу Коші.
Метод Ньютона
Зрозуміло, що в методі Коші застосовується “найкраща” локальна стратегія пошуку з використанням градієнта. Але, рух в напрямку, протилежному градієнту, приводить в точку мінімуму лише в тому випадку, коли лінії рівня функції є колами. Таким чином, напрямок, протилежний градієнту, взагалі кажучи, не може бути прийнятним глобальним напрямком пошуку точок оптимума нелінійних функцій. Метод Коші грунтується на послідовній лінійній апроксимації цільової функції і вимагає обчислення значень функції і її перших похідних на кожній ітерації. Для того, шоб побудувати більш загальну стратегію пошуку, варто прийняти до уваги інформацію про другі похідні цільової функції.
Розкладемо цільову функцію в ряд Тейлора
.
Відкинувши всі члени розкладу третього порядку і вище, отримаємо квадратичну апроксимацію
, (6)
де - апроксимуюча функція змінної в точці . На основі квадратичної апроксимації функції сформуємо послідовність ітерацій таким чином, щоб в новій точці градієнт апроксимуючої функції перетворювався в нуль. Маємо
, (7)
звідки
. (8)
Послідовне застосування схеми квадратичної апроксимації приводить до реалізації оптимізаційного методу Ньютона за формулою
, (9)
використання якого продемонструємо на наступному прикладі.
Приклад 2. Метод Ньютона.
Знову розглянемо функцію з попереднього прикладу:
,
, ,
.
При із формули (9) одержуємо
,
отже,
,
що відповідає точному розв’язку.
Таким чином, задача мінімізації квадратичної функції розв’язується з допомогою однієї ітерації по методу Ньютона (при довільній початковій точці).
Модифікований метод Ньютона
Досвід показує, що при дослідженні неквадратичних функцій метод Ньютона не володіє високою надійністю. Справді, якщо точка знаходиться на значній віддалі від точки , то крок по методу Ньютона часто виявляється завеликим, що може привести до відсутності збіжності. Метод можна доволі просто модифікувати, для того, щоб забезпечити зменшення цільової функції від ітерації до ітерації і здійснювати пошук вздовж прямої, як в методі Коші. Така послідовність ітерацій будується у відповідності з формулою
, (10)
Вибір здійснюється таким чином, щоб
;
це гарантує виконання нерівності
.
Такий метод носить назву модифікованого методу Ньютона і у випадках, коли обчислення перших і других похідних не пов’язано з суттєвими труднощами, виявляється надійним і ефективним. Однак, при використанні модифікованого методу Ньютона на кожній ітерації виникає необхідність побудови і розв’язку лінійного рівняння, яке містить елементи матриці Гессе .
Метод Марквардта
Даний метод є комбінацією методів Коші і Ньютона, де вдало поєднуються позитивні характеристики обох методів. Разом з тим, при використанні методу Марквардта вимагається інформація про значення других похідних цільової функції. Вище було вказано, що градієнт вказує напрямок найбільшого локального збільшення функції, а рух в напрямку, протилежному градієнту, із точки , розміщеної на значній віддалі від точки мінімуму , як правило, не приводить до суттєвого зменшення цільової функції. З іншої сторони, напрямок ефективного пошуку в околі точки мінімуму визначається по методу Ньютона. Проста ідея об’єднання методів Коші і Ньютона була покладена в основу алгоритму, розробленого Марквардтом в 1963 р. У відповідності з цим методом, напрямок пошуку визначається рівністю
. (11)
При цьому в формулі (1) слід покласти , оскільки параметр дозволяє не тільки змінювати напрямок пошуку, але й регулювати довжину кроку. В формулі (11) - одинична матриця. На початковій стадії пошуку параметру надається велике значення (наприклад, 104), так що
. (12)
Таким чином, великим значенням відповідає напрямок пошуку . З формули (11) можна зробити висновок, що при зменшенні до нуля змінюється від напрямку, протилежного градієнту, до напряку, який визначається по методу Ньютона. Якщо після першого кроку отримана точка з меншим значенням цільової функції (тобто ), необхідно вибрати і реалізувати ще один крок; в протилежному випадку необхідно покласти, де , і знову реалізувати попередній крок. Нижче наведені кроки алгоритму.
Алгоритм Марквардта
Крок 1. Задати - початкове наближення до ; максимальну (допустиму) кількість ітерацій; параметр збіжності.
Крок 2. Покласти , .
Крок 3. Вирахувати компоненти .
Крок 4. Чи виконуєтьсмя нерівність
?
Так: перейти до кроку 11.
Ні: перейти до наступного кроку.
Крок 5. Чи виконується нерівність ?
Так: перейти до кроку 11.
Ні: перейти до наступного кроку.
Крок 6. Вирахувати .
Крок 7. Покласти .
Крок 8. Чи виконується нерівність
Так: пкерейти до кроку 9.
Ні: перейти до кроку 10.
Крок 9. Покласти і . Перейти до кроку 3.
Крок 10. Покласти . Перейти до кроку 6.
Крок 11. Друк результатів і зупинка.
Метод Марквардта характеризується відносною простотою, властивістю зменшення вагової функції від ітерації до ітерації, високою швидкістю збіжності в околі точки мінімуму , а також відсутністю процедури пошуку вздовж прямої.
Головним недоліком методу є необхідність обчислення і наступного розв’язування системи рівнянь, яка відповідає (11).
Метод спряжених градієнтів
Як говорилось раніше, метод Коші ефективний при пошуку на значних віддалях від точки мінімуму і погано “працює” в околі цієї точки, тоді як метод Ньютона не володіє високою надійністю при пошуку з віддаленої точки, але виявляється дуже ефективним в тих випадках, коли знаходиться поблизу точки мінімуму. Методи, які розглядатимуться нижче, мають обидві позитивні властивості і грунтуються на обчисленні значень тільки перших похідних.
Серед таких методів можна виділити клас алгоритмів, в основі яких лежить побудова спряжених напрямків. Нижче для отримання спряжених напрямків застосовується квадратична апроксимація і значень компонент градієнта.
Нехай в просторі управляючих змінних задані дві довільні різні точки і . Градієнт квадратичної функції дорівнює
. (13)
Позначення введене тут для зручності запису формули. Таким чином
,
.
Запишемо зміну градієнта при переході від точки до точки :
,
. (14)
Рівність (14) показує властивість квадратичних функцій, яка буде використана нижче.
Розгляд методу будемо проводити в припущенні, що цільова функція є квадратичною:
,
а ітерація проводиться по формулі (1), тобто
.
Напрямок пошуку на кожній ітерації визначається з допомогою наступних формул:
, (15)
, (16)
де . Оскільки після визначення системи напрямків проводиться послідовний пошук вздовж кожного із напрямків, то корисно нагадати, що в якості критерію закінчення одномірного пошуку як правило використовується умова
. (17)
Значення вибираються таким чином, щоб напрямок був -спряженим до всіх побудованих раніше напрямків пошуку. Розглянемо перший напрямок
і накладем умову спряженості його з
,
звідки .
На першій ітерації
;
отже,
Використовуючи останні формули і властивість квадратичних функцій (14), отримаємо вираз для
. (18)
Звідси випливає, що загальна формула для напрямків пошуку може бути записана у вигляді, запропонованому Флетчером і Рівсом
. (19)
Приклад 3. Метод Флетчера-Рівса.
Знайти точку мінімуму функції
,
якщо .
Розв’язок
Крок 1. ,
.
Крок 2. Пошук вздовж прямої:
.
Крок 3. :
, ().
,
,
,
.
Крок 4. Пошук вздовж прямої:
, справді
,
Тоді
, (перевірити самостійно),
З умови ,
,
.
Таким чином, . Розв’язок отримано в результаті проведення двох одномірних пошуків, оскільки цільова функція квадратична і похибки заокруглення відсутні.
Квазіньютонівські методи (метод Девідона-Флетчера-Пауелла)
Ці методи аналогічні методам попередньго пункту, оскільки також грунтуються на методах квадратичних функцій. Пошук розв’язку здійснюється по системі спряжених напрямків, але квазіньютонівські методи, володіючи перевагами методу Ньютона, використовують тільки перші похідні. У всіх методах цього типу напрямок пошуку задається за формулою (1), в якій записується у вигляді
, (20)
де - матриця порядку , яка носить назву метрики. Для її апроксимації використовується наступне рекурентне співвідношення
, (21)
де - коректуюча матриця.
Одним з найбільш відомих методів даного класу є метод Девідона-Флетчера-Пауела, в якому
.
Алгоритм забезпечує зменшення цільової функції при переході від ітерації до ітерації. Він є стійким і успішно використовується при розв’язуванні найрізноманітніших задач, які виникають на практиці. Головним недоліком методу є необхідність зберігати в пам’яті компютера матрицю порядку .
Приклад 4. Метод Девідона-Флетчера-Пауела.
З допомогою методу Девідона-Флетчера-Пауела знайти точку мінімуму функції
,
якщо .
Розв’язок
Крок 1. Покладемо .
Крок 2. Пошук вздовж прямої:
,
.
Крок 3. ,
,
,
,
,
,
,
,
.
Крок 4. Пошук вздовж прямої:
,
,
що співпадає з отриманим раніше розв’язком, отриманим методом Флетчера-Рівса.
.
Таким чином, . Розв’язок отримано в результаті проведення двох одномірних пошуків, оскільки цільова функція квадратична і похибки заокруглення відсутні.
3. КОНТРОЛЬНІ ЗАПИТАННЯ
3.1. Вкажіть характерні особливості градієнтних методів.
3.2. .Вкажіть переваги і недоліки методу Ньютона.
3.3. Вкажіть на відмінності методу Марквардта від стандартного методу Ньютона.
3.4. Перерахуйте характерні особливості методу сапряжених градієнтів.
3.5. Розповісти про квазіньютонівські методи на прикладі алгоритму Девідона-Флетчера-Пауелла.
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
4.1. Набрати, скомпілювати та запустити програму, що розв’язує завдання, видане викладачем.
4.2. Пояснити дії, які виконує програма.
4.3. Перевірити достовірність одержаного результату.
5. ЗМІСТ ЗВІТУ
5.1. Титульний лист.
5.2. Мета роботи, теоретичні відомості.
5.3. Лабораторне завдання.
5.4. Програма і результат її роботи.
5.5. Висновок.
6. ЛІТЕРАТУРА
1. Д. Химмельблау. Прикладное нелинейное программирование . Пер. с англ. М.: Мир, 1975. – 536 с.
2. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. – М.: Мир, 1986. – 352 с.
3. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 2. Пер. с англ. – М.: Мир, 1986. – 320 с.
4. Полак Э. Численные методы оптимизации. Пер. с англ. – М.: Мир, 1974. – 376 с.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора