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

摘要

We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x, y) is an element of R-2n satisfying y = f(x) and x(i)y(i) = 0 for every i is an element of {1, 2,...,n}, where f is a continuous mapping from R-n to R-n. The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in R-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 R-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. [References: 25]