An adaptive algorithm for the variational inequality over the set of solutions of the equilibrium problem. (English. Russian original) Zbl 1471.49009
Cybern. Syst. Anal. 57, No. 1, 91-100 (2021); translation from Kibern. Sist. Anal. 57, No. 1, 104-114 (2021).
Summary: In the paper, we consider bilevel problems: variational inequality problems over the set of solutions of the equilibrium problem. Finding normal Nash equilibrium is an example of such a problem. To solve these problems, an iterative algorithm is proposed that combines the ideas of the 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. The proposed algorithm is shown to be applicable to monotone bilevel variational inequalities in Hilbert spaces.
MSC:
| 49J40 | Variational inequalities |
| 47J20 | Variational and other types of inequalities involving nonlinear operators (general) |
| 65K10 | Numerical optimization and variational techniques |
Keywords:
bilevel problem; variational inequality; equilibrium problem; two-stage proximal algorithm; adaptivity; iterative regularization; strong convergenceReferences:
| [1] | Bakushinskii, AB; Goncharskii, AV, Iterative Methods for Solving Ill-Posed Problems [in Russian] (1989), Moscow: Nauka, Moscow · Zbl 0676.65050 |
| [2] | Browder, F., Existence and approximation of solutions of nonlinear variational inequalities, Proc. Nat. Acad. Sci. USA, 56, 4, 1080-1086 (1966) · Zbl 0148.13502 · doi:10.1073/pnas.56.4.1080 |
| [3] | Browder, F., Convergence of approximants of fixed points of nonexpansive non-linear mappings in Banach spaces, Arch. Rational Mech. Anal., 24, 82-90 (1967) · Zbl 0148.13601 · doi:10.1007/BF00251595 |
| [4] | Attouch, H., Viscosity solutions of minimization problems, SIAM J. Optim., 6, 3, 769-806 (1996) · Zbl 0859.65065 · doi:10.1137/S1052623493259616 |
| [5] | V. V. Podinovskii and V. N. Gavrilov, Optimization by Sequentially Applied Criteria [in Russian], Sov. Radio, Moscow (1975). |
| [6] | Kalashnikov, VV; Kalashnikova, NI, Solution of two-level variational inequality, Cybern. Syst. Analysis, 30, 4, 623-625 (1994) · Zbl 0834.49009 · doi:10.1007/BF02366574 |
| [7] | I. V. Konnov, “On systems of variational inequalities,” Izv. Vuzov, Matematika, No. 12, 79- 88 (1997). · Zbl 0949.49004 |
| [8] | Popov, LD, Lexicographic variational inequalities and some applications, Mathematical Programming. Regularization and Approximation. A Collection of Papers, Tr. IMM, 8, 1, 103-115 (2002) · Zbl 1116.49304 |
| [9] | L. D. Popov, “A one-stage method of solving lexicographic variational inequalities,” Izv. Vuzov, Matematika, No. 12, 71-81 (1998). |
| [10] | Solodov, M., An explicit descent method for bilevel convex optimization, J. of Convex Analysis, 14, 227-238 (2007) · Zbl 1145.90081 |
| [11] | Semenov, VV, On the parallel proximal decomposition method for solving the problems of convex optimization, J. Autom. Inform. Sci., 42, 4, 13-18 (2010) · doi:10.1615/JAutomatInfScien.v42.i4.20 |
| [12] | Semenov, VV, A strongly convergent splitting method for systems of operator inclusions with monotone operators, J. Autom. Inform. Sci., 46, 5, 45-56 (2014) · doi:10.1615/JAutomatInfScien.v46.i5.40 |
| [13] | Semenov, VV, Hybrid splitting methods for the system of operator inclusions with monotone operators, Cybern. Syst. Analysis, 50, 5, 741-749 (2014) · Zbl 1317.65128 · doi:10.1007/s10559-014-9664-y |
| [14] | Verlan, DA; Semenov, VV; Chabak, LM, A strongly convergent modified extragradient method for variational inequalities with non-Lipschitz operators, J. Autom. Inform. Sci., 47, 7, 31-46 (2015) · doi:10.1615/JAutomatInfScien.v47.i7.40 |
| [15] | G. Kassay and V. D. Radulescu, Equilibrium Problems and Applications, Acad. Press, London (2019). · Zbl 1448.47005 |
| [16] | Antipin, AS, Equilibrium programming: Proximal methods, Comput. Math. Math. Phys., 37, 1285-1296 (1997) · Zbl 0944.90083 · doi:10.1134/S0965542507120044 |
| [17] | G. Mastroeni, “On auxiliary principle for equilibrium problems,” in: P. Daniele et al. (eds.), Equilibrium Problems and Variational Models, Kluwer Acad. Publ., Dordrecht (2003), pp. 289-298. doi:10.1007/978-1-4613-0239-1. · Zbl 1069.49009 |
| [18] | Combettes, PL; Hirstoaga, SA, Equilibrium programming in Hilbert spaces, J. Nonlinear Convex Anal., 6, 117-136 (2005) · Zbl 1109.90079 |
| [19] | Quoc, TD; Muu, LD; Hien, NV, Extragradient algorithms extended to equilibrium problems, Optimization, 57, 749-776 (2008) · Zbl 1152.90564 · doi:10.1080/02331930601122876 |
| [20] | Lyashko, SI; Semenov, VV; Voitova, TA, Low-cost modification of Korpelevich’s methods for monotone equilibrium problems, Cybern. Syst. Analysis, 47, 4, 631-639 (2011) · Zbl 1297.49014 · doi:10.1007/s10559-011-9343-1 |
| [21] | S. I. Lyashko and V. V. Semenov, “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, 115, Springer, Cham (2016), pp. 315-325. doi:10.1007/978-3-319-42056-1_10. · Zbl 1354.90172 |
| [22] | V. V. Semenov, “Strongly convergent algorithms for variational inequality problem over the set of solutions the equilibrium problems,” in: M. Z. Zgurovsky and V. A. Sadovnichiy (eds.), Continuous and Distributed Systems. Solid Mechanics and Its Applications, 211, Springer Intern. Publ., Switzerland (2014), pp. 131-146. doi:10.1007/978-3-319-03146-0_10. · Zbl 1325.65096 |
| [23] | Ya. I. Vedel, S. V. Denisov, and V. V. Semenov, “Algorithm for variational inequality problem over the set of solutions the equilibrium problems,” J. of Numerical and Applied Math., No. 1 (133), 18-30 (2020). |
| [24] | Popov, LD, On schemes for the formation of a master sequence in a regularized extragradient method for solving variational inequalities, Russian Mathematics, 48, 1, 67-76 (2004) · Zbl 1083.49009 |
| [25] | D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and their Applications, Acad. Press, New York (1980). · Zbl 0457.35001 |
| [26] | Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), Berlin-Heidelberg-New York: Springer, Berlin-Heidelberg-New York · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7 |
| [27] | Semenov, VV, A version of the mirror descent method to solve variational inequalities, Cybern. Syst. Analysis, 53, 2, 234-243 (2017) · Zbl 1384.49014 · doi:10.1007/s10559-017-9923-9 |
| [28] | Denisov, SV; Semenov, VV; Stetsyuk, PI, Bregman extragradient method with monotone rule of step adjustment, Cybern. Syst. Analysis, 55, 3, 377-383 (2019) · Zbl 1493.47087 · doi:10.1007/s10559-019-00144-5 |
| [29] | Malitsky, YV; Semenov, VV, An extragradient algorithm for monotone variational inequalities, Cybern. Syst. Analysis, 50, 2, 271-277 (2014) · Zbl 1311.49024 · doi:10.1007/s10559-014-9614-8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
