Linear Complementarity Problem

Das lineare Komplementaritätsproblem (LKP, engl. linear complementarity problem) ist ein mathematisches Problem aus der Linearen Algebra.

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

$y=Mx+q~, ~ ~ x,y \geq 0~, ~ ~ x\times y=0$

Eine eindeutige Lösung für dieses Problem existiert genau dann, wenn M eine P-Matrix ist, das heißt, dass alle prinzipalen Minoren der Matrix M strikt positiv sind. Verschiedene Algorithmen (u. a. Lemkes Algorithmus, oder mittels Unique Sink Orientations) zur Lösung von linearen Komplementaritätsproblemen sind bekannt.

Lineare Komplementaritätsprobleme tauchen in der Praxis z. B. in der Spieltheorie oder als Optimalitätsbedingungen (KKT) eines quadratischen Programms auf.