УДК 517.988
АДАПТИВНЫЙ АЛГОРИТМ ДЛЯ ВАРИАЦИОННОГО НЕРАВЕНСТВА
НА МНОЖЕСТВЕ РЕШЕНИЙ ЗАДАЧИ О РАВНОВЕСИИ
Аннотация. Рассмотрены двухуровневые задачи: вариационные неравенства на множестве решений задач о равновесии.
Примером таких задач является поиск нормального равновесия Нэша. Для их решения предложен итераци-онный алгоритм,
сочетающий в себе идеи двухэтапного проксимального ме-тода, адаптивности и итеративной регуляризации.
В отличие от применяе-мых ранее правил выбора величины шага в предлагаемом алгоритме не проводится вычислений
значений бифункции в дополнительных точках, не требуются знания информации о липшицевых константах бифункции,
кон-стантах липшицевости и сильной монотонности оператора. Для монотонных бифункций липшицевого типа
и сильно монотонных липшицевых операто-ров доказана теорема о сильной сходимости алгоритма.
Показано, что пред-ложенный алгоритм применим к монотонным двухуровневым вариацион-ным неравенствам в гильбертовых пространствах.
Ключевые слова: двухуровневая задача, вариационное неравенство, задача о равновесии, двухэтапный проксимальный метод,
адаптивность, итератив-ная регуляризация, сильная сходимость.
ПОЛНЫЙ ТЕКСТ
Ведель Яна Игоревна,
аспирантка Киевского национального университета имени Тараса Шевченко,
yana.vedel@gmail.com
Денисов Cергей Викторович,
ассистент кафедры Киевского национального университета имени Тараса Шевченко,
sireukr@gmail.com
Семенов Владимир Викторович,
доктор физ.-мат. наук, профессор, профессор кафедры Киевского национального университета имени Тараса Шевченко,
semenov.volodya@gmail.com
СПИСОК ЛИТЕРАТУРЫ
- 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, N 4. P. 1080–1086.
- Browder F. Convergence of approximants of fixed points of nonexpansive non-linear mappings in Banach spaces. Arch. Rational Mech. Anal. 1967. Vol. 24. P. 82–90.
- Attouch H. Viscosity solutions of minimization problems. SIAM J. Optim. 1996. Vol. 6. Iss. 3. P. 769–806. https://doi.org/10.1137/S1052623493259616.
- Подиновский В.В., Гаврилов В.Н. Оптимизация по последовательно применяемым критериям. Москва: Сов. радио, 1975. 192 с.
- Kalashnikov V.V., Kalashnikova N.I. Solution of two-level variational inequality. Cybernetics and Systems Analysis. 1994. Vol. 30, N 4. P. 623–625. https://doi.org/10.1007/BF02366574.
- Коннов И.В. О системах вариационных неравенств. Изв. вузов. Матем. 1997. № 12. C. 79–88.
- Попов Л.Д. Лексикографические вариационные неравенства и некоторые приложения. Математическое программирование. Регуляризация и аппроксимация. Сб. статей. Тр. ИММ. 2002. T. 8, № 1. С. 103–115.
- Попов Л.Д. Об одноэтапном методе решения лексикографических вариационных неравенств. Изв. вузов. Матем. 1998. № 12. C. 71–81.
- Solodov M. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis. 2007. Vol. 14. P. 227–238.
- Semenov V.V. On the parallel proximal decomposition method for solving the problems of convex optimization. Journal of Automation and Information Sciences. 2010. Vol. 42, N 4. P. 13–18. https://doi.org/10.1615/JAutomatInfScien.v42.i4.20.
- Semenov V.V. A strongly convergent splitting method for systems of operator inclusions with monotone operators. Journal of Automation and Information Sciences. 2014. Vol. 46, N 5. P. 45–56. https://doi.org/10.1615/JAutomatInfScien.v46.i5.40.
- Semenov V.V. Hybrid splitting methods for the system of operator inclusions with monotone operators. Cybernetics and Systems Analysis. 2014. Vol. 50, N 5. P. 741–749. https://doi.org/ 10.1007/s10559-014-9664-y.
- Verlan D.A., Semenov V.V., Chabak L.M. A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators. Journal of Automation and Information Sciences. 2015. Vol. 47, N 7. P. 31–46. https://doi.org/10.1615/JAutomatInfScien.v47.i7.40.
- Kassay G., Radulescu V.D. Equilibrium problems and applications. London: Academic Press, 2019. xx+419 p.
- Antipin A.S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys. 1997. Vol. 37. P. 1285–1296. https://doi.org/10.1134/S0965542507120044.
- Mastroeni G. On auxiliary principle for equilibrium problems. In: Daniele P. et al. (eds.). Equilibrium Problems and Variational Models. Dordrecht: Kluwer Academic Publishers, 2003. P. 289–298. https://doi.org/10.1007/978-1-4613-0239-1.
- Combettes P.L., Hirstoaga S.A. Equilibrium programming in Hilbert spaces. J. Nonlinear Convex Anal. 2005. Vol. 6. P. 117–136.
- Quoc T.D., Muu L.D., Hien N.V. Extragradient algorithms extended to equilibrium problems. Optimization. 2008. Vol. 57. P. 749–776. https://doi.org/10.1080/02331930601122876.
- Lyashko S.I., Semenov V.V., Voitova T.A. Low-cost modification of Korpelevich’s methods for monotone equilibrium problems. Cybernetics and Systems Analysis. 2011. Vol. 47, N 4. P. 631–639. https://doi.org/10.1007/s10559-011-9343-1.
- Lyashko S.I., Semenov V.V. A new two-step proximal algorithm of solving the problem of equilibrium programming. In: Goldengorin B. (ed.). Optimization and Its Applications in Control and Data Sciences. Springer Optimization and Its Applications, 115. Cham: Springer, 2016. P. 315–325. https://doi.org/10.1007/978-3-319-42056-1_10.
- Semenov V.V. Strongly convergent algorithms for variational inequality problem over the set of solutions the equilibrium problems. In: Zgurovsky M.Z., Sadovnichiy V.A. (eds.). Continuous and Distributed Systems. Solid Mechanics and Its Applications, 211, Springer International Publishing Switzerland, 2014. P. 131–146. https://doi.org/10.1007/978-3-319-03146-0_10.
- Vedel Ya.I., Denisov S.V., Semenov V.V. Algorithm for variational inequality problem over the set of solutions the equilibrium problems. Journal of Numerical and Applied Mathematics. 2020. N 1 (133). P. 18–30.
- 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, N 1. P. 67–76.
- Kinderlehrer D., Stampacchia G. An introduction to variational inequalities and their applications. New York: Academic Press, 1980. Russian transl., Moscow: Mir, 1983. 256 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. A version of the mirror descent method to solve variational inequalities. Cybernetics and Systems Analysis. 2017. Vol. 53, N 2. P. 234–243. https://doi.org/10.1007/s10559-017-9923-9.
- 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, N 3. P. 377–383. https://doi.org/ 10.1007/s10559-019-00144-5.
- Malitsky Yu.V., Semenov V.V. An extragradient algorithm for monotone variational inequalities. Cybernetics and Systems Analysis. 2014. Vol. 50, N 2. P. 271–277. https://doi.org/10.1007/ s10559-014-9614-8.
