Linear complementarity problem

A linear complementarity problem asks for real vectors $z,w\in {\mathbb{R}}^n$ satisfyingfor a prescribed real matrix $M$ and vector $q$. The inequalities hold componentwise. Since every product $z_i{w}_i$ is nonnegative, the final equality means $z_i{w}_i=0$ for every index: each paired component has at least one zero. The linear complementarity problem is a feasibility problem; it need not come with an objective function. Its affine equation does not make the product condition linear.^[ref]

For an original two-variable example, takeThe pair $z=(1/2,0{)}^T$ and $w=(0,1/2{)}^T$ satisfies all three conditions. Guessing which member of each pair vanishes reduces the remaining equations to a candidate linear system, but each candidate must still satisfy nonnegativity. Choosing $z=0$ here gives $w=q$ and fails that check. Some data admit no solution: in one dimension, $M=-1,q=-1$ gives $w=-z-1<0$ for every $z\ge 0$.

The connection with quadratic programming explains one important tractable case. For a symmetric matrix $M$, considerThe Karush-Kuhn-Tucker conditions set its gradient equal to a nonnegative constraint multiplier $w$ and impose complementary slackness, giving precisely the displayed linear complementarity problem. If $M$ is a positive-definite matrix, the objective function is strictly convex and grows without bound as $\Vert z\Vert \to \infty$, so a unique minimizer exists. This conclusion uses that additional matrix property, not merely the word linear.

There is also a short uniqueness proof. For two complementary pairs,Positive definiteness then forces $z=z^{\prime }$. This argument gives a directly checkable reason for uniqueness in the stipulated case.

In unilateral contact complementarity, a nonnegative separation pairs with a nonnegative normal contact force: an open gap has zero contact reaction, while a positive reaction requires closed contact. A time-discretized rigid body model can relate its next-step gap affinely to the unknown reaction, producing a linear complementarity problem. The particular discretization and impact law determine that affine relation; the algebraic form alone does not select the physical contact model.^[ref]