Schlupfvariable

Schlupfvariablen (engl. slack variables), auch Überschussvariablen genannt, sind mathematische Variablen, die für die Lösung eines Problems eingeführt werden, deren Wert aber nicht von Interesse ist. Die zusätzlichen Schlupfvariablen sollen ein Problem auf ein einfacheres Problem zurückführen.

Bei der linearen Optimierung führt man Schlupfvariablen ein, um Ungleichungsnebenbedingungen in Gleichungsnebenbedingungen umzuwandeln. Dies beruht auf der Idee, dass die Ungleichung x < b {\displaystyle x<b} erfüllt ist, wenn die Gleichung x = b − χ {\displaystyle x=b-\chi } für eine beliebige Zahl χ > 0 {\displaystyle \chi >0} gilt.

Lagrange-Multiplikatoren werden eingesetzt, um Optimierungsprobleme mit Nebenbedingungen in Optimierungsprobleme ohne Nebenbedingungen zu überführen.

Bei Support Vector Machines bilden Schlupfvariablen sogenannte Fehlerterme, das heißt, sie erlauben Fehlentscheidungen, bestrafen diese aber gleichzeitig.

Betrachte das Ungleichungssystem

2 x 1 + x 2 ≤ 6 7 x 1 − 3 x 2 ≤ 8 {\displaystyle {\begin{aligned}2x_{1}&+x_{2}&\leq 6\\7x_{1}&-3x_{2}&\leq 8\end{aligned}}}

Wir führen die Schlupfvariablen x 1 S , x 2 S ≥ 0 {\displaystyle x_{1}^{S},x_{2}^{S}\geq 0} ein, um die Ungleichungen in Gleichungen umzuwandeln. Dann folgt

2 x 1 + x 2 + x 1 S = 6 7 x 1 − 3 x 2 + x 2 S = 8 {\displaystyle {\begin{aligned}2x_{1}&+x_{2}&+x_{1}^{S}&&=6\\7x_{1}&-3x_{2}&&+x_{2}^{S}&=8\end{aligned}}}

Gerade in der linearen Optimierung findet man dafür oftmals die folgende Matrixschreibweise:

( 2 1 1 0 7 − 3 0 1 ) ⋅ ( x 1 x 2 x 1 S x 2 S ) = ( 6 8 ) {\displaystyle {\begin{pmatrix}2&1&1&0\\7&-3&0&1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\\x_{1}^{S}\\x_{2}^{S}\end{pmatrix}}={\begin{pmatrix}6\\8\end{pmatrix}}}

Das Einführen der Schlupfvariablen führt dazu, dass hinter der Koeffizientenmatrix ( 2 1 7 − 3 ) {\displaystyle {\begin{pmatrix}2&1\\7&-3\end{pmatrix}}} eine Einheitsmatrix passender Dimension ( 1 0 0 1 ) {\displaystyle {\begin{pmatrix}1&0\\0&1\end{pmatrix}}} angefügt wird.

• Hochstättler Winfried: Algorithmische Mathematik, Springer Berlin Heidelberg, 2010. ISBN 978-3-642-05421-1, 202–203
• Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer, Berlin 2012, ISBN 978-3-642-32185-6.