Solving a class of bilevel programs with quadratic lower level

Martina Cerulli (1) , Antoine Oustry (1, 2) , Claudia d'Ambrosio (1) , Leo Liberti (1)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 ENPC - École des Ponts ParisTech

We focus on a particular class of bilevel programs with a quadratic lower-level problem, which can be obtained by reformulating semi-infinite problems with an infinite number of quadratically parametrized constraints. We propose a new approach to solve this class of bilevel programs, based on the dual of the lower-level problem, which can lead to a convex or a semidefinite programming problem, depending on the parametrization of the lower level with respect to the upper-level variables. This approach is compared with a new tailored cutting plane algorithm, which is proved to be convergent. The rate of convergence of this cutting plane algorithm, directly related to the iteration index, is derived when the upper-level objective function is strongly convex, and under a strict feasibility assumption. We successfully test the two proposed methods on two applications: the constrained quadratic regression and a zero-sum game with cubic payoff.

Mots clés: Bilevel programming; Semi-infinite programming; Semidefinite programming; Cutting Plane

Domaines: Mathématiques [math]; Optimisation et contrôle [math.OC]; Informatique [cs]

Martina Cerulli, Antoine Oustry, Claudia d'Ambrosio, Leo Liberti. Solving a class of bilevel programs with quadratic lower level. 2021. ⟨hal-03339887v1⟩