A General Framework of Continuation Methods for Complementarity Problems

A general class of continuation methods is presented which, in particular, solve linear complementarity problems with compositive-plus and L_*-matrices. Let a, b ∈ Rⁿ be nonnegative vectors. We embed the complementarity problem with a continuously differentiable mapping f: Rⁿ → Rⁿ in an artificial system of equations

(*)   F(x, y) = (μa, ζb) and (x, y) ≥ 0,

where F: R²ⁿ → R²ⁿ is defined by

F(x, y) = (x₁y₁, …, x_ny_n, y − f(x))

and μ ≥ 0 and ζ ≥ 0 are parameters. A pair (x, y) is a solution of the complementarity problem if and only if it solves (*) for μ = 0 and ζ = 0. A general idea of continuation methods founded on the system (*) is as follows:

(1) Choose n-dimensional vectors a ≥ 0 and b > 0 such that the system (*) has a trivial solution (x¹, y¹) for some μ¹, ζ¹ ≥ 0.

(2) Trace solutions of (*) from (x¹, y¹) with μ = μ¹ and ζ = ζ¹ as the parameters μ and ζ are decreased to zero.

This idea provides a theoretical basis for various methods such as Lemke's method and a method of tracing the central trajectory of linear complementarity problems.