2024, випуск 1, c. 27-46
Одержано 12.03.2024; Виправлено 18.03.2024; Прийнято 19.03.2024
Надруковано 29.03.2024; Вперше Online 31.03.2024
https://doi.org/10.34229/2707-451X.24.1.3
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Використання методу еліпсоїдів для задачі Сильвестра та її узагальнення
П.І. Стецюк 1 *
, О.М. Хом’як 1
, О.О. Давидов 2
1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
2 Київський національний університет імені Тараса Шевченка, Україна
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Задача Сильвестра або задача про найменше обмежувальне коло – це задача про побудову круга найменшого радіуса, який містить скінченний набір точок на площині. В n-вимірному просторі їй відповідає задача про найменшу обмежувальну гіперсферу, яка можна сформулювати як задачу мінімізації опуклої кусочно-квадратичної функції.
Стаття присвячена дослідженню застосування методу еліпсоїдів для розв’язання цієї задачі та мінімаксної задачі опуклого програмування, що є еквівалентною узагальненій задачі про найменшу обмежувальну гіперсферу. Узагальнена задача полягає у знаходженні центру кулі в n-вимірному просторі, яка має мінімальний радіус та містить скінченний набір n-вимірних куль, заданих їх центрами та радіусами.
Матеріал статті викладений у 3 розділах. У розділі 1 описано алгоритм emshor – алгоритм методу еліпсоїдів для задачі мінімізації довільної опуклої функції, доведено теореми про його збіжність, наведено геометричну інтерпретацію алгоритму, яка базується на використанні еліпсоїда мінімального об’єму. Тут представлено octave реалізацію алгоритму emshor, яку можна успішно застосовувати для мінімізації негладких опуклих функцій, якщо кількість змінних n = 2 ¸ 30.
У розділі 2 побудовано алгоритм sylvester1, який є застосуванням алгоритму emshor для розв'язання задачі мінімізації опуклої кусково-квадратичної функції, що є еквівалентною задачі знаходження кулі мінімального радіуса для скінченного набору точок. У розділі 3 побудовано алгоритм sylvester2, який є застосуванням алгоритму emshor для розв'язання задачі мінімізації опуклої функції, що є еквівалентною узагальненій задачі знаходження кулі мінімального радіуса для скінченного набору куль з заданими їх центрами та радіусами. Результати тестування алгоритмів sylvester1 та sylvester2 демонструють високу швидкість роботи для сучасних комп’ютерів та високу точність за оптимальним значенням цільової функції при розв’язанні задач в n-вимірних просторах для невеликих значень n = 2 ¸ 30.
Ключові слова: метод еліпсоїдів, опукла функція, задача Сильвестра, кусково-гладка функція, мінімаксна задача.
Цитувати так: Стецюк П.І., Хом’як О.М., Давидов О.О. Використання методу еліпсоїдів для задачі Сильвестра та її узагальнення. Cybernetics and Computer Technologies. 2024. 1. С. 27–46. https://doi.org/10.34229/2707-451X.24.1.3
Список літератури
1. Sylvester J.J. A question in the geometry of situation. Quarterly Journal of Mathematics. 1857. Т. 1. P. 79.
2. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач. Экономика и математические методы. 1976. Вып. 2. С. 357–369.
3. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика. 1977. Т. 13. № 1. С. 94–95.
4. Шор Н.З., Билецкий В.И. Метод растяжения пространства для ускорения сходимости в задачах овражного типа. Теория оптимальных решений. 1969. № 2. С. 3–18.
5. Шор Н.З. Использование операции растяжения пространства в задачах минимизации выпуклых функций. Кибернетика. 1970. Т. 6. № 1. С. 6–12.
6. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.
7. Octave. http://www.octave.org (звернення: 12.03.2024)
8. Fischer A., Khomyak O., Stetsyuk P. The ellipsoid method and computational aspects. Commun. Optim. Theory. 2023. No. 21. P. 1–14.
9. Стецюк П.І., Фішер А., Хом’як О.М. Уніфіковане представлення класичного методу еліпсоїдів. Кібернетика та системний аналіз. 2023. Т. 59. № 5. С. 113–123.
10. Задача про найменше коло. https://en.wikipedia.org/wiki/Smallest-circle_problem. (звернення: 12.03.2024)
11. Хом’як О.М., Давидов О.О. Метод еліпсоїдів для гіперкулі мінімального радіуса. Матеріали VII-ї Міжнародної наукової конференції "Математичне моделювання, оптимізація та інформаційні технології (MMOTI-2021)", 15–19 листопада 2021 р. С. 340–342.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна