Lineares Komplementaritätsproblem
aus Wikipedia, der freien Enzyklopädie
Lemke-Algorithmus (LCP, engl Linear Complementarity Problem) ist definiert als:
Gegeben eine rationale Matrix 
und ein rationaler Vektor 
, finde Vektoren 
so, dass
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. Lemke's Algorithmus, oder mittels Unique Sink Orientations) zur Lösung von linearen Komplementaritätsproblemen sind bekannt.
[Bearbeiten] Anwendung
Lineare Komplementaritätsprobleme tauchen in der Praxis z.B. in der Spieltheorie oder als Optimalitäts-Bedingungen (KKT) eines quadratischen Programms auf.
