die Frage nach der Lösbarkeit des folgenden Systems von Gleichungen und Ungleichungen: Gegeben seien eine Matrix M ∈ ℝ^n×n und ein Vektor q ∈ ℝⁿ. Gesucht sind Vektoren w = (w₁, …, w_n) und z = (z₁, …, z_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 w^t · 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̅ ∈ ℝⁿ das Minimum von x → c^T·x unter den Nebenbedingungen A · x ≥ b, x ≥ 0 mit A ∈ ℝ^m×n, b ∈ ℝ^m, c ∈ ℝⁿ, 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.