Limiting Behavior of Trajectories Generated by a Continuation Method for Monotone Complementarity Problems
Abstract
Defining the mapping F from the 2n-dimensional Euclidean space R2n into itself by
F(x, y) = (x1y1, …, xn yn, y1 − f1(x), …, yn − fn(x))
for every (x, y) ∈ R2n, we write the CP, the complementarity problem, with a mapping f: Rn → Rn as the system of equations
F(x, y) = 0 and (x, y) ∈ R+2n,
where R+2n denotes the nonnegative orthant of R2n. Under the assumption that f is a monotone function on R+n, we show that F maps the positive orthant R++2n of R2n homeomorphically. This result then ensures the existence of a trajectory consisting of the solutions (x, y, t) of the system of equations
F(x, y) = w(t) and (x, y, t) ∈ R++2n × (0, 1],
where w is a continuous mapping from the unit interval [0, 1] into F(R++2n) such that w(0) = 0; if t = 0, the system coincides with the CP. We study limiting behavior of the trajectory as t → 0, and give some sufficient conditions for the trajectory to lead to a solution of the CP. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving positive semidefinite linear complementarity problems.
