A new continuation method for complementarity problems with uniformP-functions

Abstract

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ⁿ₊ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) ∈ R ²ⁿ₊ , whereF denotes the mapping from the nonnegative orthantR ²ⁿ₊ ofR ²ⁿ intoR ⁿ₊ × Rⁿ defined byF(x, y) = (x ₁y₁,⋯,x_ny_n, f₁(x) − y₁,⋯, f_n(x) − y_n) for every(x, y) ∈ R ²ⁿ₊ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ²ⁿ₊ ontoR ⁿ₊ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) ∈ R ²ⁿ₊ from an arbitrary initial point(x ⁰, y⁰) ∈ R ²ⁿ₊ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.