imported>부고: /* Literatur */

2016-08-30T13:55:53Z

Literatur

Neue Seite

Das '''lineare Komplementaritätsproblem''' (''LKP'', [[Englische Sprache|engl.]] ''linear complementarity problem'') ist ein mathematisches Problem aus der [[Lineare Algebra|Linearen Algebra]].

Gegeben sei eine reelle Matrix <math>M \in \R^{n \times n}</math> und ein reeller Vektor <math>q \in \R^n</math>, dann finde Vektoren <math>x, y \in \R^n</math> so, dass die drei Bedingungen gelten:
:<math>y=Mx+q~, ~ ~ x,y \geq 0~, ~ ~ x_i y_i=0</math> für alle <math>i</math>

Eine eindeutige Lösung für dieses Problem existiert genau dann, wenn M eine P-Matrix ist, das heißt, dass alle prinzipalen [[Minor (Mathematik)|Minoren]] der Matrix M strikt positiv sind. Verschiedene [[Algorithmus|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 [[Optimierung (Mathematik)|Optimalitätsbedingungen]] (KKT) eines [[Quadratisches Programm|quadratischen Programms]] auf.

Das Problem wurde 1968 von [[Richard Warren Cottle]] und [[George Dantzig]] eingeführt.
==Literatur==
*Richard W. Cottle, [[Jong-Shi Pang]], Richard E. Stone: The linear complementarity problem, Academic Press 1992, SIAM 2009
[[Kategorie:Lineare Optimierung]]
[[Kategorie:Lineare Algebra]]

Lineares Komplementaritätsproblem - Versionsgeschichte

imported>부고: /* Literatur */