First-Order Optimality Conditions for Mathematical Programming with Equilibrium Constraints
Louis Shuo Wang · 2026
Read First-Order Optimality Conditions for Mathematical Programming with Equilibrium Constraints 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-00388.txt.
Introduction
Louis Shuo Wang systematically introduces first-order optimality conditions for mathematical programs with equilibrium constraints, the conditions a candidate solution must satisfy at a local best point. Standard nonlinear programming tools fit these problems poorly. Rewriting them through their optimality systems, or through smooth exact penalties, usually demands strong assumptions such as nondegeneracy and smoothness that real problems rarely grant.
Wang instead builds the theory from first principles, starting with the geometry of the feasible region. He studies several notions of stationarity, the generalized versions of 'no improving direction' suited to kinked feasible sets. A detailed description of the tangent cone at feasible points follows, leading to constraint qualifications tailored to this problem class. The results clarify how the original formulation and its optimality-system rewrite relate, and they ground later work on solving such problems.
Catalog record
| CREATOR | Louis Shuo Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00388
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
First-Order Optimality Conditions for Mathematical Programming with Equilibrium Constraints Louis Shuo Wang Abstract We present a systematic introduction to first-order optimality conditions for mathematical programs with equilibrium constraints (MPECs), emphasizing the limitations of classical nonlinear programming techniques. The goal is twofold. First, we explain why a direct application of standard optimality conditions—based on reformulating MPECs via KKT systems or differentiable exact penalty functions—is often inadequate, as such approaches typically require strong and restrictive assumptions, including nondegeneracy and smoothness conditions. Second, we develop a first-principles framework for analyzing MPECs by focusing on the geometric structure of the feasible region. In particular, we study stationarity concepts and provide a detailed characterization of the tangent cone at feasible points, which leads to appropriate constraint qualifications tailored to MPECs. These results form the foundation for rigorous first-order analysis and clarify the relationship between the original MPEC formulation and its KKT-based representation, offering practical guidance for handling these inherently challenging optimization problems. 1 Introduction A mathematical program with equilibrium constraints (MPEC) is an optimization problem where the upper-level variables are constrained by the solution set of a lower-level variational inequality or complementarity problem. Such models arise in engineering design, network equilibrium, contact mechanics, economics, and hierarchical control. A central message of these notes is that a naive KKT reformulation of the lower-level equilibrium system can obscure the true local geometry of the MPEC feasible set. In particular, the tangent cone is generally nonconvex, so the standard nonlinear programming linearization is not the right first-order object. 2 Background Prerequisites for Chapter 3 This section collects the minimum optimization background needed to read Chapter 3 on first-order optimality conditions for MPECs. The goal is not to develop full general theory, but to explain the objects that appear in the chapter and why they matter. 2.1 Vectors, gradients, Jacobians, and Hessians Let x\in\mathbb{R}^{n} be a vector of variables and let \phi:\mathbb{R}^{n}\to\mathbb{R} be differentiable. Definition 2.1 (Gradient) . The gradient of \phi at x is \nabla\phi(x)=\begin{bmatrix}\frac{\partial\phi}{\partial x_{1}}(x)\\ \vdots\\ \frac{\partial\phi}{\partial x_{n}}(x)\end{bmatrix}. It gives the first-order change of \phi : \phi(x+d)\approx\phi(x)+\nabla\phi(x)^{T}d. Definition 2.2 (Jacobian) . If g:\mathbb{R}^{n}\to\mathbb{R}^{m} is differentiable, its Jacobian is the matrix \nabla g(x)=\begin{bmatrix}\nabla g_{1}(x)^{T}\\ \vdots\\ \nabla g_{m}(x)^{T}\end{bmatrix}. Each row is the gradient of one component function. Definition 2.3 (Hessian) . If \phi is twice differentiable, its Hessian is \nabla^{2}\phi(x)=\left[\frac{\partial^{2}\phi}{\partial x_{i}\partial x_{j}}(x)\right]_{i,j=1}^{n}. It captures second-order curvature. Remark 2.4 . In optimization, first-order theory is based mainly on gradients and Jacobians. Hessians enter second-order theory. 2.2 Local minimizers and feasible directions Consider the constrained optimization problem \min_{x}\ \phi(x)\qquad\text{subject to }x\in\Omega, where \Omega\subseteq\mathbb{R}^{n} is the feasible set. Definition 2.5 (Local minimizer) . A point \bar{x}\in\Omega is a local minimizer if there exists \varepsilon>0 such that \phi(\bar{x})\leq\phi(x)\qquad\forall x\in\Omega\cap B_{\varepsilon}(\bar{x}). Definition 2.6 (Feasible direction) . A vector d\in\mathbb{R}^{n} is a feasible direction at \bar{x}\in\Omega if one can move from \bar{x} a little in direction d while staying feasible, at least to first order. The mathematical object that collects all such first-order feasible directions is the tangent cone. 2.3 Tangent cone and linearized cone Definition 2.7 (Tangent cone) . Let \Omega\subseteq\mathbb{R}^{n} and \bar{x}\in\Omega . The tangent cone to \Omega at \bar{x} is T(\bar{x};\Omega):=\left\{d:\exists\,x^{k}\in\Omega,\ x^{k}\to\bar{x},\ \exists\,t_{k}\downarrow 0\text{ such that }\frac{x^{k}-\bar{x}}{t_{k}}\to d\right\}. Remark 2.8 . The tangent cone contains all first-order directions in which feasibility can be approached. It is the correct geometric object for first-order necessary conditions. If \bar{x} is a local minimizer, then no tangent direction can be a descent direction for the objective. Theorem 2.9 (Primal first-order necessary condition) . If \bar{x} is a local minimizer of \min_{x\in\Omega}\phi(x), and \phi is differentiable, then \nabla\phi(\bar{x})^{T}d\geq 0\qquad\forall d\in T(\bar{x};\Omega). In practice, T(\bar{x};\Omega) may be hard to compute exactly. For a smooth nonlinear program \min_{x}\ \phi(x)\quad\text{s.t.}\quad g_{i}(x)\leq 0,\ i=1,\dots,m,\qquad h_{j}(x)=0,\ j=1,\dots,p, one often uses the linearized cone . Definition 2.10 (Linearized cone) . Let \bar{x} be feasible and define the active inequality index set I(\bar{x}):=\{i:g_{i}(\bar{x})=0\}. Let \mathcal{F}\subset\Omega be the feasible region for the mathematical program under consideration. The linearized cone is \mathcal{L}(\bar{x};\mathcal{F}):=\left\{d\in\mathcal{T}(\bar{x};\Omega):\nabla g_{i}(\bar{x})^{T}d\leq 0\ \forall i\in I(\bar{x}),\,\,\,\nabla h_{j}(\bar{x})^{T}d=0\ \forall j\right\}. Remark 2.11 . Always, T(\bar{x};\mathcal{F})\subseteq\mathcal{L}(\bar{x};\mathcal{F}). If equality holds, then the abstract tangent-cone condition becomes a computable linear condition. 2.4 Lagrangian and KKT conditions For the nonlinear program above, define the Lagrangian \mathcal{L}(x,\lambda,\mu)=\phi(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{p}\mu_{j}h_{j}(x). Definition 2.12 (KKT conditions) . A feasible point \bar{x} satisfies the KKT conditions if there exist multipliers \bar{\lambda}\in\mathbb{R}^{m} and \bar{\mu}\in\mathbb{R}^{p} such that \displaystyle\nabla_{x}\mathcal{L}(\bar{x},\bar{\lambda},\bar{\mu}) \displaystyle=0\qquad\text{(stationarity)}, \displaystyle g_{i}(\bar{x}) \displaystyle\leq 0,\quad i=1,\dots,m\qquad\text{(primal feasibility)}, \displaystyle h_{j}(\bar{x}) \displaystyle=0,\quad j=1,\dots,p\qquad\text{(primal feasibility)}, \displaystyle\bar{\lambda}_{i} \displaystyle\geq 0,\quad i=1,\dots,m\qquad\text{(dual feasibility)}, \displaystyle\bar{\lambda}_{i}g_{i}(\bar{x}) \displaystyle=0,\quad i=1,\dots,m\qquad\text{(complementary slackness)}. Remark 2.13 . The KKT system is a primal–dual form of first-order optimality. It augments the primal variable x with multiplier variables. 2.5 Constraint qualifications KKT conditions are not automatically valid at every local minimizer. Some regularity assumption is needed. Definition 2.14 (Constraint qualification) . A constraint qualification (CQ) is an assumption ruling out pathological degeneracy of the constraints, so that tangent-cone geometry and multiplier-based conditions behave well. Two standard examples are LICQ and MFCQ. Definition 2.15 (LICQ) . The linear independence constraint qualification holds at a feasible point if the gradients of all active inequalities together with the gradients of all equalities are linearly independent. Definition 2.16 (MFCQ) . The Mangasarian–Fromovitz constraint qualification holds at a feasible point if the equality gradients are linearly independent and there exists a direction that preserves equalities while strictly decreasing all active inequalities. Remark 2.17 . Under standard CQs, the tangent cone of an NLP matches the linearized cone, and KKT conditions hold at local minimizers. 2.6 Variational inequalities MPECs involve a lower-level equilibrium problem. One standard way to model equilibrium is through a variational inequality. Definition 2.18 (Variational inequality) . Let K\subseteq\mathbb{R}^{m} be closed and convex, and let F:\mathbb{R}^{m}\to\mathbb{R}^{m} . The variational inequality problem \mathrm{VI}(F,K) is to find y\in K such that F(y)^{T}(v-y)\geq 0\qquad\forall v\in K. Remark 2.19 . Interpretation: at the equilibrium point y , moving to any other feasible point v\in K cannot produce a negative first-order directional change in the equilibrium map. Definition 2.20 (Solution set) . The solution set of the VI is denoted \mathrm{SOL}(F,K). Example 2.21 . If K=\mathbb{R}^{m} , then the VI condition becomes F(y)=0. So VIs generalize systems of equations. Definition 2.22 (Affine variational inequality) . If F(y)=My+q with matrix M and vector q , the problem is called an affine variational inequality (AVI). We use the notations \mathrm{AVI}(q,M,K) and \mathrm{SOL}(q,M,K) to represent the affine variation problem and its solution set. Here, K is the same as in Definition 2.18 . 2.7 Complementarity problems A very important special case of a VI is a complementarity system. Definition 2.23 (Nonlinear complementarity problem) . Given F:\mathbb{R}^{m}\to\mathbb{R}^{m} , the nonlinear complementarity problem (NCP) is to find y\in\mathbb{R}^{m} such that y\geq 0,\qquad F(y)\geq 0,\qquad y_{i}F_{i}(y)=0\ \ \forall i. Remark 2.24 . For each index i , complementarity means: \text{either }y_{i}=0\text{ or }F_{i}(y)=0, possibly both. Thus the product condition enforces a switch-like behavior. Definition 2.25 (Linear complementarity problem) . If F(y)=My+q , then the NCP becomes a linear complementarity problem (LCP): y\geq 0,\qquad My+q\geq 0,\qquad y^{T}(My+q)=0. Remark 2.26 . Complementarity systems appear naturally in contact mechanics, equilibrium networks, market clearing, and KKT systems of optimization problems. 2.8 From lower-level equilibrium to MPEC An MPEC combines an upper-level optimization problem with a lower-level equilibrium problem. Definition 2.27 (MPEC: informal form) .