The New Butterfly Relaxation Method for Mathematical Programs with Complementarity Constraints

Overview & Synopsis

We propose a new family of relaxation schemes for mathematical program with complementarity constraints that extends the relaxations of Kadrani, Dussault, Bechakroun from 2009 and the one of Kanzow & Schwartz from 2011. We discuss the properties of the sequence of relaxed non-linear program as well as stationarity properties of limiting points. A sub-family of our relaxation schemes has the desired property of converging to an M-stationary point. We introduce a new constraint qualication to prove convergence of our method, which is the weakest known constraint qualication that ensures bounded-ness of the sequence generated by the method. A comprehensive numerical comparison between existing relaxations methods is performed on the library of test problems MacMPEC and shows promising results for our new method.