2025, випуск 4, с. 12-28
Одержано 11.08.2025; Виправлено 11.11.2025; Прийнято 18.11.2025
Надруковано 08.12.2025; Вперше Online 15.12.2025
https://doi.org/10.34229/2707-451X.25.4.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
R-алгоритм для розв’язання задачі квадратичного програмування
П.І. Стецюк * 
, Н.І. Тукалевська, О.М. Хом’як , М.Г. Стецюк
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Задачі квадратичного програмування мають широке коло практичних застосувань у різних галузях науки й техніки, зокрема, у фінансовому моделюванні та розпізнаванні образів, що зумовлює актуальність дослідження методів їх ефективного розв’язання. У реальних застосуваннях параметри таких моделей часто є неточними або змінними, що може суттєво впливати на якість отриманих розв’язків. Робастні підходи гарантують стійкість розв’язків до невизначеності, дозволяючи приймати надійні рішення, які залишаються припустимими для всіх допустимих реалізацій вхідних даних.
У даній роботі представлено алгоритм QPralg (Quadratic Programming by r-algorithm) та його реалізацію в середовищі Octave для розв’язання задач мінімізації опуклої квадратичної функції при лінійних двобічних обмеженнях. Запропонований метод базується на використанні негладких штрафних функцій та octave–програми ralgb5a, яка реалізує r-алгоритм з адаптивним кроком. Це субградієнтний метод з постійним коефіцієнтом розтягу простору у напрямку різниці двох послідовних субградієнтів та адаптивним регулюванням кроку в напрямку антисубградієнта у перетвореному просторі змінних.
Матеріал статті викладений у 4 розділах. У розділі 1 описано r(α)–алгоритм з адаптивним способом регулювання кроку та наведена octave–програма ralgb5a, яка його реалізує. У розділі 2 наведено метод негладких штрафних функцій для задачі опуклого програмування та дві теореми, які дозволяють обґрунтовувати скінченні значення штрафних коефіцієнтів. У розділі 3 описано алгоритм QPralg, його програмну реалізацію мовою Octave, в розділі 4 наведено результати обчислювальних експериментів для задач квадратичного програмування з двоcторонніми обмеженнями.
Алгоритм QPralg орієнтований на задачі з невеликою кількістю змінних та дуже великою кількістю обмежень (від сотень тисяч до кількох мільйонів). Для таких задач комерційні солвери, зокрема, Gurobi, потребують у декілька разів більше обчислювального часу на сучасних комп’ютерах із 8 ГБ оперативної пам’яті. Можливість ефективно працювати з великою кількістю обмежень дозволяє також розв’язувати квадратичні та лінійні задачі робастної оптимізації для широкого набору реалізацій вектора невизначеності.
Ключові слова: задача квадратичного програмування, робастна оптимізація, негладка штрафна функція, r-алгоритм, GNU Octave.
Цитувати так: Стецюк П.І., Тукалевська Н.І., Хом’як О.М., Стецюк М.Г. R-алгоритм для розв’язання задачі квадратичного програмування. Cybernetics and Computer Technologies. 2025. 4. С. 12–28. https://doi.org/10.34229/2707-451X.25.4.2
Список літератури
1. Nocedal J., Wright S.J. Numerical optimization (Springer Series in Operations Research and Financial Engineering). Berlin: Springer, 2006.
2. Gertz E.M., Wright S.J. Object-oriented software for quadratic programming. ACM Transactions on Mathematical Software (TOMS). 2003. Vol. 29, No. 1. P. 58–81.
3. Boggs P.T., Tolle J.W. Sequential quadratic programming, Acta Numerica. 1995. Vol. 4. P. 1–51.
4. Ben–Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. Princeton: Princeton Univ. Press, 2009. 576 p.
5. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наук. думка, 1979. 200 с.
6. Octave. http://www.octave.org (звернення: 09.11.2025)
7. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. Киев: Наук. думка, 1989. 208 с.
8. Стецюк П.И., Фишер А. r–Алгоритмы Шора и octave–функция ralgb5a. Тези міжнародної наукової конференції «Сучасна інформатика: проблеми, досягнення та перспективи розвитку», що присвячена 60–річчю заснування Інституту кібернетики імені В.М. Глушкова НАН України (Київ, 13–15 грудня 2017). 2017. С. 143–146.
9. Стецюк П.І., Пилиповський О.В., Хом’як О.М. GNU Octave та Python реалізації r–алгоритму Шора з адаптивним регулюванням кроку. Cybernetics and Computer Technologies. 2022. № 3. С. 98–112. https://doi.org/10.34229/2707-451X.22.3.10
10. Bertsekas D.P. Necessary and sufficient conditions for a penalty method to be exact. Math. Program. 1975. 9. P. 87–99. https://doi.org/10.1007/bf01681332
11. Пшеничный Б.Н. Метод линеаризации. М.: Наука, 1983. 136 с.
12. Алєксєєва І.В., Перевознюк Т.І. Застосування робастної оптимізації для лінійної моделі функціонування малого підприємства. Mathematics in Modern Technical University. 2018. Vol. 2018, No 1. P. 61–73. https://doi.org/10.20535/mmtu–2018.1–061
13. Stetsyuk P., Fischer A., Pichugina O. A Penalty Approach to Linear Programs with Many Two–Sided Constraints. In: Pardalos P., Khachay M., Kazakov A. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2021. Lecture Notes in Computer Science. Vol 12755. Springer, Cham. 2021. P. 206–217. https://doi.org/10.1007/978–3–030–77876–7_14
14. Стецюк П.І., Стецюк М.Г., Брагін Д.О., Молодик М.О. Використання r–алгоритму Шора в лінійних задачах робастної оптимізації. Кібернетика та комп'ютерні технології. 2021. № 1. С. 29–42. https://doi.org/10.34229/2707–451X.21.1.3
15. Стецюк П., Фішер А., Хом’як О. Штрафна функція максимуму в лінійному програмуванні. Фізико–математичне моделювання та інформаційні технології. 2021. № 33. С. 156–160. https://doi.org/10.15407/fmmit2021.33.156
16. Shary S.P. Non–traditional intervals and their use. Which ones really make sense? Numerical Analysis and Applications. 2023. 16 (2). P. 179–191. https://doi.org/10.1134/S1995423923020088
17. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. http://www.gurobi.com/ (звернення: 06.08.2025).
18. NEOS Solver. https://neos–server.org/ (звернення: 06.08.2025)
19. Стецюк П.И., Нурминский Е.А. Негладкий штраф и субградиентные алгоритмы для решения задачи проекции на политоп. Кибернетика и системный анализ. 2010. № 1. С. 59–63.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна