2023, випуск 3, c. 16-22
Одержано 18.09.2023; Виправлено 25.09.2023; Прийнято 26.09.2023
Надруковано 29.09.2023; Вперше Online 19.10.2023
https://doi.org/10.34229/2707-451X.23.3.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про r-алгоритм Шора для задач з обмеженнями
В.І. Норкін 1, 2 
, А.Ю. Козирєв 2 *
1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
2 Національний технічний університет України «Київський політехнічний інститут ім. Ігоря Сікорського»
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Проблеми негладкої оптимізації виникають у широкому діапазоні застосувань, включаючи техніку, фінанси та глибоке навчання, де функції активації часто мають розривні похідні, наприклад, ReLU. Звичайні алгоритми оптимізації, розроблені переважно для гладких проблем, стикаються з труднощами при застосуванні до негладких контекстів через розриви та інші пов’язані нерегулярності. Можливі підходи для подолання цих проблем включають методи згладжування функцій та застосування методів негладкої оптимізації. Зокрема, r-алгоритм Шора (Шор, Журбенко (1971), Шор (1979)) з розтягуванням простору у напрямку різниці двох послідовних субградієнтів це конкурентно-здатний метод негладкої оптимізації (Bagirov et al. (2014)). Проте оригінальний r-алгоритм призначений для мінімізації опуклих яружних функцій без обмежень.
Мета роботи. Стандартний прийом для вирішення цим алгоритмом завдань з обмеженнями полягає у застосуванні точних негладких штрафних функцій (Єрьомін (1967), Zangwill (1967)). При цьому необхідно правильно вибрати (досить великий) коефіцієнт штрафу методом штрафних функцій. У роботах (Норкін (2020, 2022), Galvan та ін. (2021) запропоновано так званий проєктивний метод точних штрафних функцій, який теоретично не потребує точного визначення штрафного коефіцієнта. Мета роботи полягає у дослідженні можливостей нового методу точних проєктивних негладких штрафних функцій для розв’язання умовних задач негладкої оптимізації r-алгоритмом Шора.
Результати. У цій статті негладка оптимізаційна задача з опуклими обмеженнями спочатку перетворюється на задачу без обмежень методом проєктивних штрафних функцій, а потім для вирішення перетвореної задачі застосовується r-алгоритм. Наводяться результати тестування такого підходу на задачах з лінійними обмеженнями за допомогою програми, реалізованої у Matlab. Результати представленого дослідження показують, що стандартний метод негладких штрафів у поєднанні з r-алгоритмом Шора – швидкий, оскільки він використовує надану програму для розрахунку субградієнтів, але вимагає ретельного вибору параметра штрафу. Метод проєктивних штрафів – повільний, оскільки в цьому дослідженні він використовує кінцеві різниці для розрахунків узагальнених градієнтів, але досить стабільний щодо вибору параметра штрафу. Подальші дослідження будуть спрямовані на дослідження диференціальних властивостей проєкційного відображення та скорочення часу обчислення субградієнтів за рахунок паралельних обчислень.
Ключові слова: субградієнтний спуск, оптимізація з обмеженнями, r-алгоритм, точний проєктивний штраф.
Цитувати так: Norkin V., Kozyriev A. On Shor's r-Algorithm for Problems with Constraints. Cybernetics and Computer Technologies. 2023. 3. P. 16–22. https://doi.org/10.34229/2707-451X.23.3.2
Список літератури
1. Михалевич В.С., Гупал А.М., Норкин В.И. Методы невыпуклой оптимизации. М.: Наука, 1987. 278 с.
2. Mayne D.Q., Polak E. Nondifferential optimization via adaptive smoothing. Journal of Optimization Theory and Applications. 1984. 43 (4). P. 601–613.
3. Nesterov Y., Spokoiny V. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics. 2015. 17. P. 527–566. https://api.semanticscholar.org/CorpusID:254160038
4. Шор Н.З. Методы минимизации недифференцируемых функций. Киев: Наук. думка. 1979. 200 с.
5. Bagirov A., Karmitsa N., Mäkelä M. M. Introduction to Nonsmooth Optimization. Springer. 2014.
6. Eremin I.I. The penalty method in convex programming. Soviet Math. Dokl. 1966. 8. P. 459–462.
7. Eremin I.I. The penalty method in convex programming. Cybernetics. 1967. 3 (4). P. 53–56. https://doi.org/10.1007/BF01071708
8. Zangwill W. Non-linear programming via penalty junctions. Management Science. 1967. 13. P. 344–358. https://doi.org/10.1287/mnsc.13.5.344
9. Norkin V.I. A stochastic smoothing method for nonsmooth global optimization. Cybernetics and Computer technologies. 2020. 1. P. 5–14. https://doi.org/10.34229/2707-451X.20.1.1
10. Norkin V.I . A new projective exact penalty function for a general constrained optimization. Dopovidi Nac.akademii nauk Ukrainy. 2022. 5. P. 23–29. https://doi.org/10.15407/dopovidi2022.04.023
11. Galvan G., Sciandrone M., Eucidi S. A parameter-free unconstrained reformulation for nonsmooth problems with convex constraints. 2021. CompuL. Optim. Appl. 80. P. 33–53. https://doi.org/10.1007/s10589-021-00296-1
12. Shor N.Z., Zhurbenko N.G. A minimization method using the operation of extension of the space in the direction of the difference of two successive gradients. Cybernetics and Systems Analysis. 1971. 7 (3). P. 450–459. https://doi.org/10.1007/BF01070454
13. Stetsyuk P.I. Theory and Software Implementations of Shor’s r-Algorithms. Cybern Syst Anal. 2017. 53 (5). P. 692–703. https://doi.org/10.1007/s10559-017-9971-1
14. Stetsyuk P.I. Subgradient methods ralgb5 and ralgb4 for minimizing ravine convex functions. Computational technologists (ICT SB RAS). 2017. 22 (2). P. 127–149.
15. Norkin V.I. The projective exact penalty method for general constrained optimization. Preprint. V.M. Glushkov Institute of Cybernetics, Kyiv, 2022. https://optimization-online.org/?p=20458
16. Rockafellar R.T., Wets R.J-B. Variational Analysis. Springer. 1998. 734 p.
17. Kappel F., Kuntsevich A.V. An implementation of Shor’s r-algorithm. Comput. Optim. and Appl. 2000. 15 (2). P. 193–205. https://doi.org/10.1023/A:1008739111712
18. Davis T.A., Sigmon K. MATLAB® Primer. Eighth Edition. CHAPMAN & HALL/CRC. 2010. 214 p.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна