Основні поняття та визначення

МЕТОДИ ОПТИМІЗАЦІЇ БАГАТОВИМІРНИХ ЗАДАЧ

Лекція № 14

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

На перший погляд може показатися, що відмінність між методами багатовимірного і одномірного пошуку полягає лише в тому, що перші вимагають більшого об'єму обчислень, і, що в принципі методи, які придатні для функцій однієї змінної, можна застосовувати і для функцій багатьох змінних. Однак це не так, оскільки багатовимірний простір якісно відрізняється від одномірного. Передусім зі збільшенням числа вимірів зменшується ймовірність унімодальності цільової функції. Крім того, безліч елементів, які утворюють багатовимірний простір, значно потужніші множини елементів одномірного простору. Об'єм обчислень, які необхідні для звуження інтервалу невизначеності в багатовимірному просторі, є степеневою функцією, показник якої рівний розмірності простору. Так, якщо в випадку одномірного простору для досягнення =0,1 вимагається обчислити 19 значень цільової функції, то у випадку двомірного простору це число складає 361, тримірного – 6859, чотиримірного – 130321, а п'ятимірного – 2476099! Оскільки при виборі оптимальної конструкції нерідко потрібно мати діло з п'ятьма і більше змінними, серйозність труднощів, зумовлених багатовимірністю, стає очевидною.

Спочатку розглянемо питання аналізу (в статиці( з використовуванням положення лінійної алгебри і диференційного обчислення, а також умови, які (в достатньо загальних можливих випадках) дозволяють ідентифікувати точки оптимуму. Такі умови використовують для перевірки обраних точок і дають можливість з’ясувати, чи є ці точки точками мінімуму чи сідловими точками. При цьому задача вибору вказаних точок залишається за межами цього аналізу; основна увага віддається розв’язанню питання про те, чи відповідають досліджувані точки розв’язку багатовимірної задачі безумовної оптимізації, у якій вимагається мінімізувати f(x) , xОR^N, (14.1) коли обмеження відсутні на х , де х - вектор керованих змінних розмірності N, f — скалярна цільова функція. Звичайно допускається, що х_і (для всіх значень = 1,2,3,...,N) можуть приймати будь-які значення, хоча інколи в практичних застосуваннях область значень х обирається в вигляді дискретної множини. Крім того, часто зручно допускати, що функція f і її похідні існують і неперервні скрізь, хоча ми знаєм, що оптимуми можуть досягати в точках розриву f чи її градієнта

. (14.1)

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

Рисунок 14.1 - Лінії рівняння мультимодальної функції

f(x)=[x12+x2-11]2+[x1+x22-7]2, (14.2)

неважко побачити , що ця функція має чотири різних мінімуму.

Далі підійдемо до питання аналізу (в динаміці(, яке формулюється таким чином: якщо точка х⁽⁰⁾ не задовольняє вимогам, які

Функція Хіммельблау:

(14.3)

визначаються критеріями оптимальності, то як отримати (добре( нове наближення х⁽¹⁾ до розв’язку х? Спроба дати відповідь на це питання приводить до необхідності розгляду ряду методів. Методи, які розглядаються, класифікуються у відповідності з тим, чи використовується інформація про похідні досліджуваної функції.