АДАПТИВНИЙ МЕТОД ОПЕРАТОРНОЇ ЕКСТРАПОЛЯЦІЇ ДЛЯ ВАРІАЦІЙНИХ НЕРІВНОСТЕЙ В БАНАХОВИХ ПРОСТОРАХ

Завантажити статтю

Семенов Володимир Вікторовичдоктор фізико-математичних наук, професор Київського національного університету імені Тараса Шевченка

Денисов Сергій Вікторовичасистент Київського національного університету імені Тараса Шевченка

pages 82-92

DOI: http://doi.org/10.34229/1028-0979-2021-5-7

Багато актуальних задач дослідження операцій та математичної фізики може бути записано у формі варіаційних нерівностей. Розробка та дослідження алгоритмів розв’язання варіаційних нерівностей є напрямком прикладного нелінійного аналізу, що активно розвивається. Відзначимо, що часто негладкі задачі оптимізації можуть ефективно розв’язуватися, якщо переформулювати їх у вигляді сідлових задач і застосувати алгоритми розв’язання варіаційних нерівностей. Останнім часом намітився прогрес у вивченні алгоритмів для задач в банахових просторах. Це обумовлено широким залученням результатів та конструкцій геометрії банахових просторів. В роботі запропоновано та досліджено новий алгоритм для розв’язання варіаційних нерівностей в банаховому просторі. Пропонований алгоритм є адаптивним варіантом «forward-reflected-backward algorithm», де використовується правило поновлення величини кроку, що не вимагає знання ліпшицевої константи оператора. Крім того, замість метричної проекції на допустиму множину використовується узагальнена проекція Альбера. Перевагою використання алгоритму є лише одне обчислення на ітераційному кроці проекції на допустиму множину. Для варіаційних нерівностей з монотонними, ліпшицевими операторами, що діють в 2-рівномірно опуклому та рівномірно гладкому банаховому просторі, доведено теорему про слабку збіжність методу.

Kлючові слова: варіаційна нерівність, монотонний оператор, алгоритм, збіжність, адаптивність, 2-рівномірно опуклий банаховий простір, рівномірно гладкий банаховий простір.

  1. Лионс Ж.-Л., Мадженес Э. Неоднородные граничные задачи и их приложения. М. : Мир, 1971. 371 с.
  2. Киндерлерер Д., Стампаккья Г. Введение в вариационные неравенства и их приложения. М. : Мир, 1983. 256 c.
  3. Nagurney A. Network economics: a variational inequality approach. Dordrecht : Kluwer Academic Publishers, 1999. 325 p.
  4. Alber Y., Ryazantseva I. Nonlinear Ill-posed problems of monotone type. Dordrecht: Springer, 2006. 410 p.
  5. Lyashko S.I., Klyushin D.A., Nomirovsky D.A., Semenov V.V. Identification of age-structured contamination sources in ground water. In: R. Boucekkline, N. Hritonenko, and Y. Yatsenko (eds.). Optimal Control of Age-Structured Populations in Economy, Demography, and the Environment. 2013. P. 277–292.
  6. Facchinei F., Pang J.-S. Finite-dimensional variational inequalities and complementarity problems. V. II. New York : Springer, 2003. 666 p.
  7. A variational inequality perspective on generative adversarial networks. G. Gidel, H. Berard,
    G. Vignoud, P. Vincent, S. Lacoste-Julien. Published as a conference paper at ICLR 2019. arXiv preprint arXiv:1802.10551. 2018. P. 1–38.
  8. 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. 15. P. 229–251. https://doi.org/10.1137/ S1052623403425629.
  9. Korpelevich G.M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. 12, N 4. P. 747–756.
  10. Censor Y., Gibali A., Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. Journal of Optimization Theory and Applications. 2011. 148. P. 318–335. https://doi.org/10.1007/s10957-010-9757-3.
  11. Semenov V.V. Modified extragradient method with Bregman divergence for variational inequalities. Journal of Automation and Information Sciences. 2018. 50, N 8. P. 26–37. https:// doi.org/10.1615/JAutomatInfScien.v50.i8.30.
  12. Tseng P. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization. 2000. 38. P. 431–446. https://doi.org/ 10.1137/S0363012998338806.
  13. Shehu Y. Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces. Results in Math. 2019. 74. https://doi.org/10.1007/s00025-019-1061-4.
  14. Shehu Y. Single projection algorithm for variational inequalities in Banach spaces with application to contact problem. Acta Math. Sci. 2020. 40. P. 1045–1063. https://doi.org/10.1007/s10473-020-0412-2.
  15. Yang J., Cholamjiak P., Sunthrayuth P. Modified Tseng's splitting algorithms for the sum of two monotone operators in Banach spaces. AIMS Mathematics. 2021. 6, N 5. P. 4873–4900. https://doi.org/10.3934/math.2021286.
  16. Cholamjiak P., Shehu Y. Inertial forward-backward splitting method in Banach spaces with application to compressed sensing. Appl. Math. 2019. 64. P. 409–435. https://doi.org/ 10.21136/AM.2019.0323-18.
  17. 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. 47, N 7. P. 31–46. https://doi.org/10.1615/JAutomatInfScien.v47.i7.40.
  18. Bach F., Levy K.Y. A universal algorithm for variational inequalities adaptive to smoothness and noise. arXiv preprint arXiv:1902.01637. 2019. P. 1–33.
  19. Antonakopoulos K., Belmega V., Mertikopoulos P. An adaptive mirror-prox method for variational inequalities with singular operators. In Advances in Neural Information Processing Systems 32 (NeurIPS). 2019. P. 8455–8465.
  20. Stonyakin F.S., Vorontsova E.A., Alkousa M.S. New version of mirror prox for variational inequalities with adaptation to inexactness. In M. Jacimovic, M. Khachay, V. Malkova, M. Posypkin (eds.). Optimization and Applications. OPTIMA 2019. Communications in Computer and Information Science. Cham : Springer, 2020. 1145. P. 427–442. https://doi.org/10.1007/978-3-030-38603-031.
  21. Denisov S.V., Semenov V.V., Stetsyuk P.I. Bregman extragradient method with monotone rule of step adjustment. Cybernetics and Systems Analysis. 2019. 55, N 3. P. 377–383. https:// doi.org/10.1007/s10559-019-00144-5.
  22. 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. 51, N 6. P. 12–24. https:// doi.org/10.1615/JAutomatInfScien.v51.i6.20.
  23. Vedel Y.I., Golubeva E.N., Semenov V.V., Chabak L.M. Adaptive extraproximal algorithm for the equilibrium problem in the hadamard spaces. Journal of Automation and Information Sciences. 2020. 52, N 8. P. 46–58. https://doi.org/10.1615/JAutomatInfScien.v52.i8.40.
  24. Bregman L.M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics. 1967. 7, N 3. P. 200–217. https://doi.org/10.1016/0041-5553(67)90040-7.
  25. 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. 28, N 5. P. 845–848. https://doi.org/10.1007/BF01141092.
  26. Malitsky Yu.V., Semenov V.V. An extragradient algorithm for monotone variational inequalities. Cybernetics and Systems Analysis. 2014. 50, N 2. P. 271–277. https://doi.org/10.1007/s10559-014-9614-8.
  27. 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. Cham :Springer. 2016. 115. P. 315–325. https://doi.org/10.1007/978-3-319-42056-1_10.
  28. Chabak L., Semenov V., Vedel Y. A new non-euclidean proximal method for equilibrium problems. In O. Chertov, T. Mylovanov, Y. Kondratenko, J. Kacprzyk, V. Kreinovich, V. Stefanuk (eds.). Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018. Advances in Intelligent Systems and Computing. Cham : Springer, 2019. 836. P. 50–58. https://doi.org/10.1007/978-3-319-97885-7_6.
  29. Nomirovskii D.A., Rublyov B.V., Semenov V.V. Convergence of two-stage method with Bregman divergence for solving variational inequalities. Cybernetics and Systems Analysis. 2019. 55, N 3. P. 359–368. https://doi.org/10.1007/s10559-019-00142-7.
  30. Gibali A., Thong D.V. A new low-cost double projection method for solving variational ine-qualities. Optim. Eng. 2020. 21. P. 1613–1634. https://doi.org/10.1007/s11081-020-09490-2.
  31. Malitsky Y., Tam M.K. A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization. 2020. 30, N 2. P. 1451–1472. https: //doi.org/ 10.1137/18M1207260.
  32. Csetnek E.R., Malitsky Y., Tam M.K. Shadow Douglas-Rachford splitting for monotone inclusions. Appl Math Optim. 2019. 80. P. 665–678. https://doi.org/10.1007/s00245-019-09597-8.
  33. Cevher V., Vu B.C. A reflected forward-backward splitting method for monotone inclusions involving lipschitzian operators. Set-Valued and Variational Analysis. 2021. 29. P 163–174. https://doi.org/10.1007/s11228-020-00542-4.
  34. Дистель Дж. Геометрия банаховых пространств. Киев : Вища школа, 1980. 215 с.
  35. Beauzamy B. Introduction to Banach spaces and their geometry. Amsterdam : North-Holland, 1985. 307 p.
  36. Alber Y.I. Metric and generalized projection operators in Banach spaces: properties and applications. In Theory and Applications of Nonlinear Operators of Accretive and Monotone Type. New York : Dekker, 1996. 178. P. 15–50.
  37. Vainberg M.M. Variational method and method of monotone operators in the theory of nonlinear equations. New York : Wiley, 1974. 356 p.
  38. Aoyama K., Kohsaka F. Strongly relatively nonexpansive sequences generated by firmly nonexpansive-like mappings. Fixed Point Theory and Appl. 2014. 95. https://doi.org/10.1186/1687-1812-2014-95.
  39. Bot R.I., Csetnek E.R., Vuong P.T. The forward-backward-forward method from continuous and discrete perspective for pseudo-monotone variational inequalities in Hilbert spaces. European Journal of Operational Research. 2020. 287, N 1. P. 49–60. https://doi.org/ 10.1016/j.ejor.2020.04.035.