Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 57 >>> № 1 JANUARY — FEBRUARY 2021
-->

UDC 517.988
Ya.I. Vedel1, S.V. Denisov2, V.V. Semenov3


1 Taras Shevchenko National University of Kyiv,
Kyiv, Ukraine

 yana.vedel@gmail.com

2 Taras Shevchenko National University of Kyiv,
Kyiv, Ukraine

 sireukr@gmail.com

3 Taras Shevchenko National University of Kyiv,
Kyiv, Ukraine

 semenov.volodya@gmail.com

AN ADAPTIVE ALGORITHM FOR THE VARIATIONAL INEQUALITY OVER
THE SET OF SOLUTIONS OF THE EQUILIBRIUM PROBLEM

Abstract. In this paper, we consider bilevel problems: variational inequality problems over the set of solutions of the equilibrium problem. An example of such a problem is finding a normal Nash equilibrium. To solve these problems, an iterative algorithm is proposed that combines the ideas of a two-stage proximal method, adaptability, and iterative regularization. In contrast to the previously used rules for choosing the step size, the proposed algorithm does not calculate bifunction values at additional points and does not require knowledge of information on bifunction’s Lipschitz constants and operator’s Lipschitz and strong monotonicity constants. For monotone bifunctions of Lipschitz type and strongly monotone Lipschitz operators, the theorem on strong convergence of sequences generated by the algorithm is proved. It is shown that the proposed algorithm is applicable to monotone bilevel variational inequalities in Hilbert spaces.

Keywords: bilevel problem, variational inequality, equilibrium problem, two-stage proximal algorithm, adaptivity, iterative regularization, strong convergence.



FULL TEXT

REFERENCES

  1. Bakushinskii A.B., Goncharskii A.V. Iterative methods for solving ill-posed problems. Moscow: Nauka, 1989. 126 p.

  2. Browder F. Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. USA. 1966. Vol. 56, N 4. P. 1080-1086.

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

  4. Attouch H. Viscosity solutions of minimization problems. SIAM J. Optim. 1996. Vol. 6. Iss. 3. P. 769-806. https://doi.org/10.1137/S1052623493259616.

  5. Podinovsky V.V., Gavrilov V.N. Optimization according to consistently applied criteria [in Russian]. Moscow: Sov. radio, 1975. 192 p.

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

  7. Konnov I.V. Systems of variational inequalities. Izv. vuzov. Matem. 1997. N 12. P. 79-88.

  8. Popov L.D. Lexicographic variational inequalities and some applications. Mathematical programming. Regularization and approximation. Coll. articles. Tr. IMM. 2002. Vol. 8, N 1. P. 103-115.

  9. Popov L.D. On a one-stage method for solving lexicographic variational inequalities. Izv. vuzov. Matem. 1998. N 12. P. 71-81.

  10. Solodov M. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis. 2007. Vol. 14. P. 227-238.

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

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

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

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

  15. Kassay G., Radulescu V.D. Equilibrium problems and applications. London: Academic Press, 2019. xx+419 p.

  16. Antipin A.S. Equilibrium programming: Proximal methods. Comput. Math. Math. Phys. 1997. Vol. 37. P. 1285-1296. https://doi.org/10.1134/S0965542507120044.

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

  18. Combettes P.L., Hirstoaga S.A. Equilibrium programming in Hilbert spaces. J. Nonlinear Convex Anal. 2005. Vol. 6. P. 117-136.

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

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

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

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

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

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

  25. Kinderlehrer D., Stampacchia G. An introduction to variational inequalities and their applications. New York: Academic Press, 1980. Russian transl., Moscow: Mir, 1983. 256 p.

  26. Bauschke H.H., Combettes P.L. Convex analysis and monotone operator theory in Hilbert spaces. Berlin; Heidelberg; New York: Springer, 2011. 408 p.

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

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

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




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