Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2001-003 (February 05, 2001)

On the identification of degenerate indices in the nonlinear complementarity problem with the proximal point algorithm
by Nobuo Yamashita, Hiroshige Dan and Masao Fukushima

PostScript File

In this paper we focus on the problem of identifying the index sets $P(x):=\{i\;|x_i>0\}$, $N(x):=\{i\;|F_i(x)>0\}$ and $C(x):=\{i\;|x_i=F_i(x)=0\}$ for a solution $x$ of the monotone nonlinear complementarity problem NCP($F$). The correct identification of these sets is important from both theoretical and practical points of view. Such an identification enables us to remove complementarity conditions from the NCP and locally reduce the NCP to a system which can be dealt with more easily. We present a new technique that utilizes a sequence generated by the proximal point algorithm (PPA). Using the superlinear convergence property of PPA, we show that the proposed technique can identify the correct index sets without assuming the nondegeneracy and the local uniqueness of the solution.