Introduction to Exact Penalization for Mathematical Programming with Equilibrium Constraints

Louis Shuo Wang · 2026

Read Introduction to Exact Penalization 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-00387.txt.

Introduction

Louis Shuo Wang gives a focused primer on exact penalization for hard search problems, including programs with balance constraints. Penalization folds constraints into the goal as a cost, and an exact penalty reproduces the problem's solutions exactly once the price is high enough. The classic theory leans on smoothness conditions, which Wang recasts as error bounds on how feasible sets respond to small shifts.

Newer results, built on subanalytic geometry and Łojasiewicz-type bounds, push the method beyond those old assumptions. Wang then applies the theory to such problems by rewriting them through their first-order systems and building penalties from leftover terms. Fractional-order penalties, which arise from the new error bounds, get close attention. The paper aims to give both insight into why the method works and help in using it.

Catalog record

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

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

Browse the full library · About the Tower of Babel

Full text

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

Introduction to Exact Penalization for Mathematical Programming with Equilibrium Constraints Louis Shuo Wang Abstract We present a focused introduction to exact penalty methods for nonlinear programs and mathematical programs with equilibrium constraints (MPECs), emphasizing their connection to modern error bound theory. The goal is twofold. First, we explain how classical optimality conditions can be interpreted through exact penalization, and why such results typically rely on constraint regularity conditions that can be understood as error bounds on perturbations of feasible sets. We then highlight how recent developments based on subanalytic geometry and Łojasiewicz-type inequalities extend this framework beyond classical regularity assumptions, enabling exact penalization under broader analytic conditions. Second, we demonstrate how this theory can be applied in practice to MPECs by reformulating them via KKT systems and constructing exact penalty functions based on residual mappings. Particular attention is given to fractional-order penalties arising from Łojasiewicz error bounds, as well as to improved formulations for special problem classes where sharper exponents can be obtained. These developments provide both theoretical insight and practical guidance for analyzing and solving challenging constrained optimization problems. 1 Introduction and motivation A mathematical program with equilibrium constraints (MPEC) is an optimization problem in which feasibility is partly defined by the solution set of a lower-level equilibrium system, often a variational inequality (VI), complementarity system, or generalized equation. MPECs are difficult for at least two structural reasons: [label=0.] 1. the feasible set is defined implicitly through an equilibrium problem; 2. natural one-level reformulations introduce complementarity constraints , which destroy standard constraint qualifications and invalidate much of classical nonlinear programming theory. A central idea in exact penalization is to replace hard equilibrium constraints by a residual term added to the objective. If the penalty is exact , then minimizers of the penalized problem coincide with minimizers of the original constrained problem for all sufficiently large penalty parameters. In classical nonlinear programming this is often achieved with an \ell_{1} -type penalty under a regularity condition. For MPECs, however, the correct penalty may involve a fractional power of a residual. This reflects a weaker error bound and is one of the main conceptual messages of the subject. These notes develop the following chain of ideas: \text{exact penalty}\Longleftrightarrow\text{error bound}\Longleftrightarrow\text{metric control of feasibility violation}. The modern viewpoint relevant here is: [label=()] 1. represent the MPEC as a standard constrained problem via KKT conditions for the lower-level equilibrium system; 2. define a residual for those KKT conditions; 3. invoke a Łojasiewicz-type error bound on a subanalytic set; 4. deduce exact penalization, often with exponent \gamma\in(0,1] . 2 The MPEC model We work with a prototypical MPEC of the form \displaystyle\min_{x,y} \displaystyle f(x,y) (1) \displaystyle\text{s.t.} \displaystyle(x,y)\in Z, \displaystyle y\in\mathcal{S}(x), where [label=()] 1. x\in\mathbb{R}^{n} is the upper-level decision variable, 2. y\in\mathbb{R}^{m} is the lower-level or equilibrium variable, 3. Z\subseteq\mathbb{R}^{n}\times\mathbb{R}^{m} is a given constraint set, 4. \mathcal{S}(x) is the solution map of a parametric equilibrium problem. A standard example is a parameterized VI: \text{find }y\in C(x)\ \text{ such that }\ \left\langle F(x,y),v-y\right\rangle\geq 0\quad\forall v\in C(x), (2) where C(x):=\left\{y\in\mathbb{R}^{m}:g_{i}(x,y)\leq 0,\ i=1,\dots,\ell\right\}. If the lower-level problem admits a KKT representation, then ( 2 ) can be expressed using a multiplier vector \lambda\in\mathbb{R}^{\ell}_{+} : F(x,y)+\sum_{i=1}^{\ell}\lambda_{i}\nabla_{y}g_{i}(x,y)=0,\qquad g_{i}(x,y)\leq 0,\qquad\lambda_{i}g_{i}(x,y)=0,\qquad\lambda_{i}\geq 0. (3) This converts ( 1 ) into a one-level constrained problem in variables (x,y,\lambda) . 3 Residual functions and the exact-penalty principle 3.1 Residuals for ordinary constrained optimization Consider the nonlinear program \displaystyle\min_{x} \displaystyle\theta(x) (4) \displaystyle\text{s.t.} \displaystyle x\in X, \displaystyle g(x)\leq 0,\qquad h(x)=0, where X\subseteq\mathbb{R}^{n} , g:\mathbb{R}^{n}\to\mathbb{R}^{p} , h:\mathbb{R}^{n}\to\mathbb{R}^{q} , and \theta:\mathbb{R}^{n}\to\mathbb{R} . A natural residual for the functional constraints is r(x):=\sum_{i=1}^{p}\left(g_{i}(x)\right)_{+}+\sum_{j=1}^{q}\left\lvert h_{j}(x)\right\rvert. (5) Then r(x)\geq 0 and r(x)=0\iff x\text{ is feasible for }\eqref{eq:nlp}. Definition 3.1 (Exact penalty equivalent) . A penalized problem \min_{x\in X}\ \theta(x)+\alpha\psi(x) is called an exact penalty equivalent of ( 4 ) if, for all sufficiently large \alpha , its set of global minimizers coincides with the set of global minimizers of ( 4 ). The crucial issue is not merely that \psi(x)=0 on the feasible set, but that \psi must dominate the distance to feasibility in a suitable quantitative way. 3.2 Metric idea Let W:=\left\{x\in X:g(x)\leq 0,\ h(x)=0\right\}. Suppose \theta is Lipschitz on X with modulus L , and suppose there exists a nonnegative function \psi such that \operatorname{dist}(x,W)\leq c\,\psi(x)\qquad\forall x\in X. Then one expects \theta(x)+\alpha\psi(x) to become exact once \alpha>cL (up to a factor relating global bounds on \psi ). Thus: Exact penalization is driven by error bounds. 4 Subanalyticity and Łojasiewicz-type inequalities The theory in this topic is substantially broader than smooth nonlinear programming. The right ambient class is often the class of subanalytic sets and functions. Definition 4.1 (Analytic function) . A function \varphi:U\to\mathbb{R} on an open set U\subseteq\mathbb{R}^{n} is analytic if it admits a convergent power-series expansion in a neighborhood of each point of U . Definition 4.2 (Semianalytic and subanalytic sets) . A set X\subseteq\mathbb{R}^{n} is semianalytic if locally it can be described by finitely many analytic equalities and inequalities. A set is subanalytic if locally it is the projection of a bounded semianalytic set in a higher-dimensional space. Subanalyticity is large enough to include many piecewise-analytic constructions and many nonsmooth residuals arising from maxima, absolute values, and finite-dimensional equilibrium reformulations. The key analytical tool is a Łojasiewicz-type inequality. Theorem 4.3 (Łojasiewicz-type comparison inequality) . Let S\subseteq\mathbb{R}^{n} be compact and subanalytic, and let \phi,\psi:S\to\mathbb{R} be continuous and subanalytic. If \phi^{-1}(0)\subseteq\psi^{-1}(0), then there exist \rho>0 and an integer N^{\ast}\geq 1 such that \rho\,\left\lvert\psi(x)\right\rvert^{N^{\ast}}\leq\left\lvert\phi(x)\right\rvert\qquad\forall x\in S. A particularly important specialization is obtained by taking \phi(x)=r(x),\qquad\psi(x)=\operatorname{dist}(x,W), which yields an error bound of the form \rho\,\operatorname{dist}(x,W)\leq r(x)^{1/N^{\ast}}. (6) Thus, a fractional-power penalty appears naturally from the geometry of subanalytic feasibility sets. 5 General exact penalty theorem We now state the basic template. Theorem 5.1 (General exact penalty theorem) . Consider ( 4 ). Assume: [label=()] 1. X\subseteq\mathbb{R}^{n} is compact and subanalytic; 2. \theta is Lipschitz continuous on X ; 3. each g_{i} and h_{j} is continuous and subanalytic; 4. the feasible set W is nonempty. Then there exist \alpha^{\ast}>0 and an integer N^{\ast}\geq 1 such that for every \alpha\geq\alpha^{\ast} and every N\geq N^{\ast} , \operatorname*{arg\,min}_{x\in W}\theta(x)=\operatorname*{arg\,min}_{x\in X}\Bigl(\theta(x)+\alpha r(x)^{1/N}\Bigr), where r is the residual ( 5 ). Proof sketch. Let \psi(x):=\operatorname{dist}(x,W). By subanalyticity and compactness, Theorem 4.3 implies that \rho\,\psi(x)\leq r(x)^{1/N^{\ast}}\qquad\forall x\in X for some \rho>0 . If z\in W is a nearest feasible point to x , then Lipschitz continuity gives \theta(x)\geq\theta(z)-L\left\lVert x-z\right\rVert=\theta(z)-L\psi(x). Hence \theta(x)+\alpha r(x)^{1/N^{\ast}}\geq\theta(z)+(\alpha\rho-L)\psi(x). Thus whenever \alpha\rho>L , the penalized objective cannot improve on a feasible comparator unless \psi(x)=0 , i.e., unless x\in W . This proves exactness. ∎ Remark 5.2 . The important point is not the precise exponent 1/N^{\ast} , but the mechanism: \text{error bound}\Longrightarrow\text{exact penalty}. When classical regularity is strong enough, one may obtain N^{\ast}=1 . In degenerate settings, only a weaker fractional exponent may be available. 6 Local exact penalties The same logic localizes. If x^{\ast}\in W is a local minimizer of ( 4 ), then on a sufficiently small neighborhood B(x^{\ast},\varepsilon) the restricted problem is a global minimization problem. Applying the previous theorem locally yields: Corollary 6.1 (Local exact penalty characterization) . Assume X is closed and subanalytic, each g_{i},h_{j} is continuous and subanalytic, and \theta is Lipschitz near a feasible point x^{\ast}\in W . Then x^{\ast} is a

Read the complete text