Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 57 >>> № 6 NOVEMBER — DECEMBER 2021
-->

UDC 517.988
V.V. Semenov1, S.V. Denisov2, A.V. Kravets3


1 Taras Shevchenko National University of Kyiv,
Kyiv, Ukraine

 semenov.volodya@gmail.com

2 Taras Shevchenko National University of Kyiv,
Kyiv, Ukraine

 sireukr@gmail.com

3 Taras Shevchenko National University of Kyiv,
Kyiv, Ukraine

 anya171kravets@gmail.com

ADAPTIVE TWO-STEP BREGMAN METHOD FOR VARIATIONAL INEQUALITIES

Abstract. The authors analyze the two-step Popov method with Bregman divergence and a new adaptive rule for choosing the step size, which does not require knowledge of Lipschitz constants and calculation of operator values at additional points. For variational inequalities with pseudo-monotone and Lipschitz continuous operators acting in a finite-dimensional normed linear space, a convergence theorem for the method is proved.

Keywords: variational inequality, pseudomonotonicity, Bregman divergence, two-step method, adaptivity, convergence.


FULL TEXT

REFERENCES

  1. Kinderlerer D., Stampakchia G. Introduction to variational inequalities and their applications [Russian translation]. Moscow: Mir, 1983. 256 p.

  2. Baiocchi K., Capelo A. Variational and quasi-variational inequalities [Russian translation]. Moscow: Science, 1988. 448 p.

  3. Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p. doi: https://doi.org/10.1007/978-1-4757-3005-0.

  4. Lyashko S.I., Klyushin D.A., Nomirovsky D.A., Semenov V.V. Identification of age-structured contamination sources in ground water. In: Boucekkline R., Hritonenko N., and Yatsenko Y. (eds.). Optimal Control of Age-Structured Populations in Economy, Demography, and the Environment. London; New York: Routledge, 2013. P. 277–292.

  5. Konnov I.V. Combined relaxation methods for variational inequalities. Berlin; Heidelberg; New York: Springer-Verlag, 2001. 181 p. https://doi.org/10.1007/978-3-642-56886-2.

  6. Facchinei F., Pang J.-S. Finite-dimensional variational inequalities and complementarily problem. Vol. 2. New York: Springer, 2003. 666 p.

  7. 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, Iss. 1. P. 67–76.

  8. Nurminsky E.A. Using additional small actions in Fejer's models of iterative algorithms. Zhurn. vychisl. matem. i matem. fiz. 2008. Vol. 48, N 12. P. 2121–2128.

  9. 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. https://doi.org/10.1615/JAutomatInfScien.v42.i4.20.

  10. 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. https://doi.org/10.1615/JAutomatInfScien.v50.i8.30.

  11. Gidel G., Berard H., Vincent P., Lacoste-Julien S. A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802.10551. 2018.

  12. Korpelevich G.M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. Vol. 12, N 4. P. 747–756.

  13. Tseng P. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Optimization. 2000. Vol. 38. P. 431–446.

  14. 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.

  15. 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.

  16. 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.

  17. Nemirovski A. Prox-method with rate of convergence 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. https:// doi.org/10.1137/S1052623403425629.

  18. Bregman L.M. A relaxation method for finding a common point for convex sets and its application to solving convex programming problems. Zhurn. vychisl. matem. i matem. fiz. 1967. N 3. P. 620–631.

  19. 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.

  20. Stonyakin F.S. On the adaptive proximal method for a class of variational inequalities and related problems. Trudy Inst. Mat. i Mekh. UrO RAN. 2019. Vol. 25, N 2. P. 185–197. https://doi.org/10.21538/0134-4889-2019-25-2-185-197.

  21. Stonyakin F.S., Vorontsova E.A., Alkousa M.S. New version of mirror prox for variational inequalities with adaptation to inexactness. In: Jaimovi M., Khachay M., Malkova V., Posypkin M. (eds.). Optimization and Applications. OPTIMA 2019. Communications in Computer and Information Science. Cham: Springer, 2020. Vol. 1145. P. 427–442. https:// doi.org/10.1007/978-3-030-38603-0_31.

  22. 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.

  23. 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, Iss. 5. P. 845–848. https://doi.org/10.1007/BF01141092.

  24. 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.

  25. 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. Cham: Springer, 2016. Vol. 115. P. 315–325. https://doi.org/10.1007/978-3-319-42056-1_10.

  26. 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.

  27. 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. Vol. 55, N 3. P. 359–368. https://doi.org/10.1007/s10559-019-00142-7.

  28. 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. Cham: Springer, 2019. P. 50–58. https://doi.org/10.1007/978-3-319-97885-7_6.

  29. Beck A. First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics, 2017. 479 p.




Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2021 Kibernetika.org. All rights reserved.