A General Framework of Continuation Methods for Complementarity Problems
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno · Mathematics of Operations Research · 1993
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 n be nonnegative vectors. We embed the complementarity problem with a continuously differentiable mapping f: R n → R n in an artificial system of equations (*) F(x, y) = (μa, ζb) and (x, y) ≥ 0, where F: R 2 n → R 2 n is defined by F(x, y) = (x 1 y 1 , …, x n y 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 1 , y 1 ) for some μ 1 , ζ 1 ≥ 0. (2) Trace solutions of (*) from (x 1 , y 1 ) with μ = μ 1 and ζ = ζ 1 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.