A globally convergent method for computing B-stationary points of mathematical programs with equilibrium constraints

Source abstract

Abstract This paper introduces a computationally efficient method that converges globally to B-stationary points of mathematical programs with equilibrium constraints (MPECs). B-stationarity is necessary for optimality and means that no feasible first-order direction can improve the objective. It can be certified by solving a linear program with equilibrium constraints (LPEC) constructed at a given feasible point. The proposed method solves a finite sequence of LPECs, which either certify B-stationarity or provide an active-set estimate for the complementarity constraints, along with branch nonlinear programs (BNLPs) obtained by fixing the complementarity active set in the MPEC. In particular, the method proceeds in two phases: the first identifies a feasible BNLP or a stationary point of a constraint infeasibility minimization problem, and the second solves a sequence of BNLPs until a B-stationary point of the MPEC is found. We prove that under the MPEC-MFCQ, the method requires solving only a finite number of BNLPs and LPECs for convergence. Moreover, we show that, unless the current iterate is B-stationary, the combinatorial LPECs need not be solved to optimality. For convergence, it suffices to compute a nonzero feasible point, which in practice often requires solving a single linear program, yielding significant computational savings. Numerical experiments show that the proposed method is more robust and faster than relaxation-based methods and mixed-integer NLP reformulations (which, in contrast to the proposed approach, do not provide a certificate of B-stationarity), even on medium- to large-scale instances.