Direkt zum Inhalt

Lexikon der Mathematik: lineares Komplementaritätsproblem

die Frage nach der Lösbarkeit des folgenden Systems von Gleichungen und Ungleichungen: Gegeben seien eine Matrix M ∈ ℝn×n und ein Vektor q ∈ ℝn. Gesucht sind Vektoren w = (w1, …, wn) und z = (z1, …, zn) ∈ ℝn mit

\begin{eqnarray}\begin{array}\ll w-M\cdot z=q,\\ w\ge 0,z\ge 0,\text{und}\\ {w}_{1}\cdot {z}_{1}=0\forall 1\le i\le n.\end{array}\end{eqnarray}

Hierbei sind lediglich die letzten n Gleichungen als Komplementaritätsbedingung nichtlinear.

Jedes lineare Komplementaritätsproblem ist zu einem quadratischen Optimierungsproblem der folgenden Form äquivalent:

Minimiere wt · z unter den linearen Nebenbedingungen

\begin{eqnarray}\begin{array}{cc}w=M\cdot z+q, & w\ge 0,z\ge 0.\end{array}\end{eqnarray}

Ist M darüberhinaus eine positiv semi-definite Matrix, dann ist das zugehörige quadratische Programmierungsproblem konvex.

Lineare Komplementaritätsprobleme treten beispielsweise als notwendige und hinreichende Optimalitätsbedingungen bei der Lösung linearer Optimierungsprobleme auf. Ist etwa x̅ ∈ ℝn das Minimum von xcT·x unter den Nebenbedingungen A · xb, x ≥ 0 mit A ∈ ℝm×n, b ∈ ℝm, c ∈ ℝn, und ist y̅ ∈ ℝm die zugehörige Lösung des dualen Problems, dann gibt es einen Vektor w ∈ ℝm+n so, daß w und \(z:=\left(\begin{array}{c}\bar{x}\\ \bar{y}\end{array}\right)\) Lösung des linearen Komplementaritätsproblems mit

\begin{eqnarray}M:=\left(\begin{array}{cc}0 & -{A}^{T}\\ A & 0\end{array}\right)\text{und}q:=\left(\begin{array}{c}c\\ -b\end{array}\right)\end{eqnarray}

sind.

Die Umkehrung dieser Aussage gilt ebenfalls.

Ein Verfahren zur Lösung linearer Komplementaritätsprobleme ist zum Beispiel das Verfahren von Lemke (Lemke, Verfahren von). Auch gibt es Verfahren, die auf Innere-Punkte Methoden basieren.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte