ПРИВЕДЕННЯ ЗАДАЧІ ОПТИМІЗАЦІЇ З ОБМЕЖЕННЯМИ ДО ЗАДАЧІ БЕЗ ОБМЕЖЕНЬ ШЛЯХОМ ПОДВІЙНОГО ПРОСТОРОВОГО ПЕРЕТВОРЕННЯ

Анотація

В статті розглядається спосіб вирішення задач мінімізації і максимізації з обмеженнями із використанням алгоритмів для розв’язку задач оптимізації без обмежень шляхом побудови відображення з багатовимірного простору на багатовид, утворений обмеженнями задачі оптимізації. Ця конструкція не є опуклою на відміну від симплексу, але тим не менш саме вона є завершеною множиною комбінацій вершин, які утворюють простір варіантів задачі нелінійної оптимізації. Таким шляхом використання такої конструкції дозволяє розглядати задачу без обмежень і використовувати принципи безумовної оптимізації, що компенсує можливі обчислювальні труднощі через використання багатовиду. Фактично стаття є першим етапом до побудови універсальної методики розв’язання таких задач, і у процесі аналізу та класифікації модифікацій цього методу, було описано вимоги до якісних характеристик такого способу вирішення. Приведення задачі оптимізації з обмеженнями до задачі без обмежень шляхом подвійного просторового перетворення здійснюється операціями, які мали більше поширення в галузі комп’ютерної графіки з білінійними перетвореннями, що могло бути причиною недооцінки їх ефективності в задачах нелінійної оптимізації. Таким чином надається «друге дихання» для такого інструменту як метод оптимізації з обмеженнями шляхом лінійної апроксимації (COBYLA), котрий був ще навіть досить нещодавно віднесений до методів другорядних, ефективність яких була апріорі менша ніж звичних методів нелінійної оптимізації – Нелдера-Міда, або градієнтних методів. Амбіційні наміри побудови універсального алгоритма спочатку розглядаються на задачах невеликого розміру, які проте зовсім не уособлюють собою спрощені випадки. Наводиться приклад такого відображення для двовимірного простору і чотирьох лінійних обмежень, а також аналіз практичного потенціалу такого підходу виконаний для задачі оптимізації квадратичної цільової функції.

Kлючові слова: умовна оптимізація; симплекс; COBYLA; штрафний параметр; багатовид; білінійне перетворення; обчислювальна складність; трансформація задач умовної оптимізації.