Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2002-008 (September 05, 2002)

A Hybrid Algorithm with Active Set Identification for Mathematical Programs with Complementarity Constraints
by Gui-Hua Lin and Masao Fukushima

PostScript File

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. To this end, we first introduce an active set identification technique. Then, by applying this technique to a smoothing continuation method presented by Fukushima and Pang (1999), we propose a hybrid method for solving MPCC. Under reasonable assumptions, the hybrid algorithm is shown to possess a finite termination property. Numerical experience shows that the proposed approach is quite effective.