The exactness of the ℓ1 penalty function for a class of mathematical programs with generalized complementarity constraints

Abstract

In a mathematical program with generalized complementarity constraints (MPGCC), complementarity relation is imposed between each pair of variable blocks. MPGCC includes the traditional mathematical program with complementarity constraints (MPCC) as a special case. On account of the disjunctive feasible region, MPCC and MPGCC are generally difficult to handle. The ℓ1 penalty method, often adopted in computation, opens a way of circumventing the difficulty. Yet it remains unclear about the exactness of the ℓ1 penalty function, namely, whether there exists a sufficiently large penalty parameter so that the penalty problem shares the optimal solution set with the original one. In this paper, we consider a class of MPGCCs that are of multi-affine objective functions. This problem class finds applications in various fields, e.g., the multi-marginal optimal transport problems in many-body quantum physics and the pricing problems in network transportation. We first provide an instance from this class, the exactness of whose ℓ1 penalty function cannot be derived by existing tools. We then establish the exactness results under rather mild conditions. Our results cover those existing ones for MPCC and apply to multi-block contexts.

Keywords

• 65K05
• 90C26
• 90C30
• 90C33