Перетворення координат в задачах глобальної оптимізації

Анотація

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