2022, випуск 3, c. 98-112
Одержано 16.09.2022; Виправлено 29.09.2022; Прийнято 15.11.2022
Надруковано 29.11.2022; Вперше Online 10.12.2022
https://doi.org/10.34229/2707-451X.22.3.10
Попередня | ПОВНИЙ ТЕКСТ | Наступна
GNU Octave та Python реалізації r-алгоритму Шора з адаптивним регулюванням кроку
П.І. Стецюк 1 *
, О.В. Пилиповський 2
, О.М. Хом’як 1
1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
2 Київський академічний університет, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
r-алгоритми, або субградієнтні методи з розтягом простору в напрямку різниці двох послідовних субградієнтів, були запропоновані Н.З. Шором в 1970 році в його докторській дисертації. Їх програмні реалізації виявилися конкурентними з найбільш ефективними методами для гладких погано обумовлених задач, як за надійністю, так і за часом розрахунків та точності результатів.
Стаття присвячена опису двох програмних реалізацій модифікації r-алгоритму Шора з постійним коефіцієнтом розтягу простору та адаптивним регулюванням кроку. Перша програма реалізована на мові GNU Octave, а друга програма реалізована мовою Python.
Матеріал статті викладено у трьох розділах. У першому розділі описано модифікацію r-алгоритму з постійним коефіцієнтом розтягу простору в напрямку різниці двох послідовних субградієнтів та адаптивним способом регулювання кроку у напрямку антисубградієнта у перетвореному просторі змінних. Представлена програмна реалізація цієї модифікації у вигляді octave-функції ralgb5a, яка дозволяє знаходити або наближення до точки мінімуму опуклої функції, або наближення до точки максимуму увігнутої функції. Наведено код функції ralgb5a з коротким описом її вхідних та вихідних параметрів.
У другому розділі описано тестові експерименти для дослідження ефективності octave-функції ralgb5a для максимізації кусково-лінійної увігнутої функції, яка отримана за допомогою методу негладких штрафних функцій для задачі лінійного програмування, та мінімізації кусково-лінійної опуклої функції, яка відповідає методу найменших модулів. Представлено результати обчислювальних експериментів для розв’язання тестових задач з 200, 500, 1000, 1500 та 2000 змінних, які демонструють ефективну роботу octave-функції ralgb5a.
У третьому розділі описано python-функцію ralgb5a та наведено її код з описом вхідних та вихідних параметрів. Показано, як за допомогою налаштування двох параметрів можна прискорити роботу функцію ralgb5a. Представлено результати обчислювальних експериментів для розв’язання тестової задачі за методом найменших модулів для 5000 змінних та 10000 спостережень.
Ключові слова: r-алгоритм, лінійне програмування, негладка штрафна функція, метод найменших модулів, GNU Octave, python.
Цитувати так: Стецюк П.І., Пилиповський О.В., Хом’як О.М. GNU Octave та Python реалізації r-алгоритму Шора з адаптивним регулюванням кроку. Cybernetics and Computer Technologies. 2022. 3. С. 98–112. https://doi.org/10.34229/2707-451X.22.3.10
Список літератури
1. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения: автореф. дис. ... докт. физ-мат. наук. Киев, 1970. 44 с.
2. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов. Кибернетика. 1971. 3. С. 51–59.
3. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.
4. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. Киев: Наук. думка, 1989. 208 с.
5. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
6. Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd. 2008. 568 p.
7. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. № 5. С. 43–57.
8. Стецюк П.И. Субградиентные методы ralgb5 и ralgb4 для минимизации овражных выпуклых функций. Вычислительные технологии. 2017. Т. 22, № 2. С. 127–149.
9. Стецюк П.І. Комп'ютерна програма "Octave-програма ralgb5a: r(α)-алгоритм з адаптивним кроком". Свідоцтво про реєстрацію авторського права на твір № 85010. Україна. Міністерство економічного розвитку і торгівлі. Державний департамент інтелектуальної власності. Дата реєстрації 29.01.2019.
10. Стецюк П.І., Стецюк М.Г., Брагін Д.О., Молодик М.О. Використання r-алгоритму Шора в лінійних задачах робастної оптимізації. Кібернетика та комп’ютерні технології. 2021. № 1. С. 29–42.
11. Хьюбер Дж. П. Робастность в статистике. М.: Мир, 1984. 304 с.
12. Lyn C. Thomas, David B. Edelman, Jonathan N. Crook. Credit Scoring and its Applications. SIAM Monographs on Mathematical Modeling and Computation. Philadelphia, 2002. 243 p.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна