Introduction to Mathematical Programming with Equilibrium Constraints (MPECs) and Bilevel Optimization

Louis Shuo Wang · 2026

Read Introduction to Mathematical Programming with Equilibrium Constraints (MPECs) and Bilevel Optimization by Louis Shuo Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00386.txt.

Introduction

Louis Shuo Wang offers an introduction to mathematical programs with equilibrium constraints, known as MPECs, and to the closely related bilevel optimization problems. These are optimization problems with a twist: part of the feasible set is defined by another problem. That inner problem might be an optimization, a variational inequality, a complementarity system, or an equilibrium model.

As an introduction, the paper explains the objects before judging them. It motivates MPECs through applications, so readers see why a leader's choice might be constrained by a follower's best response. It then presents the main equivalent formulations of equilibrium constraints, which recast the tangled feasible set in workable forms. Finally, it summarizes the basic existence theory, the conditions under which an optimal solution is guaranteed to exist at all.

Catalog record

CREATORLouis Shuo Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00386

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Introduction to Mathematical Programming with Equilibrium Constraints (MPECs) and Bilevel Optimization Louis Shuo Wang Abstract Our aim is to explain mathematical programs with equilibrium constraints (MPECs), motivate them through applications, present the main equivalent formulations of equilibrium constraints, and summarize the basic existence theory for optimal solutions. The central message is that an MPEC is an optimization problem whose feasible set is partly defined by another optimization, variational inequality, complementarity system, or equilibrium model. 1 Introduction and Big Picture An MPEC is an optimization problem in which part of the feasible set is defined implicitly through an equilibrium problem. The upper level chooses variables (x,y) to optimize a global objective, while lower-level feasibility of y is determined by a variational inequality, complementarity problem, or optimization problem parameterized by x . This structure arises naturally in economics, engineering design, transportation, mechanics, robotics, and game theory. It generalizes bilevel programming and complementarity-constrained optimization. It also introduces major analytical challenges: nonconvex feasible regions, possible loss of closedness, nonsmoothness, and multi-valued lower-level response maps. Upper-level decision choose (x,y) Minimize f(x,y) Joint constraints (x,y)\in Z Lower-level equilibrium y\in S(x) VI \operatorname{VI}(F(x,\cdot),C(x)) Complementarity 0\leq a\perp b\geq 0 Lower optimization y\in\operatorname*{argmin}\theta(x,y) 2 A One-Page Workshop Recap Topic Key message MPEC definition Optimize an upper-level objective subject to a lower-level equilibrium. VI form y\in C(x) and (v-y)^{T}F(x,y)\geq 0 for all v\in C(x) . Complementarity form Cone-constrained VIs become generalized complementarity systems. KKT form Valid when lower-level convex constraints admit multipliers under an appropriate CQ. Fischer–Burmeister form Use \phi(a,b)=0 to encode 0\leq a\perp b\geq 0 ; for g\leq 0 , use slack u=-g\geq 0 . Implicit form If S(x)=\{y(x)\} , the MPEC becomes an optimization problem in x alone. Existence Need continuous objective, closed feasible region, and bounded lower level set. Main warning Closedness of Z is not enough; the graph of the equilibrium map must also be closed. 3 Problem Formulation 3.1 The general MPEC model Let f:\mathbb{R}^{n+m}\to\mathbb{R},\qquad F:\mathbb{R}^{n+m}\to\mathbb{R}^{m}, let Z\subset\mathbb{R}^{n+m} be nonempty and closed, and let C:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m} be a set-valued map with nonempty closed convex values on the domain of interest. Define X=\{x\in\mathbb{R}^{n}:(x,y)\in Z\text{ for some }y\in\mathbb{R}^{m}\}, and assume X\subset\operatorname{dom}(C) . For each x\in X , let S(x) denote the solution set of the variational inequality y\in C(x),\qquad(v-y)^{T}F(x,y)\geq 0\quad\forall v\in C(x). Then the MPEC is \displaystyle\min_{x,y} \displaystyle f(x,y) (MPEC) \displaystyle\text{s.t.} \displaystyle(x,y)\in Z, \displaystyle y\in S(x). Its feasible region is \mathcal{F}=Z\cap\operatorname{Gr}(S), where \operatorname{Gr}(S)=\{(x,y)\in\mathbb{R}^{n+m}:y\in S(x)\}. 3.2 Interpretation of the model ingredients [label=()] 1. f(x,y) is the upper-level objective. 2. Z collects joint constraints on (x,y) . 3. F(x,y) defines the lower-level equilibrium condition. 4. C(x) is the lower-level feasible set for y given x . 5. S(x) is the lower-level solution map, also called the reaction map. 3.3 Bilevel programming as a special case If there exists a continuously differentiable function \theta(x,y) such that F(x,y)=\nabla_{y}\theta(x,y), then the lower-level VI is the first-order optimality condition for \min_{y}\;\theta(x,y)\quad\text{s.t. }y\in C(x). If \theta(x,\cdot) is convex and an appropriate constraint qualification holds, the VI solution set coincides with the optimizer set of the lower-level problem. Remark 3.1 (Optimistic versus pessimistic bilevel modeling) . If the lower-level problem has multiple optimizers, the condition y\in S(x) does not by itself specify how the lower-level solution is selected. The formulation above is the standard optimistic or strong version when the upper level is allowed to choose the most favorable y\in S(x) . A pessimistic or weak version instead evaluates the upper-level objective against the least favorable lower-level optimizer. 3.4 Complementarity systems as a special case If C(x) is a convex cone, then the VI is equivalent to a generalized complementarity problem: y\in C(x),\qquad F(x,y)\in C(x)^{*},\qquad y^{T}F(x,y)=0, where the positive dual cone is C(x)^{*}=\{z:z^{T}v\geq 0\ \forall v\in C(x)\}. This sign convention matches the VI convention (v-y)^{T}F(x,y)\geq 0 . Under a polar-cone convention, the same statement is written with the corresponding sign change. When C(x)=\mathbb{R}^{m_{1}}\times\mathbb{R}_{+}^{m_{2}} , one obtains mixed complementarity systems. When m_{1}=0 , one obtains standard nonlinear complementarity problems. a b a\geq 0,\ b=0 a=0,\ b\geq 0 Complementarity set 0\leq a\perp b\geq 0 3.5 Why MPECs are difficult The main difficulties are structural rather than cosmetic. [label=()] 1. Nonconvexity. Even if each lower-level problem is convex, the graph of the solution map S can be highly nonconvex, so \mathcal{F} is typically nonconvex. 2. Possible failure of closedness. Although Z may be closed, \operatorname{Gr}(S) may fail to be closed unless the lower-level solution map has suitable closed-graph properties. 3. Nonsmoothness. Even when S(x) is single-valued, it may fail to be differentiable in x . 4. Multivaluedness. The lower-level solution map may be set-valued, which creates ambiguity in the upper-level model and motivates optimistic and pessimistic Stackelberg interpretations. 5. Combinatorial structure. Complementarity constraints encode disjunctions. For example, 0\leq a\perp b\geq 0 means either a=0 or b=0 or both. This creates a latent finite-union structure similar to disjunctive programming. 3.6 Teaching summary Concept Meaning Upper level Global optimization over (x,y) Lower level Equilibrium or optimization problem in y parameterized by x Reaction map S(x) Set of equilibrium responses to x Feasible set \mathcal{F} Jointly feasible pairs that also satisfy lower-level equilibrium Main difficulty Nonconvexity, nonsmoothness, possible lack of closedness, and finite-union/combinatorial structure 4 Representative Problems This section motivates MPEC through representative applications. The common modeling template is \text{design, policy, or strategy choice}\quad+\quad\text{equilibrium response}. 4.1 Bracken–McGill bilevel programs These are early bilevel models from defense, production, and marketing. A firm or agency chooses upper-level decisions while accounting for adversarial or competitive lower-level choices. The lower-level variables represent the competitors’ or opponents’ optimizing reactions. 4.2 Stackelberg games A leader chooses x , anticipating that followers choose an equilibrium response y\in S(x) . The leader solves \min_{x,y}f(x,y)\quad\text{s.t. }x\in X,\ y\in S(x). If S(x) is multi-valued, two versions arise: [label=()] 1. Strong/optimistic Stackelberg: the leader assumes followers choose the response most favorable to the leader. 2. Weak/pessimistic Stackelberg: the leader assumes followers choose the response least favorable to the leader. Leader chooses x Followers solve equilibrium problem Response set S(x) Selection rule optimistic or pessimistic Leader objective f(x,y) 4.3 Misclassification minimization A minimum-misclassification hyperplane problem can be reformulated as a bilevel linear program by introducing lower-level variables that encode misclassification indicators through optimization. 4.4 Robotics and contact mechanics In robotic motion with frictional contact, the dynamic constraints together with Coulomb friction and complementarity conditions lead to a complementarity system. If the original physical equations are infeasible or inconsistent, one may minimize a residual subject to the remaining equilibrium constraints. This produces an MPEC formulation. 4.5 Residual minimization of complementarity systems Given an NCP, x\geq 0,\qquad F(x)\geq 0,\qquad x^{T}F(x)=0, one may minimize a residual such as \theta(x)=\frac{1}{2}\|\min(x,F(x))\|^{2}. This residual minimization problem can itself be written as an MPEC or as a closely related nonsmooth optimization problem. 4.6 Transportation and network design The upper level selects capacities, tolls, demands, or service frequencies. The lower level is a traffic equilibrium, route-choice equilibrium, or shortest-path problem. Representative examples include continuous network design, origin–destination demand adjustment, and transit planning. 4.7 Facility location and production A large firm chooses plant locations and production quantities while anticipating market-clearing prices produced by a spatial price equilibrium problem. The lower-level equilibrium is often expressible as a complementarity system; the upper level optimizes profit. 4.8 Structural mechanics and optimal design Design variables such as

Read the complete text