On solving bilevel optimization problems with a nonconvex lower level: the case of a bimatrix game. (English) Zbl 1489.90140
Pardalos, Panos (ed.) et al., Mathematical optimization theory and operations research. 20th international conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12755, 235-249 (2021).
Summary: This paper addresses the optimistic statement of one class of bilevel optimization problems (BOPs) with a nonconvex lower level. Namely, we study BOPs with a convex quadratic objective function at the upper level and with a bimatrix game at the lower level. It is known that the problem of finding a Nash equilibrium point in a bimatrix game is equivalent to the special nonconvex optimization problem with a bilinear structure. Nevertheless, we can replace such a lower level with its optimality conditions and transform the original bilevel problem into a single-level nonconvex optimization problem. Then we apply the original Global Search Theory (GST) for general D.C. optimization problems and the Exact Penalization Theory to the resulting problem. After that, a special method of local search, which takes into account the structure of the problem under consideration, is developed.
For the entire collection see [Zbl 1482.90002].
For the entire collection see [Zbl 1482.90002].
Keywords:
bilevel optimization; bilevel problems with a nonconvex lower level; optimistic solution; bimatrix game; Nash equilibrium; reduction theorem; problem with D.C. constraints; global search theory; exact penalization theory; local searchReferences:
| [1] | Dempe, S., Foundations of Bilevel Programming (2002), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1038.90097 |
| [2] | Dempe, S., Zemkoho, A. (eds.): Bilevel Optimization: Advances and Next Challenges. Springer International Publishing, New York (2020). doi:10.1007/978-3-030-52119-6 · Zbl 1470.90001 |
| [3] | Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Ann. Oper. Res., 153, 235-256 (2007) · Zbl 1159.90483 · doi:10.1007/s10479-007-0176-2 |
| [4] | Dempe, S.; Audet, C.; Hansen, P.; Savard, G., Bilevel programming, Essays and Surveys in Global Optimization, 165-193 (2005), Boston: Springer, Boston · Zbl 1136.90505 · doi:10.1007/0-387-25570-2_6 |
| [5] | Dempe, S.; Kalashnikov, VV; Perez-Valdes, GA; Kalashnykova, N., Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks (2015), Berlin-Heidelberg: Springer-Verlag, Berlin-Heidelberg · Zbl 1338.90005 · doi:10.1007/978-3-662-45827-3 |
| [6] | Stackelberg, HFV, Marktform und Gleichgewicht (1934), Wien: Springer, Wien · Zbl 1405.91003 |
| [7] | Mitsos, A.; Lemonidis, P.; Barton, PI, Global solution of bilevel programs with a nonconvex inner program, J. Global Optim., 42, 475-513 (2008) · Zbl 1163.90700 · doi:10.1007/s10898-007-9260-z |
| [8] | Lin, G-H; Xu, M.; Ye, JJ, On solving simple bilevel programs with a nonconvex lower level program, Math. Program., 144, 277-305 (2013) · Zbl 1301.65050 · doi:10.1007/s10107-013-0633-4 |
| [9] | Zhu, X.; Guo, P., Approaches to four types of bilevel programming problems with nonconvex nonsmooth lower level programs and their applications to newsvendor problems, Math. Methods Oper. Res., 86, 2, 255-275 (2017) · Zbl 1396.90097 · doi:10.1007/s00186-017-0592-2 |
| [10] | Hu, M.; Fukushima, M., Existence, uniqueness, and computation of robust Nash equilibria in a class of multi-leader-follower games, SIAM J. Optim., 23, 2, 894-916 (2013) · Zbl 1273.91094 · doi:10.1137/120863873 |
| [11] | Ramos, M.; Boix, M.; Aussel, D.; Montastruc, L.; Domenech, S., Water integration in eco-industrial parks using a multi-leader-follower approach, Comput. Chem. Eng., 87, 190-207 (2016) · doi:10.1016/j.compchemeng.2016.01.005 |
| [12] | Yang, Z.; Ju, Y., Existence and generic stability of cooperative equilibria for multi-leader-multi-follower games, J. Global Optim., 65, 3, 563-573 (2015) · Zbl 1414.91088 · doi:10.1007/s10898-015-0393-1 |
| [13] | Mazalov, V., Mathematical Game Theory and Applications (2014), New York: John Wiley & Sons, New York · Zbl 1309.91003 |
| [14] | Strekalovsky, AS; Orlov, AV, Bimatrix Games and Bilinear Programming (2007), Moscow: FizMatLit, Moscow · Zbl 1142.91002 |
| [15] | Orlov, AV; Gruzdeva, TV; Khachay, M.; Kochetov, Y.; Pardalos, P., The local and global searches in bilevel problems with a matrix game at the lower level, Mathematical Optimization Theory and Operations Research, 172-183 (2019), Cham: Springer, Cham · Zbl 1443.90284 · doi:10.1007/978-3-030-22629-9_13 |
| [16] | Törn, A.; Žilinskas, A., Global Optimization (1989), Heidelberg: Springer, Heidelberg · Zbl 0752.90075 · doi:10.1007/3-540-50871-6 |
| [17] | Strongin, R.G., Sergeyev, Ya.D.: Global Optimization with Non-convex Constraints. Sequential and Parallel Algorithms. Springer-Verlag, New York (2000). doi:10.1007/978-1-4615-4677-1 · Zbl 0987.90068 |
| [18] | Strekalovsky, AS, Elements of Nonconvex Optimization (2003), Novosibirsk: Nauka, Novosibirsk |
| [19] | Nocedal, J.; Wright, SJ, Numerical Optimization (2000), New York: Springer-Verlag, New York · Zbl 0930.65067 · doi:10.1007/978-0-387-40065-5 |
| [20] | Bonnans, J-F; Gilbert, JC; Lemarechal, C.; Sagastizabal, CA, Numerical Optimization: Theoretical and Practical Aspects (2006), Berlin-Heidelberg: Springer, Berlin-Heidelberg · Zbl 1108.65060 · doi:10.1007/978-3-540-35447-5 |
| [21] | Strekalovsky, AS, Global optimality conditions and exact penalization, Optim. Lett., 13, 3, 597-615 (2017) · Zbl 1432.90126 · doi:10.1007/s11590-017-1214-x |
| [22] | Strekalovsky, AS; Jaćimović, M.; Khachay, M.; Malkova, V.; Posypkin, M., On a global search in D.C. optimization problems, Optimization and Applications, 222-236 (2020), Cham: Springer, Cham · Zbl 1477.90075 · doi:10.1007/978-3-030-38603-0_17 |
| [23] | Strekalovsky, AS; Orlov, AV, Linear and Quadratic-linear Problems of Bilevel Optimization (2019), Novosibirsk: SB RAS Publishing, Novosibirsk |
| [24] | Orlov, AV; Strekalovsky, AS, Numerical search for equilibria in bimatrix games, Comput. Math. Math. Phys., 45, 947-960 (2005) · Zbl 1086.91006 |
| [25] | Orlov, AV, Numerical solution of bilinear programming problems, Comput. Math. Math. Phys., 48, 225-241 (2008) · Zbl 1224.90171 · doi:10.1134/S0965542508020061 |
| [26] | Gruzdeva, TV; Petrova, EG, Numerical solution of a linear bilevel problem, Comput. Math. Math. Phys., 50, 1631-1641 (2010) · Zbl 1224.90135 · doi:10.1134/S0965542510100015 |
| [27] | Strekalovsky, AS; Orlov, AV; Malyshev, AV, On computational search for optimistic solutions in bilevel problems, J. Global Optim., 48, 1, 159-172 (2010) · Zbl 1202.90219 · doi:10.1007/s10898-009-9514-z |
| [28] | Orlov, AV; Strekalovsky, AS; Batbileg, S., On computational search for Nash equilibrium in hexamatrix games, Optim. Lett., 10, 2, 369-381 (2014) · Zbl 1336.91010 · doi:10.1007/s11590-014-0833-8 |
| [29] | Orlov, AV; Kalyagin, VA; Pardalos, PM; Prokopyev, O.; Utkina, I., The global search theory approach to the bilevel pricing problem in telecommunication networks, Computational Aspects and Applications in Large-Scale Networks, 57-73 (2018), Cham: Springer, Cham · doi:10.1007/978-3-319-96247-4_5 |
| [30] | Orlov, AV; Kochetov, Y.; Bykadorov, I.; Gruzdeva, T., On a solving bilevel D.C.-convex optimization problems, Mathematical Optimization Theory and Operations Research, 179-191 (2020), Cham: Springer, Cham · Zbl 1460.90146 · doi:10.1007/978-3-030-58657-7_16 |
| [31] | Strekalovsky, AS; Orlov, AV; Dempe, S.; Zemkoho, A., Global search for bilevel optimization with quadratic data, Bilevel Optimization, 313-334 (2020), Cham: Springer, Cham · Zbl 1481.90245 · doi:10.1007/978-3-030-52119-6_11 |
| [32] | Mangasarian, OL; Stone, H., Two-person nonzero games and quadratic programming, J. Math. Anal. Appl., 9, 348-355 (1964) · Zbl 0126.36505 · doi:10.1016/0022-247X(64)90021-6 |
| [33] | Strekalovsky, A.S.: On local search in D.C. optimization problems. Appl. Math. Comput. 255, 73-83 (2015) · Zbl 1338.90327 |
| [34] | Tao, P.D., Souad, L.B.: Algorithms for solving a class of non convex optimization. Methods of subgradients. In: Hiriart-Urruty J.-B. (ed.) Fermat Days 85, pp. 249-271. Elservier Sience Publishers B.V., North Holland (1986) · Zbl 0638.90087 |
| [35] | Strekalovsky, A.S.: Local search for nonsmooth DC optimization with DC equality and inequality constraints. Accepted for publication. In: Bagirov, A. et al. (Eds.) Numerical Nonsmooth Optimization - State of the Art Algorithms (2020) |
| [36] | Ben-Tal, A.; Nemirovski, A., Non-Euclidean restricted memory level method for large-scale convex optimization, Math. Program., 102, 407-456 (2005) · Zbl 1066.90079 · doi:10.1007/s10107-004-0553-4 |
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.
