ISSN:
1436-4646
Keywords:
Key words: non-interior point method – complementarity problem – smoothing function – homotopy method
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 x i y i =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 have 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s101070050082
