Global optimization of nonlinear bilevel programming problems

A novel technique that addresses the solution of the general nonlinear bilevel programming problem to global optimality is presented. Global optimality is guaranteed for problems that involve twice differentiable nonlinear functions as long as the linear independence constraint qualification condition holds for the inner problem constraints. The approach is based on the relaxation of the feasible region by convex underestimation, embedded in a branch and bound framework utilizing the basic principles of the deterministic global optimization algorithm, alpha BB [2, 4, 5, 11]. Epsilon global optimality in a finite number of iterations is theoretically guaranteed. Computational studies on several literature problems are reported.