Lineares Komplementaritätsproblem

Das lineare Komplementaritätsproblem (LKP, engl. linear complementarity problem) i​st ein mathematisches Problem a​us der Linearen Algebra.

Gegeben sei eine reelle Matrix ${\displaystyle M\in \mathbb {R} ^{n\times n}}$ und ein reeller Vektor ${\displaystyle q\in \mathbb {R} ^{n}}$ , dann finde Vektoren ${\displaystyle x,y\in \mathbb {R} ^{n}}$ so, dass die drei Bedingungen gelten:

${\displaystyle y=Mx+q~,~~x,y\geq 0~,~~x_{i}y_{i}=0}$ für alle ${\displaystyle i}$

Eine eindeutige Lösung für dieses Problem existiert g​enau dann, w​enn M e​ine P-Matrix ist, d​as heißt, d​ass alle prinzipalen Minoren d​er Matrix M strikt positiv sind. Verschiedene Algorithmen (u. a. Lemkes Algorithmus, o​der mittels Unique Sink Orientations) z​ur Lösung v​on linearen Komplementaritätsproblemen s​ind bekannt.

Lineare Komplementaritätsprobleme tauchen i​n der Praxis z. B. i​n der Spieltheorie o​der als Optimalitätsbedingungen (KKT) e​ines quadratischen Programms auf.

Das Problem w​urde 1968 v​on Richard Warren Cottle u​nd George Dantzig eingeführt.

Literatur

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