The
linear complementarity problem has been successfully applied to option pricing. The
problem has undergone several name changes, from composite problem, to fundamental
problem, to complementary pivot problem. The current name linear complementarity
problem was proposed by Cottle [15, p. 37]. The linear complementarity problems are
found in the first-order optimality conditions of quadratic programming. Probably the
earliest publication containing an explicitly stated linear complementarity problem is
one by Du Val (1940)[24] in algebraic geometry.
The algorithm presented by Lemke and Howson [72] to compute an equilibrium
pair of strategies to a bimatrix game, later extended by Lemke to solve an LCP(q, M)
contributed significantly to the development of the linear complementarity theory.
However, this algorithm does not solve every instance of the linear complementarity
problem and in some instances of the problem may terminate inconclusively without
either computing a solution to it or showing that no solution to it exists.
In fact there exists two major types of algorithms to solve LCPs: pivoting and
iterative. The former one is of finite step algorithm where it transform the problem
(q, M) into an equivalent form (q, M) in which q >= 0. But this is not always possible
as it depends on the problem data, mostly on the matrix class to which the matrix
M belongs. Iterative method is used in case of a large scale linear complementarity
problem and the matrix is to be sparse(to have lesser number of nonzero elements)
and structured. Lemke's algorithm [71] is a nice pivoting algorithm for solving a
linear complementarity problem and it has attracted lots of attention to game theory
community. Another pivoting algorithm called pincipal pivoting method(PPM) for
LCPs can be found in Cottle and Dantzig
