Linear complementarity problem

In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.

Given a real matrix M and vector q, the linear complementarity problem LCP(M, q) seeks vectors z and w which satisfy the following constraints:

A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite. If M is such that LCP(M, q) have a solution for every q, then M is a Q-matrix. If M is such that LCP(M, q) have a unique solution for every q, then M is a P-matrix. Both of these characterizations are sufficient and necessary.

The vector w is a slack variable, and so is generally discarded after z is found. As such, the problem can also be formulated as:

Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function

subject to the constraints

These constraints ensure that f is always non-negative. The minimum of f is 0 at z if and only if z solves the linear complementarity problem.

If M is positive definite, any algorithm for solving (strictly) convex QPs can solve the LCP. Specially designed basis-exchange pivoting algorithms, such as Lemke's algorithm and a variant of the simplex algorithm of Dantzig have been used for decades. Besides having polynomial time complexity, interior-point methods are also effective in practice.

Also, a quadratic-programming problem stated as minimize ${\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}$ subject to ${\displaystyle Ax\geqslant b}$ as well as ${\displaystyle x\geqslant 0}$ with Q symmetric

...
Wikipedia