ПРОКСИМАЛЬНІ АЛГОРИТМИ ДЛЯ ДВОРІВНЕВИХ ЗАДАЧ ОПУКЛОЇ ОПТИМІЗАЦІЇ
DOI:
https://doi.org/10.17721/2706-9699.2021.1.19Ключові слова:
опукла оптимізація, дворівнева задача, проксимальний алгоритм, збіжністьАнотація
У роботі розглянуто задачі дворівневої опуклої мінімізації у гільбертовому просторі. Дворівнева задача опуклої мінімізації полягає у мінімізації першої опуклої функції на множині мінімумів другої опуклої функції. Ця постановка має багато застосувань, але неявні обмеження, що породжені внутрішньою задачею ускладнюють отримання умов оптимальності та побудову методів. Подібним чином формулюються й багаторівневі задачі, джерелом яких стали питання дослідження операцій (оптимізація за послідовно заданими критеріями або лексикографічна оптимізація). Увага зосереджена на розв’язанні задач за допомогою двох методів проксимального типу. Основні теоретичні результати – теореми про збіжність методів у різних ситуаціях. Перший з методів отриманий поєднанням методу штрафних функцій та проксимального методу. Доведена сильна збіжність у випадку сильної опуклості функції зовнішньої задачі. У загальному випадку отримана лише слабка збіжність. Другий, так званий, проксимально-градієнтний метод є поєднанням одного з варіантів швидкого проксимально-градієнтного алгоритму з методом штрафних функцій. Встановлені оцінки швидкості проксимально-градієнтного методу та його слабка збіжність.
Посилання
Podinovskii V.V., Gavrilov V.M. Optimization with respect to successively applied criteria. Moscow: Sovetskoe Radio, 1975. 192 p.
Bakushinskii A. B., Goncharskii A. V. Iterative Methods for Solving Ill-Posed Problems. Moscow: Nauka, 1989. 126 p.
Attouch H. Viscosity Solutions of Minimization Problems. SIAM J. on Optim. 1996. Vol. 6. P. 769–806.
Solodov M. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis. 2007. Vol. 4. P. 227–238.
Solodov M. A bundle method for a class of bilevel nonsmooth convex minimization problems. SIAM J. on Optim. 2007. Vol. 18. P. 242–259.
Guler O. On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 1991. Vol. 29. P. 403–419.
Passty G.B. Ergodic Convergence to a Zero of the Sum of Monotone Operators in Hilbert Spaces. Journal of Mathematical Analysis and Applications. 1979. Vol. 72. P. 383-390.
Malitsky Yu. Chambolle-Pock and Tseng's methods: relationship and extension to the bilevel optimization. arXiv:1706.02602. 2017.
Luita A.V., Semenov V.V. A novel method for the bilevel optimization problem. XXXII International Conference “Problems of decision making under uncertainties”. August 27-31, 2018. Prague, Czech Republic. Abstracts. P. 81–82.
Luita A.V., Semenov V.V. A novel proximal-gradient method for the bilevel optimization problem. Proceedings of the XXIV All-Ukrainian Scientific Conference “Contemporary Problems of Applied Mathematics and Informatics”. September 26-28, 2018. Lviv. P. 77–79.
Tseng P. On accelerated proximal gradient methods for convex-concave optimization. 2008. http://www.mit.edu/~dimitrib/PTseng/papers/apgm.pdf.
