2021, випуск 1, c. 29-42

Одержано 12.03.2021; Виправлено 19.03.2021; Прийнято 25.03.2021

Надруковано 30.03.2021; Вперше Online 03.04.2021

https://doi.org/10.34229/2707-451X.21.1.3

Попередня  |  Повний текст  |  Наступна

 

УДК 519.85

Використання r-алгоритму Шора в лінійних задачах робастної оптимізації

П.І. Стецюк 1 * ORCID ID favicon Big,   М.Г. Стецюк 1,   Д.О. Брагін 2,   М.О. Молодик 2

1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ

2 Московський фізико-технічний институт, Долгопрудний, Московська область

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Cтаття присвячена опису нового підходу до побудови алгоритмів розв’язання задач лінійного програмування (ЛП-задач), у яких кількість обмежень є значно більшою за кількість змінних. Він базується на використанні модифікації r-алгоритму для розв`язання задачі мінімізації негладкої функції, яка є еквівалентною ЛП-задачі. Переваги підходу продемонстровані на лінійній задачі робастної оптимізації та задачі робастної оцінки параметрів за допомогою методу найменших модулів. Розроблені octave-програми призначені для розв’язання ЛП-задач з дуже великою кількістю обмежень, для яких використання стандартного програмного забезпечення з лінійного програмування є або неможливим або недоцільним, адже вимагає значних обчислювальних ресурсів.

Матеріал статті викладено у трьох розділах. У першому розділі для задачі мінімізації опуклої функції описано модифікацію r-алгоритму з постійним коефіцієнтом розтягу простору в напрямі різниці двох послідовних субградієнтів та адаптивним способом регулювання кроку у напрямі антисубградієнта у перетвореному просторі змінних. Представлена програмна реалізація цієї модифікації у вигляді Octave-функції ralgb5a, яка дозволяє знаходити або наближення до точки мінімуму опуклої функції, або наближення до точки максимуму увігнутої функції. Наведено код функції ralgb5a з коротким описом її вхідних та вихідних параметрів.

У другому розділі представлено спосіб розв’язання ЛП-задачі, який використовує негладку штрафну функцію у вигляді функції максимуму та побудову допоміжної задачі безумовної мінімізації опуклої кусково-лінійної функції. Вибір скінченного коефіцієнта штрафу забезпечує еквівалентність між ЛП-задачею та допоміжною задачею, а остання вирішується за допомогою програми ralgb5a. Представлено результати обчислювальних експериментів в GNU Octave для розв’язання тестових ЛП-задач з кількістю обмежень від двохсот тисяч до п’ятдесяти мільйонів та кількістю змінних від десяти до п’ятдесяти.

У третьому розділі представлено метод найменших модулів, який є робастним до аномальних спостережень або «викидів». Метод використовує задачу безумовної мінімізації опуклої кусково-лінійної функції, яка вирішується за допомогою програми ralgb5a. Представлено результати обчислювальних експериментів в GNU Octave для розв’язання тестових задач з великою кількістю спостережень (від двохсот тисяч до п’яти мільйонів) та невеликою кількістю невідомих параметрів (від десяти до ста). Вони демонструють перевагу розроблених програм у порівнянні з відомим програмним забезпеченням для лінійного програмування, таким як пакет GLPK.

 

Ключові слова: робастна оптимізація, задача лінійного програмування, негладка штрафна функція, r-алгоритм, метод найменших модулів, GNU Octave.

 

Цитувати так: Стецюк П.І., Стецюк М.Г., Брагін Д.О., Молодик М.О. Використання r-алгоритму Шора в лінійних задачах робастної оптимізації. Cybernetics and Computer Technologies. 2021. 1. С. 29–42. https://doi.org/10.34229/2707-451X.21.1.3

 

Список літератури

           1.     Ben-Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. Princeton: Princeton Univ. Press, 2009. 576 p.

           2.     Горяшко А.П., Немировский А.С. Оптимизация стоимости энергии в системах водоснабжения в условиях неопределенности потребления. Автоматика и телемеханика. 2014. Выпуск 10. С. 52–72.

           3.     Алєксєєва І.В., Перевознюк Т.І. Застосування робастної оптимізації для лінійної моделі функціонування малого підприємства. Mathematics in Modern Technical University. 2018. 1. P. 61–73. https://doi.org/10.20535/mmtu-2018.1-061

           4.     Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.

           5.     Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. № 5. С. 43–57.

           6.     Стецюк П.И., Фишер А. r–Алгоритмы Шора и octave-функция ralgb5a. Тези міжнародної наукової конференції «Сучасна інформатика: проблеми, досягнення та перспективи розвитку», що присвячена 60-річчю заснування Інституту кібернетики імені В.М. Глушкова НАН України (Київ, 13–15 грудня 2017). К.: Ін-т кібернетики імені В.М. Глушкова НАН України. 2017. С. 143–146.

           7.     Стецюк П.И. Субградиентные методы ralgb5 и ralgb4 для минимизации овражных выпуклых функций. Вычислительные технологии. 2017. Т. 22, № 2. С. 127–149.

           8.     Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.

           9.     Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd. 2008. 568 p.

       10.     GNU Linear Programming Kit (GLPK). http://www.gnu.org/software/glpk/glpk.html (звернення 12.03.2021)

       11.     Хьюбер Дж. П. Робастность в статистике. М.: Мир, 1984. 304 с.

       12.     Стецюк П.И., Колесник Ю.С., Лейбович М.М. О робастности метода наименьших модулей. Компьютерная математика. 2002. С. 114–123.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2021,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.