New relaxation method for mathematical programs with complementarity constraints

• Published in: Journal of optimization theory and applications 2003-07, Vol.118 (1), p.81-116
• Main Authors: LIN, G. H, FUKUSHIMA, M
• Format: Article
• Language: English
• Subjects: Applied mathematics; Applied sciences; Eigenvalues; Equilibrium; Exact sciences and technology; Informatics; Mathematical programming; Operational research and scientific management; Operational research. Management science
• ISSN: 0022-3239; 1573-2878
• DOI: 10.1023/A:1024739508603

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian-Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.