МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
/
Звіт
до лабораторної роботи № 5
з курсу: «Методи синтезу та оптимізації»
на тему:
«Використання градієнтних методів для дослідження задач багатопараметричної оптимізації»
Мета роботи: вивчити основні градієнтні методи для розв’язування двовимірних задач оптимізації.
1.Короткі теоретичні відомості:
Прямі методи дозволяють отримати розв’язок задачі оптимізації, використовуючи при обчисленнях тільки значення цільової функції. Роль цих методів безперечна, оскільки для багатьох практичних інженерних задач інформація про значення цільової функції є єдиною достовірною інформацією, якою володіє дослідник. З іншої сторони, при використанні навіть найефективніших прямих методів для отримання розв’язку інколи вимагається надзвичайно багато обчислень значень функції. Ця обставина поряд з цілком природнім прагненням реалізувавти можливості знаходження стаціонарних точок (тобто точок, які задовільняють необхідній умові першого порядку) приводить до необхідності розглядати методи, які грунтуються на використанні градієнта цільової функції.
Надалі будемо вважати, що сама функція , її перша похідна , та друга похідна існують і неперервні. Методи з використанням як перших, так і других похідних є дуже поширеними в задачах пошуку екстремумів як випуклих так і невипуклих функцій. В методах, які використовують значення першої похідної (градієнта) функції, передбачається, що компоненти градієнта можуть бути записані в аналітичному виді або з достатньо високою точністю пораховані з допомогою числових методів. Всі описані методи грунтуються на ітераційній процедурі, яка реалізується у відповідності з формулою
, (1)
де - поточне наближення до розв’язку , - параметр, який характеризує довжину кроку; - напрямок пошуку в - вимірному просторі управляючих змінних . Метод визначення і на кожній ітерації пов’язаний з особливостями методу, що використовується. Як правило, вибір здійснюється шляхом розв’язування задачі мінімізації в напрямку . Тому при реалізації даних методів необхідно використовувати ефективні алгоритми одновимірної мінімізації.
Квазіньютонівські методи (метод Девідона-Флетчера-Пауелла)
Ці методи аналогічні методам попередньго пункту, оскільки також грунтуються на методах квадратичних функцій. Пошук розв’язку здійснюється по системі спряжених напрямків, але квазіньютонівські методи, володіючи перевагами методу Ньютона, використовують тільки перші похідні. У всіх методах цього типу напрямок пошуку задається за формулою (1), в якій записується у вигляді
, (20)
де - матриця порядку , яка носить назву метрики. Для її апроксимації використовується наступне рекурентне співвідношення
, (21)
де - коректуюча матриця.
Одним з найбільш відомих методів даного класу є метод Девідона-Флетчера-Пауела, в якому
.
Алгоритм забезпечує зменшення цільової функції при переході від ітерації до ітерації. Він є стійким і успішно використовується при розв’язуванні найрізноманітніших задач, які виникають на практиці. Головним недоліком методу є необхідність зберігати в пам’яті компютера матрицю порядку .
2.Індивідуальне завдання:
(Варіант 13).
113.
,
Метод Девідона-Флетчера-Пауела
3.Результат виконання:
З допомогою методу Девідона-Флетчера-Пауела знайти точку мінімуму функції
,
якщо .
Розв’язок
=(12*x-8*y+1;-8*x+6*y+4).
Крок 1. Покладемо .
Крок 2. Пошук вздовж прямої:
,
.
Крок 3. ,
,
,
,
=g1-s0.
g1==(6;0)
,
,
,
,
s(1)=-A(1)*=-(7407/22;-4896/11).
Крок 4. Пошук вздовж прямої:
,
.
Таким чином, . Розв’язок отримано в результаті проведення двох одномірних пошуків, оскільки цільова функція квадратична і похибки заокруглення відсутні.
Перевірка:
package lab_4MSO;
import java.math.*;
public class Max {
public static void main(String [] args)
{
double A=0,B=0,C=0;
double x=0,y=0;
double dx=12*x-8*y+1;
double dy=-8*x+6*y+4;...
