A two-sided relaxation scheme for mathematical programs with equilibrium constraints

V. Demiguel, M. P. Friedlander, F. J. Nogales, and S. Scholtes. SIAM J. on Optimization, 16(1):587-609, 2005 PDF

Abstract

We propose a relaxation scheme for mathematical programs with equilibrium constraints (MPECs). In contrast to previous approaches, our relaxation is two-sided: both the complementarity and the nonnegativity constraints are relaxed. The proposed relaxation update rule guarantees (under certain conditions) that the sequence of relaxed subproblems will maintain a strictly feasible interior—even in the limit. We show how the relaxation scheme can be used in combination with a standard interior-point method to achieve superlinear convergence. Numerical results on the MacMPEC test problem set demonstrate the fast local convergence properties of the approach.

BibTeX

 @article{DeMiFrieNogaScho:2005,
  Author = {A.-V. DeMiguel and M. P. Friedlander and
            F. J. Nogales and S. Scholtes},
  Journal = {SIAM J. on Optimization},
  Number = 1,
  Pages = {587-609},
  Title = {A two-sided relaxation scheme for mathematical
           programs with equilibrium constraints},
  Volume = 16,
  Year = 2005,
  doi = {10.1109/TIT.2005.860448}
 }