Метод конфігурацій Розенброка

Метод конфігурацій Розенброка заснований на пошуку мінімуму вздовж ліній розриву похідних і часто виявляється ефективним, коли інші методи не дозволяють отримати рішення. Його нерідко називають «методом обертання вісей координат», оскільки дослідження в околі вибраної точки ведеться саме таким методом. На відміну від попередніх методів, в яких вхідним змінним надають незалежні прирости, в методі Розенброка система координат повертається так, щоб одна з вісей була направлена вздовж лінії розриву похідних, положення якої визначається в результаті попереднього дослідження. Решта осей утворять з нею ортогональну систему координат.

Метод Розенброка заснований на припущенні про унімодальність цільової функції і перевизначений для відшукання мінімуму функції багатьох змінних вигляду

(13)

при відсутності обмежень. На рис. 9 показана схема алгоритму, який використовується в цьому методі.

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

(14)

де . Якщо ж нове значення виявляється більше за попереднє, то зсув вважається невдалим і наступний крок визначається по формулі

(15)

де .

Рисунок 9 - Блок-схема алгоритму метода конфігурацій Розенброка

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

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

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

1. Що таке градієнт і антиградієнт? Поясніть математично.

2. В чому полягає сутність градієнтних методів пошуку оптимуму цільової функції.

3. Поясніть узагальнену математичну модель градієнтних методів пошуку оптимуму функції.

4. Покажіть, що функція є випуклою.

5. Знайдіть і класифікуйте стаціонарні точки функції .

6. Проведіть аналіз визначеності наступних квадратних форм: