LCPs

Linear complementarity problem (LCP) is a mathematical model in which one seeks vectors z and w in R^n that satisfy a set of complementary inequalities. In the standard form, given an n×n real matrix M and a vector q in R^n, the problem is to find z ≥ 0 and w ≥ 0 such that w = Mz + q and z^T w = 0. The last condition, z_i w_i = 0 for each i, enforces a complementarity relationship where at least one of each pair (z_i, w_i) is zero.

LCPs arise as reformulations of certain optimization problems and equilibrium models. They can be viewed as the Karush-Kuhn-Tucker (KKT) conditions of a convex quadratic program with nonnegativity constraints, making them a unifying framework for various applications. They are used to model equilibrium in economics, contact mechanics, traffic and transportation networks, game theory, and other systems with nonnegative variables and threshold-type interactions.

Existence and solvability of LCPs depend on properties of M and q. If M is a P-matrix (all principal minors of M are positive), then the LCP has a solution for every q. Uniqueness, however, is not guaranteed in general and requires stronger conditions, such as M being positive definite in addition to being a P-matrix. In the general case, a solution may not exist or may not be unique.

Algorithms and software for solving LCPs include pivot-based methods such as Lemke’s algorithm, interior-point techniques, and projection methods. Practical implementations are provided by specialized solvers (e.g., PATH) and by generalized quadratic programming or linear programming solvers that can handle LCP formulations. Variants include parametric LCPs and nonlinear complementarity problems, which extend the framework to broader settings.