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 zur Lösung von linearen Komplementaritätsproblemen sind bekannt.

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

See also

• Optimierung