Про властивiсть спуску для екстраградiєнтного алгоритму
DOI:
https://doi.org/10.17721/2706-9699.2025.1.03Ключові слова:
варiацiйна нерiвнiсть, операторне рiвняння, монотонний оператор, екстраградiєнтний алгоритм, швидкiсть збiжностiАнотація
Доведено новий результат щодо властивостi спуску екстраградiєнтного алгоритму, а для задач без обмежень отримано оцiнку швидкостi екстраградiєнтного алгоритму в термiнах природної нев’язки за слабших умов, нiж вiдомi.
Посилання
Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p.
Alber Y., Ryazantseva I. Nonlinear Ill Posed Problems of Monotone Type. Dordrecht: Springer, 2006. 410 p.
Kassay G., Radulescu V.D. Equilibrium Problems and Applications. London: Academic Press, 2019. xx + 419 p.
Polyak R. Finding Nonlinear Production-Consumption Equilibrium. arXiv pre-print arXiv:2204.04496. 2022.
Gidel G., Berard H., Vignoud G., Vincent P., Lacoste-Julien S. A variational inequality perspective on generative adversarial networks. arXiv preprintarXiv:1802.10551. 2018.
Nemirovski A. Prox-method with rate of convergence O(1/T) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. on Optim.2004. Vol. 15. P. 229–251.
Wang J.-K., Abernethy J., Levy K. Y. No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization. arXiv preprintarXiv:2111.11309. 2021.
Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarily Problem. V. 2. New York: Springer, 2003. 666 p.
Korpelevich G.M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. Vol. 12. No. 4. P. 747–756.
Tseng P. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization. 2000. Vol. 38. P. 431–446.
Censor Y., Gibali A., Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. Journal of Optimization Theory and Applications. 2011. Vol. 148. P. 318–335.
Denisov S.V., Nomirovskii D.A., Rublyov B.V., Semenov V.V. Convergence of Extragradient Algorithm with Monotone Step Size Strategy for Variational Inequalities and Operator Equations. Journal of Automation and Information Sciences. 2019. Vol. 51. Iss. 6. P. 12–24. https://doi.org/10.1615/JAutomatInfScien.v51.i6.20.
Malitsky Yu. Projected Reflected Gradient Methods for Monotone Variational Inequalities. SIAM Journal on Optimization. 2015. Vol. 25. P. 502–520.
Malitsky Y., Tam M.K. A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity. SIAM J. on Optim. 2020. Vol. 30. P. 1451–1472.
Mokhtari A., Ozdaglar A., Pattathil S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach. arXiv preprint arXiv:1901.08511. 2019.
Mokhtari A., Ozdaglar A., Pattathil S. Convergence rate of O(1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems. arXiv preprint arXiv:1906.01115. 2020.
Semenov V.V., Denisov S.V., Sandrakov G.V., Kharkov O.S. Convergence of the Operator Extrapolation Method for Variational Inequalities in Banach Spaces. Cybernetics and Systems Analysis. 2022. Vol. 58. Issue 5. P. 740–753.
Yoon T., Ryu E.K. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k2) rate on squared gradient norm. Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research. 2021. Vol. 139. P. 12098–12109.
Ryu E.K., Yin W. Large-scale convex optimization. Cambridge, UK: Cambridge University Press, 2022. 303 p. https://doi.org/10.1017/9781009160865.
Gorbunov E., Loizou N., Gidel G. Extragradient Method: O(1/k) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity. arXiv preprint arXiv: 2110.04261. 2021.
Cai Y., Oikonomou A., Zheng W. Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv preprint arXiv: 2204.09228. 2022.
Bauschke H.H., Combettes P.L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Berlin-Heidelberg-New York: Springer, 2011. 408 p.
Denisov S.V., Semenov V.V., Stetsyuk P.I. Bregman Extragradient Method with Monotone Rule of Step Adjustment. Cybernetics and Systems Analysis. 2019. Vol.55. Issue 3. P. 377–383. https://doi.org/10.1007/s10559-019-00144-5.
Gorbunov E., Taylor A., Gidel G. Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities. arXiv preprint arXiv: 2205.08446. 2022.
Semenov V.V., Denisov S.V., Kravets A.V. Adaptive Two-Stage Bregman Method for Variational Inequalities. Cybernetics and Systems Analysis. 2021. Vol. 57. Issue 6. P. 959–967. https://doi.org/10.1007/s10559-021-00421-2.
Semenov V.V., Denisov S.V. Convergence of the Method of Extrapolation from the Past for Variational Inequalities in Uniformly Convex Banach Spaces. Cybernetics and Systems Analysis. 2022. Vol. 58. Issue 4. P. 564–575.
