A Successive Proximal DC Penalty Method with an Application to Mathematical Programs with Complementarity Constraints

We develop a successive, proximal difference-of-convex (DC) function penalty method for solving DC programs with DC constraints. The proposed approach relies on a DC penalty function that measures the violation of constraints and leads to a penalty reformulation sharing the same solution set as the original problem. The resulting penalty problem is a DC program with convex constraints and is solved using a proximal DC algorithm (DCA) with successive DC decomposition. We establish convergence to a stationary point of the original problem under milder constraint qualifications than those typically required in the DC programming literature. We then specialize the framework to mathematical programs with complementarity constraints (MPCCs), which cover a large class of optimization and equilibrium problems arising in engineering, economics, and game theory. For this application, we introduce a novel DC penalty function that penalizes violations of the complementarity constraints and establish a correspondence between S-stationary points of the MPCC and stationary points of the resulting DC penalty reformulation. Numerical experiments on MPCCs arising from bilevel optimization show that the proposed successive, proximal DCA, referred to as SPDCA, reliably computes feasible solutions and achieves good solution quality, while often requiring significantly less runtime than conventional mixed-integer formulations, particularly on instances with quadratic upper-level DC objectives.

Article

Download

View PDF