Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems

Keisuke Hotta and Akiko Yoshise

We propose a class of non-interior-point algorithms for solving the complementarity problems(CP): Find a nonnegative pair $(x,y) \in \LR^{2n}$ satisfying $y=f(x)$ and $x_iy_i = 0$ for every $i \in \{1,2,\ldots,n\}$, where $f$ is a continuous mapping from $\LR^n$ to $\LR^n$. The algorithms are based on the Chen-Harker-Kanzow smooth functions for the CP, and have the following features; (a) it traces a trajectory in $\LR^{3n}$ which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from arbitrary (not necessarily positive) point in $\LR^{2n}$ in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible-interior-point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it.

Discussion Paper Series No. 708, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305, Japan