On the indefinite quadratic bilevel programming problem

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper, we consider the bilevel programming problem in which the objective function of both levels is indefinite quadratic and the feasible region is a convex polyhedron. At first, a method similar to simplex method to solve indefinite quadratic programming problem is developed. It is shown that the given problem is equivalent to maximizing a quasi-convex function over a feasible region comprised of faces of the polyhedron. Hence, there is an extreme point of the polyhedron that solves the problem. Finally, same method is employed to solve the problem when the variables are required to be integers. The solution method is illustrated with the help of an example.