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 dealing with specific cases of the linear complementarity problem.

See also

• Quadratic programming
• Optimization (mathematics)