×

A two-sided relaxation scheme for mathematical programs with equilibrium constraints. (English) Zbl 1122.90060

Summary: 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.

MSC:

90C26 Nonconvex programming, global optimization
49M37 Numerical methods based on nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

MacMPEC; MINOS
PDFBibTeX XMLCite
Full Text: DOI Link