Тема 2 «Методи оптимізації в задачах великої розмірності та методи багатокритеріальної оптимізації»

План лекції

1. Методи оптимізації в задачах великої розмірності.

2. Задачі та методи багатокритеріальної оптимізації.

1. Методи оптимізації багатовимірних задач

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

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

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

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

Градієнтні методи

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

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

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

Щоб краще зрозуміти ідею градієнтних методів, більш конкретно зупинимося на властивостях градієнтів. Розглянемо систему незалежних одиничних векторів е₁, е₂, е₃, …, е_N, які направлені в здовж вісей координат x₁, x₂, x₃, …, x_N, які є в той же час проектними параметрами.

Вектор градієнта довільної цільової функції F = (x₁, x₂, x₃, …, x_N,) має вигляд

,

де частинні похідні обчислюються в точці, яка розглядається. Цей вектор направлений вверх, в напрямку підйому; обернений йому вектор вказує напрямок спуска. Одиничний вектор градієнта часто представляють у вигляді

,

де .(1)

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

.

Тут - невелике зміщення в напрямку х_i. Цю формулу часто називають “наближенням січної”. Отриману інформацію про напрямок градієнта можна використовувати різним чином для побудови алгоритму пошуку.

Постановка задачі оптимізації градієнтними методами: мінімізація функції F (x₁, x₂, x₃, …, x_N) з N проектними параметрами за допомогою ЕОМ розв’язується ітераційними методами. Розв’язок задачі починається з вибору початкових значень (i = 1, 2, …, N), які за звичай визначаються із умов розв’язуємої задачі, і потім будують послідовні наближення, використовуючи ітераційну формулу

, (i = 1, 2, …, N; j = 0, 1, 2, …),(2)

де - величина кроку ітерації по кожному з параметрів ;

- параметр вибору “напрямку”, який звичайно визначається за формулою (14.12).

Дана формула забезпечує збіжність досліджуваної функції до деякого рішення при . Величина кроку на кожній j-ій ітерації визначається одним з методів оптимізації однопараметричної оптимізації, наприклад методом ділення відрізка навпіл або методом “золотого перетину” або Фібоначчі.