Mathematical Programs with Equilibrium Constraints: A sequential optimality condition, new constraint qualifications and algorithmic consequences.

Mathematical programs with equilibrium (or complementarity) constraints, MPECs for short, are a difficult class of constrained optimization problems. The feasible set has a very special structure and violates most of the standard constraint qualifications (CQs). Thus, the Karush-Kuhn-Tucker (KKT) conditions are not necessarily satisfied by minimizers and the convergence assumptions of many methods for solving constrained optimization problems are not fulfilled. Therefore it is necessary, both from a theoretical and numerical point of view, to consider suitable optimality conditions, tailored CQs and specially designed algorithms for solving MPECs. In this paper, we present a new sequential optimality condition useful for the convergence analysis for several methods of solving MPECs, such as relaxations schemes, complementarity-penalty methods and interior-relaxation methods. We also introduce a variant of the augmented Lagrangian method for solving MPEC whose stopping criterion is based on this sequential condition and it has strong convergence properties. Furthermore, a new CQ for M-stationary which is weaker than the recently introduced MPEC relaxed constant positive linear dependence (MPEC-RCPLD) associated to such sequential condition is presented. Relations between the old and new CQs as well as the algorithmic consequences will be discussed.

Article

Download

View PDF