Розв’язування мультимодальних оптимізаційних задач великої розмірності
This paper considers large-scale multimodal optimization problems. Such problems have many local extrema. These problems are quite difficult to solve with modern methods. But most practical optimization problems are multimodal. The libraries of test and applied multimodal problems have been develope...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/290 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479660240044032 |
|---|---|
| author | Kosolap, Anatolii |
| author_facet | Kosolap, Anatolii |
| author_institution_txt_mv | [
{
"author": "Anatolii Kosolap",
"institution": "д. ф.-м. н., професор, завідувач кафедри Українського державного хіміко-технологічного університету, просп. Гагаріна, 8, 49005, Дніпро"
}
] |
| author_sort | Kosolap, Anatolii |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | This paper considers large-scale multimodal optimization problems. Such problems have many local extrema. These problems are quite difficult to solve with modern methods. But most practical optimization problems are multimodal. The libraries of test and applied multimodal problems have been developed to test the effectiveness of new methods of global optimization. There is a problem with how to determine the effectiveness of the method when solving the problems from these libraries. We propose a simple criterion for determining the effectiveness of the optimization method. It is proposed to consider only problems with unknown solutions. Then it is better to consider such a method that gives better solutions for a larger number of problems from these libraries. The paper shows that today the best method for solving large-scale multimodal problems is the method of exact quadratic regularization. |
| first_indexed | 2026-06-09T01:09:48Z |
| format | Article |
| fulltext |
126
doi.org/10.15407/fmmit2023.36.126
Розв’язування мультимодальних оптимізаційних задач
великої розмірності
Анатолій Косолап1
1 д. ф.-м. н., професор, завідувач кафедри Українського державного хіміко-технологічного університету,
просп. Гагаріна, 8, 49005, Дніпро, e-mail: anivkos@ua.fm
У роботі розглядаються мультимодальні оптимізаційні задачі великої розмірності. Такі
задачі мають безліч локальних екстремумів. Вони є досить складними для чисельного
розв’язування сучасними методами. Але більшість практичних оптимізаційних задач є
мультимодальними. Для перевірки ефективності нових методів глобальної оптимізації
розроблені бібліотеки тестових та прикладних мультимодальних задач. Виникає проблема,
як визначати ефективність методу при розв’язуванні задач з даних бібліотек. Ми
пропонуємо простий критерій для визначення ефективності методу оптимізації.
Пропонується розглядати тільки задачі з невідомими розв’язками. Тоді кращим буде такий
метод, який дає кращі розв’язки для більшої кількості задач з даних бібліотек. В роботі
показано, що на сьогодні кращим методом для розв’язування мультимодальних задач
великої розмірності є метод точної квадратичної регуляризації.
Ключові слова: мультимодальні оптимізаційні задачі; тестові задачі;
метод точної квадратичної регуляризації.
Вступ. Задачі оптимізації виникають майже в кожній сфері людської діяльності.
Це такі сфери, як економіка, фінанси, управління, технологічні процеси,
проектування, штучний інтелект, інформатика та багато інших. Для
розв’язування таких задач будуються оптимізаційні моделі. Як правило,
оптимізаційні моделі прикладних задач будуть мультимодальними. Часто такі
моделі будуть дискретними (з дискретними змінними), але вони легко
перетворюються до неперервних мультимодальних задач. На сьогодні, для
розв’язування оптимізаційних задач розроблено безліч методів та комп’ютерних
програм. Але такі програми дозволяють ефективно розв’язувати тільки
унімодальні оптимізаційні задачі великої розмірності. Для розв’язування
мультимодальних оптимізаційних задач теж розроблені комп’ютерні програми,
зокрема такі відомі пакети: ANTIGONE, BARON, COUENNE, CPLEX, GUROBI,
LINDO, SCIP. Для використання цих пакетів, для розв’язування
мультимодальних задач (більшість з них комерційні), потрібно ввести початкові
дані. Для цього дані необхідно представити у спеціальній формі або у відомих
форматах GAMS та AMPL. На відміні від програмного забезпечення
розв’язування унімодальних задач, ці програми потребують для розв’язування
УДК 519.893
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 126-130
127
мультимодальної задачі досить багато часу, стикаються з проблемою пошуку
допустимої точки та не гарантують отримання оптимальних розв’язків. Не
дивлячись на значні зусилля [1] проблема ефективного розв’язування
мультимодальних задач залишається відкритою.
1. Бібліотеки тестових та прикладних мультимодальних задач
Відомими бібліотеками тестових та прикладних задач, які використовуються для
перевірки ефективності нових методів глобальної оптимізації є GlobalLib,
MinlpLib та PrincetonLib. Ці бібліотеки містять як задачі малої розмірності з
кількістю змінних менше 10, так і великої розмірності з десятками тисяч
змінних. Тільки частина задач з цих бібліотек має невідомі розв’язки. Наприклад,
з 1224 задач бібліотеки PrincetonLib відомо, що тільки 228 задач мають невідомі
розв’язки. Ці бібліотеки були побудовані більше 20 років тому. Їх легко можна
знайти в мережі Інтернет за адресами http://minlplib.org/dates.html та
http://www.gamsworld.org/performance/princetonlib/ princetonlib.htm. Бібліотека
GlobalLib містить тільки задачі умовної оптимізації з неперервними змінними,
всього 397 задач. Для більшості її задач оптимальні розв’язки знайдені (знайдені
нижні та верхні оцінки розв’язків, які співпадають). Більшість моделей
бібліотеки MinlpLib мають змішані змінні (неперервні, булеві та цілі), всього 269
задач. Ця бібліотека також містить тільки задачі умовної оптимізації і для
більшості її задач знайдені оптимальні розв’язки. За адресом
http://minlplib.org/dates.html приводяться кращі знайдені розв’язки для більшості
задач разом з точками мінімуму. Бібліотека PrincetonLib містить задачі
безумовної та умовної оптимізації з неперервними змінними. В Інтернеті
приводяться кращі знайдені розв’язки бібліотеки PrincetonLib, але точки
мінімумів не приводяться.
Не дивлячись на те, що задачі умовної оптимізації є досить важливими,
порівняння розв’язків для таких задач є складною задачею. Це пов’язано з
точністю виконання обмежень задачі. Автор рахує, що ця точність не повинна
бути менша 1Е-10. Крім перерахованих бібліотек, існує також відомий список
тестових функцій [2]. Ці тестові функції мають безліч локальних екстремумів (n!
і більше), але майже всі вони мають відомі розв’язки. Тільки для функцій Egg
holder та Rana точки глобальних мінімумів невідомі. Функції з даного списку
мають, як правило, розмірність два, або довільну розмірність. Автор узагальнив
ці функції розмірності два на довільну розмірність. Зокрема, це такі функції, як
Bird, Trefethen, Adjman, Scahffer 4, M. Zakarov, M. Keane, NewFunction03, siam,
liang’s. Для розмірностей цих функцій 100 і вище, значення глобального
мінімуму невідоме. Для порівняння обчислювальних експериментів автор для
розв’язування цих задач використовував метод еволюційного пошуку з
бібліотеки python та інші програми.
Таким чином, для перевірки ефективності методів глобальної оптимізації
ми можемо обмежитись тільки задачами мультимодальної оптимізації з
невідомими розв’язками (точками глобальних мінімумів).
http://www.gamsworld.org/performance/princetonlib/
http://minlplib.org/dates.html
Анатолій Косолап
Розв’язування мультимодальних оптимізаційних задач великої розмірності
128
2. Перевірка ефективності методів глобальної оптимізації
Будемо порівнювати метод точної квадратичної регуляризації (EQR) [3] з усіма
існуючими методами. Як відомо, точна квадратична регуляризація дозволяє
перетворити загальну задачу нелінійної оптимізації
},,...,1,0)(|)(min{ 0
n
i Exmixfxf (1)
до послідовності задач максимізації евклідової норми вектору на опуклій
множині
},,,...,1,||||)(,||||)1()(|||max{|| 122
0
2 n
i Exmidzrxfdzrsxfz (2)
де z = (x1,…, xn, xn+1), параметр r обираємо таким, щоб множина задачі (2) стала
опуклою, а параметр s повинен задовольняти умові s ||x
*
||
2
– f0(x
*
), x
*
– розв’язок
задачі (1). Що дає таке перетворення задачі (1) до задачі (2)? По-перше, локальні
максимуми задачі (2) упорядковані в порядку зростання скалярної величини d,
так що при мінімальному значенню d, розв’язок задачі (2) співпадає з розв’язком
задачі (1). Крім того, при фіксованому значенні d і максимізації ||z||
2
, значення
виразу r||z||
2
– d по абсолютній величині буде наближатися до нуля [3]. Таким
чином, в задачі (2) необхідно знайти мінімальне значення скалярної змінної d,
для якої розв’язок задачі (2) буде задовольняти умові r||z||
2
= d. Тоді цей розв’язок
буде також розв’язком задачі (1). Ми використовуємо для розв’язування задачі
(2) тільки програму локальної оптимізації, а для знаходження оптимального
значення d – метод дихотомії. Це дозволяє розв’язувати задачі мільтимодальної
оптимізації великої розмірності також легко, як і задачі опуклої оптимізації.
Алгоритм розв’язування задачі (2) наступній.
Крок 1. Обираємо значення параметрів r та s, які задовольняють
приведеним вище умовам, і початкову точку z (наприклад, z = (1,…,1)).
Крок 2. Розв’язуємо задачу опуклої оптимізації
},,...,1,||||)(,||||)1()(|min{ 122
0
n
i Exmidzrxfdzrsxfd
і знаходимо мінімальне та допустиме значення d. Як правило, для цього значення
d маємо r||z||
2
= d. Інакше задача (2), а разом з тим і задача (1) буде розв’язана.
Крок 3. Будемо збільшувати значення d на відповідну величину і для
кожного фіксованого значення d розв’язувати задачу (2) до тих пір, доти не
виконається умова r||z||
2
= d з заданою точністю (максимізація ||z||
2
при
фіксованому значенні d буде зменшувати абсолютну величину різниці r||z||
2
– d
на кожній ітерації).
Даним алгоритмом були розв’язані майже всі задачі з бібліотек GlobalLib,
MinlpLib та PrincetonLib за виключенням задач малої розмірності, задач досить
великої розмірності (n > 3000), а також унімодальних задач. Загалом було
розв’язано біля 300 задач. В якості програми локальної оптимізації
використовувалась надбудова OpenSolver для Excel. Деякі з задач великої
розмірності з даних бібліотек мають до 200 сторінок формул цільової функції.
Введення такого обсягу даних є проблемою, тому автором була написана
програма VBA для Excel, яка дозволяє в інтерактивному режимі ввести формули
в Excel за декілька хвилин.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 126-130
129
Таблиця 1
Розв’язки тестових задач безумовної оптимізації з PrincetonLib
№
п/п
Задача n
Метод EQR
кращий min
Кращий відомий
min
1 bdqrtic 1000 3983.818 3983.818
2 biggsb1 1000 0.015 0.015
3 bratu1d 1003 –8.53368E-05 –8.519E-05
4 broudn7d 1000 28.1325 365.96887349
5 chainwoo 999 0 1
6 chenhark 1000 –2 –2
7 dual3 111 0.13575583 0.13575583
8 edensch 2000 12003.28459 12003.28459
9 eg2 1000 -999.5 -998.94739
10 eigenbls 110 0 0
11 errinros 50 39.90415 39.90415
12 explin 120 –723756.2655 –723756.26549
13 expquad 120 –3624599.888 –3624599.888
14 fletcbv2 100 –0.514006786 –0.51400679
15 flosp2th 691 0.01 0.01922788
16 genrose 500 1 1
17 hadamals 100 25.3164 25.3164
18 indef 1000 –495.8594 –495.8594
19 noncvxu2 1000 0.0023168 0.00231789
20 noncvxun 1000 0.0023168 0.0023168
21 nonmsqrt 9 0.75180028 0.75180042
22 osborneb 11 0.04013774 0.04013774
23 penalty1 1000 0.009686 0.009686
24 pentdi 1000 -0.75 –0.75
25 probpenl 500 2E-07 2E-07
26 qrtquad 120 –3648088.364 –3648088.364
27 scon1dls 1002 0 2.89278401
28 sineali 20 1901 1900.96
Автором отримані наступні результати методом EQR. Для задач з
бібліотеки PrincetonLib були покращені розв’язки більше ніж для 30% задач, для
інших задач цієї бібліотеки розв’язки співпадають з кращими розв’язками,
отриманими всіма іншими методами за більш ніж 20 років обчислювальних
експериментів. Для бібліотеки GlobalLib кращі розв’язки були отримані методом
Анатолій Косолап
Розв’язування мультимодальних оптимізаційних задач великої розмірності
130
EQR для 15%, для інших задач розв’язки співпадають, а для бібліотеки MinlpLib
кращі розв’язки отримані для 60% задач, для інших задач розв’язки теж
співпадають.
Наведемо приклад розв’язування задач безумовної оптимізації з бібліотеки
PrincetonLib в табл. 1, де n означає кількість змінних.
Висновки. Приведені результати свідчать, що метод EQR дозволяє ефективно
розв’язувати мультимодальні оптимізаційні задачі великої розмірності. Причому
цей метод дозволяє знайти абсолютно кращі результати, для перелічених
тестових та прикладних задач, ніж всі існуючі методи глобальної оптимізації і це
при тому, що розглянуті тестові та прикладні задачі розв’язуються уже понад 20
років різними методами.
Література
[1] Locatelli, M., Schoen, F. (Global) Optimization: Historical notes and recent
Developments // EURO Journal on Computational Optimization, vol. 9, 2021. – pp. 1–15.
[2] Jamil, M, Yang, XS. A literature survey of benchmark functions for global optimization problems
// Int. J. Math. Model Numer. Optim. Vol. 4, No. 2, 2013, pp. 150–194.
[3] Kosolap A. Practical Global Optimization. – Dnipro.: Publisher Bila K.O., 2020. – 192 p.
Solving large-scale multimodal optimization problems
Anatolii Kosolap
This paper considers large-scale multimodal optimization problems. Such problems have many
local extrema. These problems are quite difficult to solve with modern methods. But most practical
optimization problems are multimodal. The libraries of test and applied multimodal problems have
been developed to test the effectiveness of new methods of global optimization. There is a problem
with how to determine the effectiveness of the method when solving the problems from these
libraries. We propose a simple criterion for determining the effectiveness of the optimization
method. It is proposed to consider only problems with unknown solutions. Then it is better to
consider such a method that gives better solutions for a larger number of problems from these
libraries. The paper shows that today the best method for solving large-scale multimodal problems
is the method of exact quadratic regularization.
Отримано 14.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-290 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:48Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/9b/62721d65e93c4c7a7cd9b83bf7adaa9b.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2902025-02-21T17:32:19Z Solving large-scale multimodal optimization problems Розв’язування мультимодальних оптимізаційних задач великої розмірності Kosolap, Anatolii мультимодальні оптимізаційні задачі; тестові задачі; метод точної квадратичної регуляризації. This paper considers large-scale multimodal optimization problems. Such problems have many local extrema. These problems are quite difficult to solve with modern methods. But most practical optimization problems are multimodal. The libraries of test and applied multimodal problems have been developed to test the effectiveness of new methods of global optimization. There is a problem with how to determine the effectiveness of the method when solving the problems from these libraries. We propose a simple criterion for determining the effectiveness of the optimization method. It is proposed to consider only problems with unknown solutions. Then it is better to consider such a method that gives better solutions for a larger number of problems from these libraries. The paper shows that today the best method for solving large-scale multimodal problems is the method of exact quadratic regularization. У роботі розглядаються мультимодальні оптимізаційні задачі великої розмірності. Такі задачі мають безліч локальних екстремумів. Вони є досить складними для чисельного розв’язування сучасними методами. Але більшість практичних оптимізаційних задач є мультимодальними. Для перевірки ефективності нових методів глобальної оптимізації розроблені бібліотеки тестових та прикладних мультимодальних задач. Виникає проблема, як визначати ефективність методу при розв’язуванні задач з даних бібліотек. Ми пропонуємо простий критерій для визначення ефективності методу оптимізації. Пропонується розглядати тільки задачі з невідомими розв’язками. Тоді кращим буде такий метод, який дає кращі розв’язки для більшої кількості задач з даних бібліотек. В роботі показано, що на сьогодні кращим методом для розв’язування мультимодальних задач великої розмірності є метод точної квадратичної регуляризації. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/290 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 126-130 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 126-130 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/290/240 Авторське право (c) 2023 Анатолій Косолап (Автор) |
| spellingShingle | мультимодальні оптимізаційні задачі тестові задачі метод точної квадратичної регуляризації. Kosolap, Anatolii Розв’язування мультимодальних оптимізаційних задач великої розмірності |
| title | Розв’язування мультимодальних оптимізаційних задач великої розмірності |
| title_alt | Solving large-scale multimodal optimization problems |
| title_full | Розв’язування мультимодальних оптимізаційних задач великої розмірності |
| title_fullStr | Розв’язування мультимодальних оптимізаційних задач великої розмірності |
| title_full_unstemmed | Розв’язування мультимодальних оптимізаційних задач великої розмірності |
| title_short | Розв’язування мультимодальних оптимізаційних задач великої розмірності |
| title_sort | розв’язування мультимодальних оптимізаційних задач великої розмірності |
| topic | мультимодальні оптимізаційні задачі тестові задачі метод точної квадратичної регуляризації. |
| topic_facet | мультимодальні оптимізаційні задачі тестові задачі метод точної квадратичної регуляризації. |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/290 |
| work_keys_str_mv | AT kosolapanatolii solvinglargescalemultimodaloptimizationproblems AT kosolapanatolii rozvâzuvannâmulʹtimodalʹnihoptimízacíjnihzadačvelikoírozmírností |