Successive Convex Relaxation Approach to Bilevel Quadratic Optimization Problems

The bilevel quadratic optimization problem is an instance of a hierarchical decision process where the lower level constraint set is dependent on decisions taken at the upper level. By replacing the lower level problem by the corresponding KKT optimality condition, the entire problem is transformed into a single level yet non-convex quadratic optimization problem involving the complementarity condition. In this paper, we adopt the successive convex relaxation method given by Kojima and Tunçel for approximating a nonconvex feasible region. By further exploiting the special structure of the bilevel quadratic optimization problem, we present new techniques which enable the efficient implementation of the successive convex relaxation method for the problem. The performance of these techniques is tested in a number of problems, and compared with some other procedures.