Bilevel polynomial programs and semidefinite relaxation methods

A bilevel program is an optimization problem whose constraints involve the solution set to another optimization problem parameterized by upper level variables. This paper studies bilevel polynomial programs (BPPs), i.e., all the functions are polynomials. We reformulate BPPs equivalently as semi-infinite polynomial programs (SIPPs), using Fritz John conditions and Jacobian representations. Combining the exchange technique and Lasserre-type semidefinite relaxations, we propose a numerical method for solving BPPs. For simple BPPs, we prove the convergence to global optimal solutions. Numerical experiments are presented to show the efficiency of the proposed algorithm.