eine Methode zur Lösung linearer Komplemetaritätsprobleme der Form

\begin{eqnarray}\begin{array}{ll}w-M\cdot z=q, & \\ w\ge 0,z\ge 0, & {w}^{T}\cdot z=0.\end{array}\end{eqnarray}

Unter der Annahme, daß q ≥ 0 nicht gilt (ansonsten ist z:= 0, w := q eine Lösung), führt man eine weitere Variable t ≥ 0 ein, und verändert das Ausgangsproblem zu

\begin{eqnarray}\begin{array}{l}w=M\cdot z={e}^{T}\cdot t+q,\\ w\ge 0, z\ge 0, t\ge 0,\end{array}\end{eqnarray}

und e := (1, …, 1)^T. Mit q_i0 := min{q_j, j} und der Wahl t := −q_i0, w_k := q_k − q_i0 für k ≠ i₀, sowie w_i0 = 0, z:= 0, gewinnt man eine Ecke des zugehörigen Polyeders. Für diese sind w_i0 und alle z_k Nichtbasisvariablen. Jetzt werden wie im Simplexverfahren – allerdings ohne das Vorhandensein einer Zielfunktion – Austauschschritte durchgeführt, wobei z_i0 die erste Pivotspalte festlegt. Ziel ist es, die Variable t aus der Basis zu entfernen. Im Falle einer positiv definiten Matrix M ist dann das Problem gelöst.