Linear complementarity problem

In mathematics, the linear complementarity problem in linear algebra consists of starting with a known n-dimensional column vector q and a known n×n matrix M, and finding two n-dimensional vectors w and z such that:

1. q = w − Mz
2. w_i ≥ 0 and z_i ≥ 0 for each i
3. w_i×z_i = 0 (i.e. either w_i=0 or z_i=0) for each i

There are several algorithms (e.g. Lemke's algorithm) dealing with specific cases of the linear complementarity problem. A linear complementarity problem has a unique solution if and only if M is a P-matrix.

See also

• Quadratic programming
• Optimization (mathematics)

Further reading

• Cottle, Richard (1992). The linear complementarity problem. Boston, Mass. : Academic Press