УДК 517.988
БРЭГМАНОВСКИЙ ЭКСТРАГРАДИЕНТНЫЙ МЕТОД
С МОНОТОННОЙ
РЕГУЛИРОВКОЙ ШАГА
Аннотация. Предложен новый вариант экстраградиентного метода для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами, действующими в конечномерном линейном нормированном пространстве. В методе использовано расхождение (расстояние) Брэгмана вместо евклидового расстояния и новая регулировка величины шага, не требующая знания константы Липшица для оператора. В отличие от применявшихся ранее правил выбора величины шага в предлагаемом методе не требуется дополнительных вычислений значений оператора и прокс-отображения. Доказана теорема сходимости метода.
Ключевые слова: вариационное неравенство, псевдомонотонность, условие Липшица, экстраградиентный метод, расхождение Брэгмана, сходимость.
ПОЛНЫЙ ТЕКСТ
Денисов Cергей Викторович,
ассистент кафедры Киевского национального университета имени Тараса Шевченко,
sireukr@gmail.com
Семёнов Владимир Викторович,
доктор. физ.-мат. наук, профессор, профессор кафедры Киевского национального университета имени Тараса Шевченко,
semenov.volodya@gmail.com
Стецюк Петр Иванович,
доктор. физ.-мат. наук, старший научный сотрудник, заведующий отделом Института кибернетики им. В.М. Глушкова НАН Украины,
stetsyukp@gmail.com
СПИСОК ЛИТЕРАТУРЫ
- Байокки К., Капело А. Вариационные и квазивариационные неравенства. Москва: Наука, 1988. 448 с.
- Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p.
- Tseng P. A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 2000. Vol. 38. P. 431–446.
- Facchinei F., Pang J.-S. Finite-dimensional variational inequalities and complementarily problem. Vol. 2. New York: Springer, 2003. 666 p.
- Stetsyuk P.I., Fesiuk O.V., Khomyak O.N. The generalized ellipsoid method. Cybernetics and Systems Analysis. 2018. Vol. 54, N 4. P. 576–584.
- Nesterov Yu. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 2007. Vol. 109, Iss. 2–3. P. 319–344.
- Нурминский Е.А. Использование дополнительных малых воздействий в фейеровских моделях итеративных алгоритмов. Журнал вычислительной математики и математической физики. 2008. T. 48, № 12. С. 2121–2128.
- 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, Iss. 4. P. 13–18.
- 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, Iss. 5. P. 45–56.
- 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.
- Yang J., Liu H.W. Strong convergence result for solving monotone variational inequalities in Hilbert space. Numerical Algorithms. 2018. DOI: https://doi.org/10.1007/s11075-018-0504-4.
- Gidel G., Berard H., Vincent P., Lacoste-Julien S. A Variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802.10551. 2018.
- Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач. Экономика и математические методы. 1976. Т. 12, № 4. С. 747–756.
- Хоботов Е.Н. О модификации экстраградиентного метода для решения вариационных неравенств и некоторых задач оптимизации. Журнал вычислительной математики и математической физики. 1987. Т. 27, № 10. С. 1462–1473.
- Semenov V.V. Strongly convergent algorithms for variational inequality problem over the set of solutions the equilibrium problems. In: Continuous and Distributed Systems. Solid Mechanics and Its Applications. Zgurovsky M.Z., Sadovnichiy V.A. (Eds.). Springer International Publishing, 2014. Vol. 211. P. 131–146.
- Denisov S.V., Semenov V.V., Chabak L.M. Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators. Cybernetics and Systems Analysis. 2015. Vol. 51, N 5. P. 757–765.
- 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, Iss. 7. P. 31–46.
- 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 Journal on Optimization. 2004. Vol. 15. P. 229–251.
- Semenov V.V. Modified extragradient method with bregman divergence for variational inequalities. Journal of Automation and Information Sciences. 2018. Vol. 50, Iss. 8. P. 26–37.
- 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.
- Chabak L., Semenov V., Vedel Y. A new non-Euclidean proximal method for equilibrium problems. In: Recent Developments in Data Science and Intelligent Analysis of Information: Proc. XVIII ICDSIAI 2018. Advances in Intelligent Systems and Computing. Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (Eds.) Cham: Springer, 2019. Vol. 836. P. 50–58.
- Номировский Д.А., Рублев Б.В., Семёнов В.В. Сходимость двухэтапного метода с расхождением Брэгмана для вариационных неравенств. Кибернетика и системный анализ. 2019. Т. 55, № 3. С. 17–27.
- Lyashko S.I., Semenov V.V. A new two-step proximal algorithm of solving the problem of equilibrium programming. In: Optimization and Its Applications in Control and Data Sciences. Springer Optimization and Its Applications. Goldengorin B. (Ed.). Cham: Springer, 2016. Vol. 115. P. 315–325.
- Beck A. First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics, 2017. 479 p.