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. 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: