Does every linear complementarity problem have a solution?

No. Existence depends on the problem data and assumptions.

Why introduce an artificial variable?

It creates an augmented starting point from which the complementary path can begin.

Does t=0 alone prove success numerically?

No. The original equations, nonnegativity, and complementarity should all be checked.

AI Glossary / Mathematics and optimization / Intermediate

Lemke's algorithm

Definition

Lemke's algorithm is a complementary-pivot method for solving a linear complementarity problem. It introduces an artificial variable to obtain a starting point, follows a structured sequence of pivots, and seeks to remove that variable while satisfying complementarity. For a general problem it may instead encounter a secondary ray; successful solution is not guaranteed without additional assumptions.

What it means

A linear complementarity problem asks for vectors z and w satisfying w=Mz+q, z>=0, w>=0, and z_i w_i=0 for every coordinate. Each paired quantity cannot be positive at the same time. This structure arises in mathematical models where an activity and its associated slack or marginal condition must balance.
Complementarity is more restrictive than merely satisfying linear equations and nonnegativity. A vector pair can meet those first two requirements while violating the zero-product conditions. Lemke's method organizes its search around the paired structure rather than treating it as an arbitrary nonlinear equation system.

How it works

If q is nonnegative, z=0 and w=q already solve the problem. Otherwise, choose a positive covering vector d and add an artificial scalar t through w=Mz+q+td. A sufficiently large t makes the starting values nonnegative.
The pivot path maintains an almost-complementary structure. When one variable leaves a basis, its complementary partner determines the next entering variable. A ratio test preserves nonnegativity. Reaching t=0 yields a candidate for the original problem; a secondary ray gives a different termination status. Degenerate cases require appropriate tie-breaking or anti-cycling treatment. Always check the original equations, signs, and complementarity residuals in the returned numerical solution.

Three practical examples

A quadratic-optimization study can formulate suitable optimality conditions as a linear complementarity problem.
An equilibrium-modeling experiment can use complementary conditions to represent activities paired with associated inequalities.
A numerical mechanics prototype can investigate contact formulations with complementarity, while carefully checking the assumptions and any approximations used in converting the physical model.

Think of it this way

Think of following a chain of linked switches: changing one switch determines which paired switch can be considered next, while an extra temporary switch helps start the process. The analogy is limited because the actual moves are algebraic pivots constrained by nonnegativity, not arbitrary on-off decisions.

Worked example

Consider an original two-variable problem with M having rows (2,-1) and (-1,2), and q=(-1,-2). We require w1=2z1-z2-1 and w2=-z1+2z2-2, with nonnegative variables and z1w1=z2w2=0.
Choose covering vector d=(1,1), giving the augmented equations w1=2z1-z2-1+t and w2=-z1+2z2-2+t. Start with z1=z2=0 and t=2. Then w1=1 and w2=0. The artificial variable makes this augmented point feasible, although t is not yet zero.
Since w2 is the zero variable at initialization, let its complement z2 enter. Keep z1=0 and w2=0. The second equation gives t=2-2z2, while the first becomes w1=1-3z2. As z2 increases from zero, w1 reaches zero at z2=1/3, before t would reach zero at z2=1. Therefore w1 leaves at the first limiting event. At this point t=4/3 and w1=w2=0.
Next let z1, the complement of w1, enter. Keep w1=w2=0 and solve the two augmented equations. Subtracting them gives z2=z1+1/3. Substitution gives t=4/3-z1. Increasing z1 reaches t=0 at z1=4/3, with z2=5/3. The artificial variable has left, so the candidate belongs to the original problem.
Verify it directly: w1=2(4/3)-5/3-1=0, and w2=-4/3+2(5/3)-2=0. Both z values are positive, both w values are zero, and both pairwise products vanish. This is a complete exact-arithmetic solution check, independent of the path description.
For an additional interpretation, the same conditions are the optimality conditions for minimizing 0.5 z transpose M z+q transpose z over z>=0. Here M is symmetric positive definite: its eigenvalues are 1 and 3. The resulting quadratic is strictly convex, so the verified solution is its unique minimizer. Its objective value is -7/3. This conclusion uses the specific matrix properties and must not be generalized to every complementarity problem.

Illustrative case study

In a fictional optimization project, Copper Meadow Research implements a small complementarity model as part of a resource-equilibrium study. The team first tests an exact two-variable case, then evaluates larger instances while recording whether the method returns a solution, a ray, or a numerical failure.
When a run terminates without a solution, the analyst preserves that status and checks the model's matrix assumptions. The team does not relabel every ray as proof that the economic model has no equilibrium. This is an illustrative workflow, not evidence about a real deployed system.

Common misconceptions and mistakes

Do not check only the equation w=Mz+q; signs and pairwise zero products are essential. A small total dot product is informative only alongside nonnegativity and suitable numerical tolerances. Otherwise cancellation can hide violations.
Lemke's algorithm is not identical to the Lemke-Howson algorithm for bimatrix games, although both involve complementary pivoting ideas. A secondary ray in a general problem is not automatically a universal infeasibility certificate. Degeneracy, scaling, and implementation tolerances also affect how the computed path behaves.

Business use

Business users usually encounter this method inside specialized optimization or equilibrium software. The useful questions concern model validity, solver termination status, and independently checked residuals. Record the covering vector and relevant options when reproducibility matters. Where a model admits multiple equilibria or solutions, one returned solution does not describe all possibilities or their business significance. A mathematically valid complementarity formulation still needs domain interpretation.

Check your understanding

Why does w1 leave before the artificial variable during the first movement in the example?

Answer: w1=1-3z2 reaches zero at z2=1/3, while t=2-2z2 would reach zero only at z2=1. Nonnegativity therefore limits the movement first at w1=0.

Related terms

Quadratic programming
Linear complementarity problem
Complementary pivot
Covering vector
Artificial variable
Secondary ray
KKT conditions
Degeneracy
Equilibrium

Learn next

Replace q with (1,2) while retaining the same M. Verify the immediate z=0 solution. Then compare checking pairwise products with checking only their sum, and explain why nonnegativity is necessary for the latter interpretation.

Sources

Primary research: Evers, More with the Lemke Complementarity Algorithm, including artificial-variable initialization and termination alternatives: https://ris.utwente.nl/ws/files/6733662/Evers_10.1007_BF01609020.pdf . The two-pivot path and quadratic interpretation are original.

Previous: Leiden Community Detection Next: Lemma