MPECs

MPECs stands for Mathematical Programs with Equilibrium Constraints. They are optimization problems in which the feasible set is defined by equilibrium conditions that themselves depend on decision variables. They commonly arise in bilevel optimization and in the modeling of strategic interactions in game theory, supply chains, engineering design, and energy systems. They are a challenging class due to nonconvexities and the entanglement of outer and inner problem constraints.

A typical formulation is to minimize a function f(x, y) subject to g(x, y) ≤ 0 and h(x, y) = 0, with y constrained by a lower-level optimization problem or by equilibrium conditions. In the standard bilevel form, the outer decision x is chosen with the knowledge that y is the optimal response to x. A common practical approach is to replace the lower-level problem by its Karush-Kuhn-Tucker conditions, yielding a mathematical program with complementarity constraints (MPCC). For a lower-level problem min φ(y) subject to Ay = b, y ≥ 0, the KKT conditions yield: ∇_y φ(y) + A^T λ = 0, Ay = b, y ≥ 0, λ ≥ 0, and λ^T y = 0. These complementarity relations model equilibrium.

This reformulation makes the problem nonconvex and often nonsmooth, and standard constraint qualifications may fail, complicating analysis and algorithm design. Regularity conditions are weaker, and multiple local optima or stationary points can exist. Special solution concepts such as MPEC-stationarity or strong stationarity are used.

Solution methods include relaxation and penalty schemes that smooth or relax complementarity, regularization, reformulation as MPCCs with specialized algorithms (trust-region, active-set, interior-point variants), and decomposition methods exploiting the bilevel structure. Global algorithms are used when global optimality is needed but are computationally demanding.

Applications include Stackelberg games in economics, electricity markets, traffic and network design, mechanical engineering, and strategic procurement.