##
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

Contact: yoshise@shako.sk.tsukuba.ac.jp