Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints

• Published in: Journal of global optimization 2019-10, Vol.75 (2), p.341-392
• Main Authors: Djelassi, Hatim, Glass, Moll, Mitsos, Alexander
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Science; Convergence; Coupling; Dependent variables; Discretization; Mathematics; Mathematics and Statistics; Metric system; Nonlinear programming; Operations Research/Decision Theory; Optimization; Real Functions; Variables
• ISSN: 0925-5001; 1573-2916
• DOI: 10.1007/s10898-019-00764-3

Discretization-based algorithms are proposed for the global solution of mixed-integer nonlinear generalized semi-infinite (GSIP) and bilevel (BLP) programs with lower-level equality constraints coupling the lower and upper level. The algorithms are extensions, respectively, of the algorithm proposed by Mitsos and Tsoukalas (J Glob Optim 61(1):1–17, 2015 . https://doi.org/10.1007/s10898-014-0146-6 ) and by Mitsos (J Glob Optim 47(4):557–582, 2010 . https://doi.org/10.1007/s10898-009-9479-y ). As their predecessors, the algorithms are based on bounding procedures, which achieve convergence through a successive discretization of the lower-level variable space. In order to cope with convergence issues introduced by coupling equality constraints, a subset of the lower-level variables is treated as dependent variables fixed by the equality constraints while the remaining lower-level variables are discretized. Proofs of finite termination with ε -optimality are provided under appropriate assumptions, the preeminent of which are the existence, uniqueness, and continuity of the solution to the equality constraints. The performance of the proposed algorithms is assessed based on numerical experiments.