Linear complementarity problem

The linear Komplementaritätsproblem ( LKP , Engl. Linear complementarity problem- ) is a mathematical problem from the linear algebra .

Given a real matrix and a real vector , find vectors such that the three conditions hold: ${\displaystyle M\in \mathbb {R} ^{n\times n}}$ ${\displaystyle q\in \mathbb {R} ^{n}}$ ${\displaystyle x,y\in \mathbb {R} ^{n}}$

${\displaystyle y=Mx+q~,~~x,y\geq 0~,~~x_{i}y_{i}=0}$ for all ${\displaystyle i}$

A unique solution to this problem exists if and only if M is a P-matrix, that is, if all principal minors of the matrix M are strictly positive. Various algorithms (including Lemke's algorithm, or using Unique Sink Orientations) for solving linear complementarity problems are known.

Linear complementarity problems arise in practice e.g. B. in game theory or as optimality conditions (KKT) of a quadratic program .

The problem was introduced in 1968 by Richard Warren Cottle and George Dantzig .

literature

• Richard W. Cottle, Jong-Shi Pang , Richard E. Stone: The linear complementarity problem, Academic Press 1992, SIAM 2009