A Gap Penalty Reformulation for Mathematical Programming with Complementarity Constraints: Convergence Analysis

Kangyu Lin, Toshiyuki Ohtsuka · 2025

Read A Gap Penalty Reformulation for Mathematical Programming with Complementarity Constraints: Convergence Analysis by Kangyu Lin, Toshiyuki Ohtsuka (2025) 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-2503-05181.txt.

Introduction

Some optimization problems carry a strict either or rule: two quantities may not both be positive at once. Kangyu Lin and Toshiyuki Ohtsuka study in 2025 a penalty method they proposed earlier for such problems. The method rewrites them as a chain of smoother problems, with a growing fine for breaking the rule. Here they ask whether the chain truly lands on a valid answer.

Under three stated conditions, they prove it does: the method settles at a strongly stationary point, the kind that marks a true local best. The proof leans on independence of the active constraints and on second order checks. The authors say the guarantee firms up the method's standing. It tells users when the answers can be trusted.

Catalog record

CREATORKangyu Lin, Toshiyuki Ohtsuka
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05181

Browse the full library · About the Tower of Babel

Full text

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

A Gap Penalty Reformulation for Mathematical Programming with Complementarity Constraints: Convergence Analysis Kangyu Lin, Toshiyuki Ohtsuka Abstract Our recent study (Lin and Ohtsuka, 2024) proposed a new penalty method for solving mathematical programming with complementarity constraints (MPCC). This method first reformulates MPCC as a parameterized nonlinear programming called gap penalty reformulation and then solves a sequence of gap penalty reformulations with an increasing penalty parameter. This study examines the convergence behavior of the new penalty method. We prove that it converges to a strongly stationary point of MPCC, provided that: (i) The MPCC linear independence constraint qualification holds. (ii) The upper-level strict complementarity condition holds. (iii) The gap penalty reformulation satisfies the second-order necessary conditions in terms of the second-order directional derivative. Because strong stationarity is used to identify the MPCC local minimum, our analysis indicates that the new penalty method can find an MPCC solution. I Introduction I-A Background This study considers a special yet common class of nonlinear programming (NLP), known as mathematical programming with complementarity constraints (MPCC). Many switching and nonsmooth decisions can be represented through complementarity constraints. Therefore, MPCC can model the discretized optimal control problems of various nonsmooth dynamical systems arising in practical applications, such as process systems with discrete events, mechanical systems with contacts, and game-theoretical dynamical systems [ 1 ] . However, complementarity constraints pose significant challenges in solving the MPCC, as almost all constraint qualifications (CQs) are violated at any MPCC feasible point. This causes two difficulties. First, MPCC solutions cannot be characterized by the optimality conditions for standard NLP problems; Second, MPCC cannot be solved using standard NLP solution methods. To characterize the MPCC solution, many MPCC-tailored concepts have been proposed [ 2 ] , some of which are reviewed in Section II-A . To solve the MPCC, many MPCC-tailored solution methods, such as relaxation methods and penalty methods , have been proposed [ 1 ] . These methods do not solve the MPCC directly. Instead, they reformulate complementarity constraints as parameterized costs or constraints, solve a sequence of well-defined parameterized NLP, and then present a rigorous convergence analysis showing that the sequence of solutions to the parameterized NLP can finally converge to an MPCC solution. These MPCC-tailored solution methods are practical because they are easy to implement using state-of-the-art NLP software. Our recent study [ 3 ] proposed a new penalty method called gap penalty method , which reformulates the MPCC as a parameterized NLP called gap penalty reformulation and solves a sequence of gap penalty reformulations with an increasing penalty parameter. Compared to other penalty methods, gap penalty reformulation exhibits certain convexity structures that can be exploited by a dedicated Hessian regularization method. The gap penalty method is practically effective, especially in optimal control of linear complementarity systems [ 3 ] , but its theoretical convergence has not been analyzed. I-B Contribution This study builds on our previous work [ 3 ] by providing a rigorous convergence analysis for the gap penalty method. This study’s main contributions are: First, because the gap penalty reformulation involves a Lipschitz continuously differentiable function, we characterize its solutions using second-order directional derivatives rather than the Hessian matrix as in standard NLP theory. These results are critical for the subsequent convergence analysis. Second, we prove that the gap penalty method converges to a strongly stationary point of MPCC under certain standard MPCC-tailored assumptions. This theoretically confirms that the gap penalty method can find an MPCC solution. I-C Outline and notation The remainder of this study is organized as follows: Section II reviews MPCC-tailored concepts and gap penalty reformulation; Section III presents the optimality conditions of gap penalty reformulation; Section IV presents a detailed convergence analysis; and Section V concludes this study. Given a vector x\in\mathbb{R}^{n} , we denote its i -th component by x_{i} , its \ell_{1} and \ell_{2} norm by \|x\|_{1} and \|x\| , respectively . We denote the complementarity condition between x,y\in\mathbb{R}^{n} as 0\leq x\perp y\geq 0 , where x\perp y means x^{T}y=0 . We take \max(x,y) with x,y\in\mathbb{R}^{n} in a component-wise manner . Given a function f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , we denote its Jacobian by \nabla_{x}f\in\mathbb{R}^{m\times n} and say that f is k -th Lipschitz continuously differentiable ( LC^{k} ) if its k -th derivative is Lipschitz continuous. II Mathematical programming with complementarity constraints II-A MPCC-tailored concepts Consider the MPCC in the form of: \displaystyle\min_{x,\lambda,\eta}\ \displaystyle J(x,\lambda,\eta), (1a) s.t. \displaystyle h(x,\lambda,\eta)=0, (1b) \displaystyle 0\leq\lambda\perp\eta\geq 0, (1c) where x\in\mathbb{R}^{n_{x}} , \lambda,\eta\in\mathbb{R}^{n_{\lambda}} are decision variables, J:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{\lambda}}\times\mathbb{R}^{n_{\lambda}}\rightarrow\mathbb{R} is the cost function, and h:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{\lambda}}\times\mathbb{R}^{n_{\lambda}}\rightarrow\mathbb{R}^{n_{h}} is the equality constraint. J and h are assumed to be LC^{2} . We define z=[x^{T},\lambda^{T},\eta^{T}]^{T}\in\mathbb{R}^{n_{x}+2n_{\lambda}} to collect decision variables. A point z satisfying ( 1b ) and ( 1c ) is referred to as the feasible point of MPCC ( 1 ). For a feasible point z of MPCC ( 1 ), the activation status of ( 1c ) at z are classified by the following index sets: \displaystyle\mathcal{I}_{\lambda}(z)=\{{i\in\{1,\cdots,n_{\lambda}\}|\lambda_{i}=0,\eta_{i}>0\}}, (2a) \displaystyle\mathcal{I}_{\eta}(z)=\{{i\in\{1,\cdots,n_{\lambda}\}|\lambda_{i}>0,\eta_{i}=0\}}, (2b) \displaystyle\mathcal{I}_{\lambda\eta}(z)=\{{i\in\{1,\cdots,n_{\lambda}\}|\lambda_{i}=0,\eta_{i}=0\}}. (2c) Subsequently, the MPCC-tailored stationarity, constraint qualification, and strict complementarity conditions can be defined based on these index sets [ 2 ] : Definition 1 (MPCC-tailored stationarity) For a feasible point z of MPCC ( 1 ), we say that • it is weakly stationary if there exists Lagrangian multipliers u\in\mathbb{R}^{n_{h}} , v,w\in\mathbb{R}^{n_{\lambda}} for h(z)=0 , \lambda\geq 0 and \eta\geq 0 , respectively, such that: \displaystyle\nabla_{z}J(z)+u^{T}\nabla_{z}h(z)-v^{T}\nabla_{z}\lambda-w^{T}\nabla_{z}\eta=0, (3a) \displaystyle v_{i}\in\mathbb{R},w_{i}=0,\ i\in\mathcal{I}_{\lambda}(z), (3b) \displaystyle v_{i}=0,w_{i}\in\mathbb{R},\ i\in\mathcal{I}_{\eta}(z), (3c) \displaystyle v_{i}\in\mathbb{R},w_{i}\in\mathbb{R},\ i\in\mathcal{I}_{\lambda\eta}(z), (3d) • it is Clarke stationary if it is weakly stationary and v_{i}w_{i}\geq 0,i\in\mathcal{I}_{\lambda\eta}(z) , • it is strongly stationary if it is weakly stationary and v_{i}\geq 0,w_{i}\geq 0,i\in\mathcal{I}_{\lambda\eta}(z) . Definition 2 (MPCC-tailored constraint qualification) For a feasible point z of MPCC ( 1 ), we say that the MPCC linear independence constraint qualification (MPCC-LICQ) holds at z if the vectors \{\nabla_{z}h(z)\}\cup\{\nabla_{z}\lambda_{i}|i\in\mathcal{I}_{\lambda}(z)\cup\mathcal{I}_{\lambda\eta}(z)\}\cup\{\nabla_{z}\eta_{i}|\mathcal{I}_{\eta}(z)\cup\mathcal{I}_{\lambda\eta}(z)\} are linearly independent. Definition 3 (MPCC-tailored strict complementarity condition) A weakly stationary point z is said to satisfy the upper-level strict complementarity (ULSC) condition if there exist multipliers satisfying ( 3 ) and v_{i}w_{i}\neq 0,\forall i\in\mathcal{I}_{\lambda\eta}(z) . With these MPCC-tailored concepts, the solution of MPCC ( 1 ) can be characterized by the following first-order necessary optimality condition for MPCC . Proposition 1 (Theorem 11.1 in [ 1 ] ) Let \bar{z} be a local minimum of MPCC ( 1 ) and suppose that the MPCC-LICQ holds at \bar{z} , then \bar{z} is a strongly stationary point of MPCC ( 1 ). II-B Gap penalty reformulation for MPCC The treatment of complementarity constraints plays a critical role in MPCC-tailored solution methods. Our recent study [ 3 ] uses the D-gap function [ 4 ] to construct a novel penalty term for the complementarity constraints ( 1c ). Definition 4 (D-gap function) Let \lambda,\eta\in\mathbb{R}^{n_{\lambda}} be two variables, a,b be two given constants satisfying b>a>0 , and \varphi^{ab}:\mathbb{R}^{n_{\lambda}}\times\mathbb{R}^{n_{\lambda}}\rightarrow\mathbb{R} be a function given by \varphi^{ab}(\lambda,\eta)=\varphi^{a}(\lambda,\eta)-\varphi^{b}(\lambda,\eta), (4) where \varphi^{a},\varphi^{b}:\mathbb{R}^{n_{\lambda}}\times\mathbb{R}^{n_{\lambda}}\rightarrow\mathbb{R} are the functions defined by \varphi^{c}(\lambda,\eta)=\frac{1}{2c}(\|\eta\|^{2}_{2}-\|\max(0,\eta-c\lambda)\|^{2}_{2}), (5) with parameter c>0 . We call \varphi^{ab} the D-gap function, where D stands for Difference. Some properties of \varphi^{ab} are summarized below; see Theorem 10.3.3 and Proposition 10.3.13 in [ 5 ] for a detailed proof. Proposition 2 The following statements are valid for \varphi^{ab} . • (Differentiability) \varphi^{ab}(\lambda,\eta) is LC^{1} with the gradients \displaystyle\begin{split}\nabla_{\lambda}\varphi^{ab}=&[\max(0,\eta-a\lambda)-\max(0,\eta-b\lambda)]^{T}\end{split} (6a) \displaystyle\begin{split}\nabla_{\eta}\varphi^{ab}=&[(\frac{1}{a}-\frac{1}{b})\eta-\frac{1}{a}\max(0,\eta-a\lambda)\\

Read the complete text