We propose a class of non-interior point algorithms for solving the complementarity problems (CP): Find a nonnegative pair (x, y) ∈ ℝ2n satisfying y = f(x) and xiyi = 0 for every i ∈ {1, 2, ..., n}, where f is a continuous mapping from ℝn to ℝn. The algorithms are based on the Chen–Harker–Kanzow–Smale smoothing functions for the CP, and the class of algorithms has the following features; (a) it traces a trajectory in ℝ3n which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ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.
