On a Global Search in Bilevel Optimization Problems with a Bimatrix Game at the Lower Level

This paper addresses one class of bilevel optimization problems (BOPs) with an equilibrium at the lower level (in optimistic statement). Namely, we study BOPs with a convex quadratic optimization problem under linear constraints at the upper level and with a parametric non-normalized bimatrix game at the lower one, where we need to find a Nash equilibrium. In order to construct numerical methods for the problem in question, first, we transform the original bilevel problem into a single-level nonconvex optimization problem by replacing the lower level with its optimality conditions. Then we apply the Exact Penalization Theory and Global Search Theory (GST) to the resulting problem. According to the standard research of nonconvex problems by the GST, we construct the d.c. representations of all nonconvex functions from the original statement (into the differences of two convex functions), formulate the Global Optimality Conditions in terms of reduced penalized problem, and develop local and global search method taking into account the specific of problem in question. The main feature of the developed methods consists in the possibility of varying the penalty parameter within the methods themselves.