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

Знову розглянемо квадратичну функцію

q(x)=4х₁²+3х₂²-4х₁х₂+х₁

Нехай задано дві точки х₍₁₎=[0, 0]^Т, х₍₂₎=[1, 0]^Т і напрям d=[1, 1]^Т.

Перший пошук проводиться вздовж прямої х=[0, 0]^Т + λ [1, 1]^Т і приводить до точки:

у₍₁₎ = [-1/6, -1/6]^Т,

(λ * = -1/6).

Другий пошук проводиться вздовж прямої х=[1, 0]^Т + λ [1, 1]^Т і дозволяє отримати точку: λ *=-5/6, відповідно

у₍₂₎=[1, 0]^Т – 5/6* [1, 1]^Т = [1, 0]^Т + [-5/6, -5/6]^Т = [1/6, -5/6]^Т

у₍₂₎=[1/6, -5/6]^Т

Згідно властивості паралельного підпростору напрям

у₍₂₎ - у₍₁₎ = [1/6, -5/6] - [-1/6, -1/6]^Т = [1/3, -2/3]^Т пов'язаний з d=[1, 1],

тобто за визначенням [1, 1]^Т C [1/3, -2/3]^Т =0.

Вище розглядалося, що в разі двох змінних, оптимум q(x) можна знайти шляхом проведення пошуку вздовж прямої заданого напряму (у₍₂₎-у₍₁₎). Цей факт не важко перевірити, оскільки мінімум q(x) вздовж прямої

х= [-1/6, -1/6]^Т + λ [1/3, -2/3]^Т

досягається в точці х* = [-3/16, -1/8]^Т, (λ = -1/16), яка збігається з раніше отриманим рішенням.

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

3.2.1 Написати програму, що реалiзує метод спряжених напрямків Пауелла.

3.2.2 За допомогою розробленої програми знайти мiнiмум функцiї (табл. 1.1).

3.2.3 Порiвняти методи Нелдера-Мiда, Хука-Дживса та Пауєлла за точнiстю знаходження оптимиму, кiлькiстю iтерацiй та часом роботи.

3.3 Зміст звіту

3.3.1 Сформульована мета роботи.

3.3.2 Алгоритм та програма, що реалізує метод Пауєлла.

3.3.3 Результати роботи програми.

3.3.4 Аналіз отриманих результатів і висновки.

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

3.4.1 До якого виду приводиться квадратична функція?

3.4.2 Як проводиться пошук оптимуму в просторі перетворених змінних?

3.4.3 Як знаходиться матриця перетворення?

ЛАБОРАТОРНА РОБОТА № 4 Градієнтні методи багатовимірної оптимізації

Мета роботи - вивчити градієнтні методи безумовної багатовимiрної оптимiзацiї.

4.1 Короткі теоретичні відомості

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

З іншого боку, при використанні навіть самих ефективних прямих методів для отримання рішення іноді необхідна надзвичайно велика кількість обчислень значень функції. Ця обставина разом з прагненням реалізувати можливості знахождення стаціонарних точок (точок, що задовольняють умові ) призводить до необхідності розгляду методів, які основані на використанні градієнта цільової функції. Вказані методи носять ітеративний характер, тому що компоненти градієнта виявляються нелінійними функціями керуючих змінних. Далі вважається, що , , існують та безперервні. Методи з використанням як 1-х, так і 2-х похідних проглядаються в їх зв‘язку з більш корисними методами.

Особливе значення приділяється застосуванню методів спряженних градієнтів, в основі яких лежать введені вище поняття спряженності напрямків і так званих квазиньютонових методів, які аналогічні методу Ньютона, але використовують інформацію тільки перших похідних. Припускається, що компоненти градієнта можуть бути записані в аналітичному вигляді або з достатньо високою точністю розрахунків за допомогою чисельних методів. Крім того, розглядаються способи чисельної апроксимації градієнтів. Всі методи, що описані, основані на ітераційній процедурі, яка реалізується у відповідності з формулою

(4.1),

де - поточне ближнє до рішення

- параметр, характеризуючий довжину кроку.

- напрямок пошуку в N – мірному просторі керуємих змінних .

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