АЛГОРИТМ ЕКСТРАПОЛЯЦІЇ З МИНУЛОГО ДЛЯ ВАРІАЦІЙНИХ НЕРІВНОСТЕЙ В ГІЛЬБЕРТОВОМУ ПРОСТОРІ
DOI:
https://doi.org/10.17721/2706-9699.2023.2.04Ключові слова:
варіаційна нерівність, гільбертовий простір, метод екстраполяції з минулого, збіжністьАнотація
У статті розглядаються варіаційні нерівності з операторами, що діють в гільбертовому просторі. Для цих задач запропоновано та обгрунтовано варіанти алгоритму екстраполяції з минулого. Доведено сублінійну оцінку ефективності для функції зазору. Доведено cильну збіжність алгоритму екстраполяції з минулого для варіаційних нерівностей з рівномірно монотонними операторами. Доведено лінійну швидкість збіжності алгоритму екстраполяції з минулого для варіаційних нерівностей з операторами, що задовольняють умову типу узагальненої сильної монотонності. Запропоновано та обгрунтовано адаптивний варіант алгоритму. Запропоновано регуляризовані варіанти алгоритму та доведено теореми про їх сильну збіжність.
Посилання
Korpelevich G. M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. Vol. 12. No. 4. P. 747–756.
Popov L. D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR. 1980. Vol. 28. Issue 5. P. 845–848.
Gidel G., Berard H., Vincent P., Lacoste-Julien S. A Variational Inequality Perspective on Generative Adversarial Networks. arXiv preprint arXiv:1802.10551. 2018.
Patriksson M. Nonlinear programming and variational inequality problems: A unified approach. Dordrecht: Kluwer Academic Publishers, 1999. xiv + 334 p.
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 preprint arXiv:2204.04496. 2022.
Konnov I. V. Combined relaxation methods for variational inequalities. Berlin, Heidelberg, New York: Springer–Verlag, 2001. 181 p.
Bauschke H. H., Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Berlin-Heidelberg-New York: Springer, 2011. 408 p.
Semenov V. V. Variational inequalities: theory and algorithms. Kyiv: "Kyiv University", 2021. 167 p.
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.
Nesterov Y. Dual Extrapolation and Its Applications to Solving Variational Inequalities and Related Problems. Math. Program. 2007. V. 109. No. 2-3. P. 319–344.
Mainge P.-E. Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization. Set-Valued Analysis. 2008. Vol. 16. P. 899–912.
Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Amer. Math. Soc. 1967. Vol. 73. P. 591–597.
Popov L. D. On schemes for the formation of a master sequence in a regularized extragradient method for solving variational inequalities. Russian Mathematics. 2004. Vol. 48. Issue 1. P. 67–76.
Malitsky Yu. V., Semenov V. V. An extragradient algorithm for monotone variational inequalities. Cybernetics and Systems Analysis. 2014. Vol. 50. P. 271–277.
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.
Denysov S., Semenov V. Theoretical Bound of the Complexity of Some Extragradient-Type Algorithms for Variational Inequalities in Banach Spaces. Selected Papers of the VIII International Scientific Conference “Information Technology and Implementation” (IT&I-2021). Workshop Proceedings, Kyiv, Ukraine, December 1-3, 2021. CEUR Workshop Proceeedings, vol. 3179. 2022. P. 144–155.
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. Iss. 4. P. 564–575.
Lyashko S. I., Semenov V. V. A New Two-Step Proximal Algorithm of Solving the Problem of Equilibrium Programming. In: B. Goldengorin (ed.) Optimization and Its Applications in Control and Data Sciences. Springer Optimization and Its Applications, vol. 115. Springer, Cham, 2016. P. 315–325.
Chabak L., Semenov V., Vedel Y. A New Non-Euclidean Proximal Method for Equilibrium Problems. In: Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (eds) Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018. Advances in Intelligent Systems and Computing, vol. 836. Springer, Cham, 2019. P. 50–58.
Semenov V. V. A Version of the Mirror descent Method to Solve Variational Inequalities. Cybernetics and Systems Analysis. 2017. Vol. 53. P. 234–243.
Semenov V. V. A variant of mirror descent method for solving variational inequalities. In: Polyakova, L. N. (ed.) Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V. F. Demyanov). IEEE, 2017. P. 281–284.
Nomirovskii D. A., Rublyov V. V., Semenov V. V. Convergence of Two-Stage Method with Bregman Divergence for Solving Variational Inequalities. Cybernetics and Systems Analysis. 2019. Vol. 55. P. 359–368.
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.
Vedel Y. I., Sandrakov G. V., Semenov V. V., Chabak L. M. Convergence of a Two-Stage Proximal Algorithm for the Equilibrium Problem in Hadamard Spaces. Cybernetics and Systems Analysis. 2020. Vol. 56. Issue 5. P. 784–792.
Vedel Y., Semenov V. Adaptive Extraproximal Algorithm for the Equilibrium Problem in Hadamard Spaces. In: Olenev N., Evtushenko Y., Khachay M., Malkova V. (eds.) Optimization and Applications. OPTIMA 2020. Lecture Notes in Computer Science, vol. 12422. Springer, Cham, 2020. P. 287–300.
Vedel Y. I., Sandrakov G. V., Semenov V. V. An Adaptive Two-Stage Proximal Algorithm for Equilibrium Problems in Hadamard Spaces. Cybernetics and Systems Analysis. 2020. Vol. 56. Issue 6. P. 978–989.
Semenov V., Vedel Y. Convergence of adaptive methods for equilibrium problems in Hadamard spaces. Proceedings of the 7th International Conference “Information Technology and Interactions" (IT&I-2020). Workshops Proceedings Kyiv, Ukraine, December 02-03, 2020. CEUR Workshop Proceedings, vol. 2845. 2021. P. 321–335.
Denisov S., Semenov V., Vedel Y. Adaptive Algorithm for Variational Inequality Problem Over the Set of Solutions the Equilibrium Problem. 2020 IEEE 2nd International Conference on Advanced Trends in Information Theory (ATIT), Kyiv, Ukraine, 2020. P. 325–329.
Vedel Y. I., Denisov S. V., Semenov V. V. An Adaptive Algorithm for the Variational Inequality Over the Set of Solutions of the Equilibrium Problem. Cybernetics and Systems Analysis. 2021. Vol. 57. Issue 1. P. 91–100.
Khanh P. D., Vuong P. T. Modified projection method for strongly pseudomonotone variational inequalities. J. Glob. Optim. 2014. Vol. 58. P. 341–350.
Bakushinskii A. B., Goncharskii A. V. Iterative Methods for Solving Ill-Posed Problems. Moscow: Nauka, 1989. 126 p.
Browder F. Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. USA. 1966. Vol. 56. No. 4. P. 1080–1086.
Browder F. E. Convergence of approximants of fixed points of nonexpansive nonlinear mappings in Banach spaces. Arch. Rational Mech. Anal. 1967. Vol. 24. P. 82–90.
Combettes P. L., Hirstoaga S. A. Equilibrium Programming in Hilbert Spaces. J. Nonlinear Convex Anal. 2005. Vol. 6. P. 117–136.
Apostol R. Ya., Grynenko A. A., Semenov V. V. Iterative algorithms for monotone bilevel variational inequalities. J. Num. Appl. Math. 2012. No. 1 (107). P. 3–14. (In Ukrainian)
