Discretization algorithms for generalized semi-infinite programs with coupling equality constraints under local solution stability

Abstract Existing algorithms for generalized semi-infinite programs can only handle lower-level constraints containing equality constraints depending on upper-level variables (so-called coupling equality constraints) under limiting assumptions. More specifically, discretization-based algorithms require that the coupling equality constraints result in some lower-level variables being determined uniquely as implicit functions of the other lower-level and upper-level variables. We propose an adaptation of the discretization-based algorithm of Blankenship & Falk and demonstrate it can handle coupling equality constraints under the weaker assumption of stability of the solution set for these constraints in the sense of Lipschitz lower semi-continuity. The key idea is to allow a perturbation of the lower-level variable values from discretization points in connection with changes in the upper-level variables in the discretized upper-level problem. We enforce that these perturbed values satisfy the coupling equality constraints while remaining close to the discretization point, provided we can guarantee the stability of the solution in the sense that a nearby solution exists for small changes of the upper-level variables. We provide concrete realizations of the algorithm for three different situations: i ) when knowledge about a certain Lipschitz constant is available, ii ) when the coupling equality constraints are assumed to have full rank, and iii ) when the coupling equality constraints are additionally linear in the lower-level variables. Numerical experiments on small test problems and a physically motivated problem related to power flow illustrate that the approach can be successfully applied to solve the challenging problems, but is currently limited in terms of scalability.