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(q, M) seeks vectors z and w which satisfy the following constraints: (that is, each component of these two vectors is non-negative) or equivalently This is the complementarity condition, since it implies that, for all , at most one of and can be positive. 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(q, M) has a solution for every q, then M is a Q-matrix. If M is such that LCP(q, M) 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: (the complementarity condition) 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 subject to as well as with Q symmetric is the same as solving the LCP with This is because the Karush–Kuhn–Tucker conditions of the QP problem can be written as: with v the Lagrange multipliers on the non-negativity constraints, λ the multipliers on the inequality constraints, and s the slack variables for the inequality constraints.