= Linear complementarity problem
A \b[linear complementarity problem] asks for real <vectors> $z,w\in\mathbb R^n$ satisfying
$$
\boxed{w=Mz+q,\qquad z\geq0,\quad w\geq0,\quad z^Tw=0,}
$$
for a prescribed real <matrix> $M$ and <vector> $q$. The inequalities hold componentwise. Since every product $z_iw_i$ is nonnegative, the final equality means $z_iw_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.<Underactuated Robotics by Russ Tedrake>[Multi-Body Dynamics, Time-Stepping with hard constraints: definition of the LCP]{ref}
For an original two-variable example, take
$$
M=\begin{pmatrix}2&-1\\-1&2\end{pmatrix},\qquad q=\begin{pmatrix}-1\\1\end{pmatrix}.
$$
The 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\geq0$.
The connection with <quadratic programming> explains one important tractable case. For a <symmetric matrix> $M$, consider
$$
\min_{z\geq0}\;\frac12z^TMz+q^Tz.
$$
The <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 $\|z\|\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,
$$
(z-z')^TM(z-z')=(z-z')^T(w-w')=-z^Tw'-{z'}^Tw\leq0.
$$
Positive definiteness then forces $z=z'$. 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.<Underactuated Robotics by Russ Tedrake>[Multi-Body Dynamics, Time-stepping LCP: Normal force]{ref}
Back to article page
