The Improvement Function Reformulation for Graphs of Minimal Point Mappings

Abstract Graphs of minimal point mappings of parametric optimization problems appear in the definition of feasible sets of bilevel optimization problems and of semi-infinite optimization problems, and the intersection of multiple such graphs defines (generalized) Nash equilibria. This paper shows how minimal point graphs of nonconvex parametric optimization problems can be enclosed with the help of well structured problems with additional parameters. This enclosure coincides with the minimal point graph under mild assumptions. We specify our results to the setting of generalized Nash equilibrium problems. This well structured formulation of the enclosure makes it accessible to approximations by branch-and-bound methods. We provide corresponding numerical results in a separate paper.