Optimization Workshop Notes for Mathematical Programming with Equilibrium Constraints (MPECs): Verification of MPEC Hypotheses
Jiguang Yu · 2026
Read Optimization Workshop Notes for Mathematical Programming with Equilibrium Constraints (MPECs): Verification of MPEC Hypotheses by Jiguang Yu (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-2604-20988.txt.
Introduction
Yu presents follow-up notes on mathematical programming with equilibrium constraints, this time on verifying the hypotheses behind first-order optimality conditions. He introduces core vocabulary: nonlinear programming, variational inequalities, and complementarity systems. He pursues two aims: explain the logic of the hypotheses under which first-order conditions become valid, and show how to use that theory in practice. That practice means sorting a model, choosing the right checking route, proving the right hypotheses, and drawing a correct first-order account.
Catalog record
| CREATOR | Jiguang Yu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73321 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.20988
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimization Workshop Notes for Mathematical Programming with Equilibrium Constraints (MPECs): Verification of MPEC Hypotheses Jiguang Yu Abstract In this workshop, we present a compact but rigorous introduction to the basic language of nonlinear programming, variational inequalities, and complementarity systems. The goal is twofold. First, we explain the mathematical logic of hypotheses under which first-order optimality conditions for MPECs become valid. Second, we explain how to use that theory in research practice: how to classify a model, choose the appropriate verification route, prove the right hypotheses, and derive a correct first-order analysis. 1 Problem Setting and Motivation We study the MPEC \displaystyle\min_{x,y} \displaystyle f(x,y) (1) \displaystyle\text{s.t.} \displaystyle x\in X, \displaystyle y\in S(x), where (i) f:\mathbb{R}^{n+m}\to\mathbb{R} is continuously differentiable, (ii) X\subset\mathbb{R}^{n} is a closed convex set, (iii) S(x) is the solution set of a parametric variational inequality \mathrm{VI}(F(x,\cdot),C(x)). That is, S(x):=\left\{y\in C(x)\;:\;(v-y)^{\top}F(x,y)\geq 0\quad\forall v\in C(x)\right\}. Define the feasible set \Gamma:=\{(x,y)\in X\times\mathbb{R}^{m}:y\in S(x)\}. If, near a reference point (\bar{x},\bar{y})\in\Gamma , the lower-level solution is locally unique and can be written as a function y=y(x), then the MPEC ( 1 ) reduces locally to \min_{x\in X}\ \varphi(x):=f(x,y(x)). (2) This is attractive for three reasons: (i) Economic interpretation: the follower’s equilibrium response becomes a locally well-defined reaction map. (ii) Geometric simplification: the tangent cone to \Gamma can be expressed in terms of the derivative of y(\cdot) . (iii) Algorithmic relevance: local descent methods can be designed on the reduced problem ( 12 ), provided one can evaluate or approximate y^{\prime}(x;d) . The cost of this simplification is that one needs strong local stability properties of the lower-level variational inequality. 1.1 The Lower-Level Variational Inequality Assume that, near \bar{x} , the feasible set of the lower-level problem has the form C(x)=\{y\in\mathbb{R}^{m}:g(x,y)\leq 0\}, where g=(g_{1},\dots,g_{\ell}):\mathbb{R}^{n+m}\to\mathbb{R}^{\ell} is C^{2} , and for each fixed x the functions g_{i}(x,\cdot) are convex in y . The lower-level variational inequality at parameter x is: VI (F(x,\cdot),C(x)) : find y\in C(x) such that (v-y)^{\top}F(x,y)\geq 0\qquad\forall v\in C(x). We will focus on a given feasible pair (\bar{x},\bar{y})\in\Gamma satisfying \bar{y}\in S(\bar{x}). Under suitable constraint qualifications, the solution \bar{y} admits Lagrange multipliers \lambda\in\mathbb{R}^{\ell}_{+} satisfying F(\bar{x},\bar{y})+\sum_{i=1}^{\ell}\lambda_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})=0, (3) together with complementarity \lambda_{i}\geq 0,\qquad g_{i}(\bar{x},\bar{y})\leq 0,\qquad\lambda_{i}g_{i}(\bar{x},\bar{y})=0\quad(i=1,\dots,\ell). Let the active set be I(\bar{x}):=\{i:g_{i}(\bar{x},\bar{y})=0\}. The multiplier set is \mathcal{M}(\bar{x}):=\left\{\lambda\in\mathbb{R}^{\ell}_{+}:F(\bar{x},\bar{y})+\sum_{i=1}^{\ell}\lambda_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})=0,\ \lambda_{i}g_{i}(\bar{x},\bar{y})=0\ \forall i\right\}. 1.2 B-Differentiability and the Key Implicit Assumption The reduced problem ( 12 ) is only useful if the reaction map y(\cdot) has enough regularity. Definition 1.1 (Directional and B-differentiability) . Let G:W\subset\mathbb{R}^{p}\to\mathbb{R}^{q} be defined on an open set W and let z\in W . (i) G is directionally differentiable at z if for every d\in\mathbb{R}^{p} , G^{\prime}(z;d):=\lim_{t\downarrow 0}\frac{G(z+td)-G(z)}{t} exists. (ii) G is B-differentiable at z if it is locally Lipschitz near z and directionally differentiable at z . Remark 1.2 . B-differentiability is the natural regularity notion in this context. It is weaker than Fréchet differentiability but strong enough to support tangent-cone calculations and chain rules for directional derivatives. Assumption 1.3 (Basic implicit function property) . At (\bar{x},\bar{y})\in\Gamma , there exist neighborhoods U of \bar{x} and V of \bar{y} , and a Lipschitz continuous function y:U\cap X\to V such that (i) y(\bar{x})=\bar{y} , (ii) y(\cdot) is directionally differentiable at \bar{x} , (iii) for each x\in U\cap X , the point y(x) is the unique solution in V of \mathrm{VI}(F(x,\cdot),C(x)) . We call this assumption BIF . Under BIF, the feasible set \Gamma is locally the graph of the map y(\cdot) . Therefore its tangent cone at (\bar{x},\bar{y}) becomes \mathcal{T}((\bar{x},\bar{y});\Gamma)=\left\{(dx,dy)\in\mathcal{T}(\bar{x};X)\times\mathbb{R}^{m}:dy=y^{\prime}(\bar{x};dx)\right\}. This identity is the central geometric gain of the implicit approach. 1.3 Stationarity of the MPEC Under BIF Suppose BIF holds at (\bar{x},\bar{y}) and let \varphi(x):=f(x,y(x)). Then the chain rule for directional derivatives yields \varphi^{\prime}(\bar{x};dx)=\nabla_{x}f(\bar{x},\bar{y})^{\top}dx+\nabla_{y}f(\bar{x},\bar{y})^{\top}y^{\prime}(\bar{x};dx). Hence (\bar{x},\bar{y}) is stationary for the original MPEC if and only if \nabla_{x}f(\bar{x},\bar{y})^{\top}dx+\nabla_{y}f(\bar{x},\bar{y})^{\top}y^{\prime}(\bar{x};dx)\geq 0\qquad\forall dx\in\mathcal{T}(\bar{x};X). (4) Remark 1.4 . Equation ( 4 ) is the exact analogue of first-order stationarity for the reduced problem ( 12 ). The main unresolved issue is now: \textit{How do we compute }y^{\prime}(\bar{x};dx)\textit{?} The answer is: by linearizing the lower-level VI, provided BIF can be justified. 1.4 How to Verify BIF: The Main Structural Assumptions We now introduce the regularity conditions guaranteeing BIF. Assumption 1.5 (MFCQ at (\bar{x},\bar{y}) ) . There exists v\in\mathbb{R}^{m} such that \nabla_{y}g_{i}(\bar{x},\bar{y})^{\top}v<0\qquad\forall i\in I(\bar{x}). This ensures metric regularity of the active inequality system and nonemptiness/boundedness of lower-level multipliers near the reference point. Assumption 1.6 (Constant rank CQ at (\bar{x},\bar{y}) ) . There exists a neighborhood W of (\bar{x},\bar{y}) such that, for every subset J\subset I(\bar{x}) , the rank of \{\nabla_{y}g_{i}(x,y):i\in J\} is constant for (x,y)\in W . Remark 1.7 . CRCQ is weaker than LICQ and allows nonunique multipliers. It is precisely this flexibility that makes the theory substantially broader than classical strong regularity theory for parametric NLPs under LICQ. We introduce the SCOC family. For every multiplier \lambda\in\mathcal{M}(\bar{x}) , define its support \mathrm{supp}(\lambda):=\{i:\lambda_{i}\neq 0\}. Consider the family \mathcal{B}(\bar{x}) of index sets J\subset I(\bar{x}) such that (i) there exists \lambda\in\mathcal{M}(\bar{x}) with \mathrm{supp}(\lambda)\subset J , (ii) the vectors \{\nabla_{y}g_{i}(\bar{x},\bar{y}):i\in J\} are linearly independent. Write \mathcal{B}(\bar{x})=\{J_{1},\dots,J_{N}\}. For each J_{j}\in\mathcal{B}(\bar{x}) , let \lambda^{j} be the associated extreme multiplier and define L(x,y,\lambda):=F(x,y)+\sum_{i=1}^{\ell}\lambda_{i}\nabla_{y}g_{i}(x,y), together with the matrix A_{j}:=\begin{bmatrix}\nabla_{y}L(\bar{x},\bar{y},\lambda^{j})&\nabla_{y}g_{J_{j}}(\bar{x},\bar{y})^{\top}\\ -\nabla_{y}g_{J_{j}}(\bar{x},\bar{y})&0\end{bmatrix}. (5) Assumption 1.8 (Strong coherent orientation condition) . The matrices A_{1},\dots,A_{N} all have the same nonzero determinantal sign: \mathrm{sgn}(\det A_{1})=\cdots=\mathrm{sgn}(\det A_{N})\in\{-1,+1\}. Remark 1.9 . SCOC is the decisive nondegeneracy condition in the theory. Under LICQ and unique multipliers, it collapses to the nonsingularity of a single KKT matrix. In general, it allows multiple multipliers while enforcing a global consistency of local orientations. 1.5 Piecewise Smooth Analysis and Why It Enters The lower-level VI is handled through its normal map . Let \bar{v}:=\bar{y}-F(\bar{x},\bar{y}). Define the Euclidean projector onto C(x) by \Pi_{C(x)}(v):=\operatorname*{arg\,min}_{y\in C(x)}\frac{1}{2}\|y-v\|^{2}, and define the normal map H(x,v):=F(x,\Pi_{C(x)}(v))+v-\Pi_{C(x)}(v). (6) Then the standard equivalence is: y\text{ solves }\mathrm{VI}(F(x,\cdot),C(x))\quad\Longleftrightarrow\quad v:=y-F(x,y)\text{ solves }H(x,v)=0, with y=\Pi_{C(x)}(v). The projector (x,v)\mapsto\Pi_{C(x)}(v) is generally not C^{1} . However, under MFCQ and CRCQ it is locally piecewise C^{1} . Since F is C^{1} , the normal map H is also PC 1 . This is important because PC 1 functions are locally Lipschitz, directionally differentiable, and amenable to inverse/implicit function theorems based on coherent orientation. 1.6 Main Existence Theorem for the Implicit Solution Map We are now ready for the central theorem. Theorem 1.10 (Existence of a PC 1 implicit solution map) . Assume: (i) g is C^{2} and each g_{i}(x,\cdot) is convex in y , (ii) F is C^{1} , (iii) \bar{y} solves \mathrm{VI}(F(\bar{x},\cdot),C(\bar{x})) , (iv) MFCQ, CRCQ, and SCOC hold at (\bar{x},\bar{y}) . Then there exist neighborhoods U of \bar{x} and V of \bar{y} , and a PC 1 function y:U\to V such that (a) y(\bar{x})=\bar{y} , (b) for every x\in U , the point y(x) is the unique solution in V of \mathrm{VI}(F(x,\cdot),C(x)) . In particular, BIF holds at (\bar{x},\bar{y}) . The proof proceeds through four conceptual steps: (i) Show that (x,v)\mapsto\Pi_{C(x)}(v) is PC 1 near (\bar{x},\bar{v}) . (ii) Deduce that the normal map H in ( 6 ) is PC 1 . (iii) Prove that the partial directional derivative H^{\prime}_{v}(\bar{x},\bar{v};\cdot) is invertible; this is where SCOC enters. (iv) Apply a PC 1 implicit function theorem to obtain a locally unique PC 1 map v=v(x)\quad\text{solving }H(x,v)=0, and then define y(x):=\Pi_{C(x)}(v(x)). 1.7 Computing the Directional Derivative of the Response