Lineares Komplementaritätsproblem

Das lineare Komplementaritätsproblem (LCP, engl Linear Complementarity Problem) ist definiert als:

Gegeben eine rationale Matrix $M\in R^{n\times n}$ und ein rationalwe Vektor $q\in R^{n}$, finde Vektoren $x,y\in R^{n}$ sodass

 $y=Mx+q~,~~x,y\geq 0~,~~x^{T}y=0$

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

Anwendung

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

Siehe auch

• Optimierung