Fourier-Motzkin-Elimination

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Fourier-Motzkin-Elimination ist ein Verfahren, um einen durch ein lineares Ungleichungssystem gegebenen konvexen Polyeder P(A,b) := \{x \;|\; A x \le b \} auf eine Hyperebene der Form  H := \{x \;|\; x_j = 0 \} zu projizieren. Dabei ist A \in \mathbb{R}^{m \times n} eine Matrix und b \in \mathbb{R}^{m} eine passende rechte Seite.

Das Verfahren wurde von Joseph Fourier im Jahr 1827 erstmals beschrieben,[1] geriet jedoch in Vergessenheit und wurde schließlich 1936 in der Doktorarbeit von Theodore Motzkin erneut entdeckt.[2]

Beschreibung des Verfahrens[Bearbeiten]

Der Algorithmus kombiniert die Zeilen A_{i \cdot} \ i \in M := \{1 \ldots m\} der Matrix A und die Einträge der rechten Seite b konisch zu neuen Ungleichungen. Dies geschieht in einer Weise, die sicherstellt, dass die resultierenden neuen Ungleichungen die Variable x_j nicht länger beinhalten.

Der Algorithmus wird durch folgenden Pseudocode beschrieben:

 function FourierMotzkin(A, b, j) is
     Eingabe: eine Matrix A der Dimension (m,n), ein Vektor b der Dimension m 
              und ein Index j \in \{1, \ldots, n\}
     Ausgabe: eine Matrix D der Dimension (r,n), sodass D_{ij}= 0 für alle i=1,\ldots,r 
              und ein Vektor d mit r Einträgen
     Z \leftarrow \{i \in M \;|\; a_{ij} = 0 \}
     N \leftarrow \{i \in M \;|\; a_{ij} < 0 \}
     P \leftarrow \{i \in M \;|\; a_{ij} > 0 \}
     R \leftarrow Z \cup (N \times P) 
     r \leftarrow | R | 
     p \leftarrow eine Indizierung der Elemente in R, also eine Bijektion  p : \{1,\ldots,r\} \rightarrow R 
     for i=1 to r do
         if  p(i) \in Z  then
             D_{i \cdot} \leftarrow A_{p(i) \cdot}
             d_{i}\ \leftarrow b_{p(i)}
         else if  p(i) = (s,t) \in N \times P  then
             D_{i \cdot} \leftarrow a_{tj} A_{s \cdot} - a_{sj} A_{t \cdot}
             d_{i}\ \leftarrow a_{tj} b_{s} - a_{sj} b_{t}
         endif
     endfor
     return (D,d)

Der resultierende Polyeder P(D,d) beschreibt anschließend die gewünschte Projektion [A. 1].

Beispiel für die Fourier-Motzkin-Elimination[Bearbeiten]

Die Projektion eines Polyeders auf verschiedene (lineare) Hyperebenen

Als Beispiel wählen wir den Polyeder P(A,b), der durch das folgende Ungleichungssystem gegeben ist:


P(A,b) = \{ (x,y) \in \mathbb{R}^2 \ |\ x \geq 1,\ 2x + 4y \leq 14,\ x - 2y \leq -1 \}

Die entsprechende Matrix und rechte Seite sind folglich


A = \left(
\begin{array}{rr}
-1 &  0 \\
 2 &  4 \\
 1 & -2 \\
\end{array}
\right),\ 

b = \left(
\begin{array}{r}
-1 \\
14 \\
-1 \\
\end{array}
\right)

Für die Projektion auf die Hyperebene x=0, also für j=1, erhalten wir die folgenden Mengen:

Z= \emptyset, N=\{1\} und P=\{2,3\}.

Damit ist r=2 und R=\{(1,2),\ (1,3)\}. Wir setzen p(1) = (1,2),\ p(2) = (1,3).

Für i = 1 kombinieren wir die erste und zweite Ungleichung:


2 \cdot (-x) - (-1) \cdot (2x+4y) \leq 2 \cdot (-1) - (-1) \cdot (14) \; \Longrightarrow \; 4y \leq 12

Für i = 2 erhalten wir durch die Kombination der ersten und dritten Ungleichung die folgende neue Ungleichung:


1 \cdot (-x) - (-1) \cdot (x -2y) \leq 1 \cdot (-1) - (-1) \cdot (-1) \; \Longrightarrow \; -2y \leq -2

Das Bild der Projektion ist also gegeben durch \{ (0,y) \in \mathbb{R}^2 \ | \  1 \leq y \leq 3 \}, während die resultierende Matrix D bzw. die rechte Seite d die folgende Gestalt haben:


D = \left(
\begin{array}{rr}
 0 &  4 \\
 0 & -2 \\
\end{array}
\right),\ 

d = \left(
\begin{array}{r}
12 \\
-2 \\
\end{array}
\right)

Die Fourier-Motzkin-Elimination aus Sicht der linearen Algebra[Bearbeiten]

Die im Algorithmus angewandten Zeilenoperationen lassen sich durch die Multiplikation der Matrix A bzw der rechten Seite b mit einer Matrix U \in \mathbb{R}_+^{r \times m} darstellen, deren i-te Zeile gegeben ist durch


U_{i \cdot} =
\begin{cases}
  e_k & \text{falls } p(i) = k \in Z \\
  a_{tj} e_s - a_{sj} e_t & \text{falls } p(i) = (s,t) \in N \times P \\
\end{cases}

Da die Matrix U eine konische Kombination der Zeilen von A beschreibt, sind alle Einträge von U nicht negativ. Im obigen Beispiel ist


U = \left(
\begin{array}{rrr}
 2 & 1 & 0 \\
 1 & 0 & 1 \\
\end{array}
\right)

Anwendungen[Bearbeiten]

Zulässigkeitsprobleme[Bearbeiten]

Die Fourier-Motzkin-Elimination hat als Projektionsverfahren die Eigenschaft, dass das System Ax \leq b eine Lösung besitzt genau dann wenn dies auch auf das System D x \leq d zutrifft.

Während es im Allgemeinen schwierig ist, zu entscheiden, ob ein konvexer Polyeder eine zulässige Lösung besitzt, lässt sich dies in einigen Spezialfällen recht leicht bewerkstelligen:

  • Verbleibt keine Variable in dem resultierenden System Dx \leq d, ist also D die Nullmatrix, so ist das System dann und nur dann lösbar, wenn die rechte Seite d nicht negativ ist
  • Enthält nur eine einzige zu einer Variable x_k gehörige Spalte der Matrix D von Null verschiedene Einträge, so entspricht die Projektion einem Intervall I. Ist dieses nicht leer, so ist auch das System A x \leq b lösbar. Weiterhin sind die möglichen Werte der Variablen x_k in dem Polyeder P(A,b) gerade durch das Intervall I gegeben


Diese Erkenntnis lässt sich nutzen, um zu überprüfen, ob ein beliebiges Polyeder P(A,b) eine zulässige Lösung hat oder nicht: Zunächst werden sämtliche Variablen nacheinander herausprojiziert:


P(A,b) \ \xrightarrow{\text{FourierMotzkin}(A,b,1)} \ P(D^{(1)},d^{(1)}) \ \xrightarrow{\text{FourierMotzkin}(D^{(1)},d^{(1)},2)} \ P(D^{(2)},d^{(2)}) \ \cdots \ P(D^{(n-1)},d^{(n-1)}) \ \xrightarrow{\text{FourierMotzkin}(D^{(n-1)},d^{(n-1)},n)} \  P(D^{(n)},d^{(n)})


Die resultierende Matrix D^{(n)} ist dann die Nullmatrix und man kann entscheiden, ob P(A,b) = \emptyset , denn P(A,b) = \emptyset gdw. P(D^{(n)},d^{(n)}) = \emptyset .

Insbesondere gilt P(A,b) \neq \emptyset gdw. d^{(n)} \geq 0 .

Da sich der j-te Projektionsschritt durch eine Multiplikation mit einer nichtnegativen Matrix U^{(j)} ausführen lässt, gilt außerdem:


D^{(n)} = U \cdot A,\ d^{(n)} = U \cdot b, \; \text{wobei} \; U := U^{(n)} \cdot U^{(n-1)} \ldots U^{(1)}
.

Wenn der k-te Eintrag von d^{(n)} negativ ist, so ist u \cdot A = 0 und u \cdot b < 0, wobei u := e_k \cdot U. Diese Aussage entspricht dem Farkas' Lemma. Da sich die Matrizen U^{(j)} während der Ausführung des Algorithmus aufstellen lassen, bietet die Fourier-Motzkin-Elimination damit die Möglichkeit, das Zertifikat für P(A,b) = \emptyset explizit zu berechnen.

Zusätzlich impliziert die Fourier-Motzkin-Elimination, dass die Projektion eines Polyeders wieder ein Polyeder ist. Dieses Resultat kann benutzt werden, um die Äquivalenz der \mathcal{V}- und \mathcal{H}-Darstellung von Polyedern zu zeigen.

Beispiel zur Entscheidung der Zulässigkeit[Bearbeiten]

Wir wollen entscheiden, ob der folgende konvexe Polyeder eine zulässige Lösung hat:


P(A,b) = \{ x \in \mathbb{R}^2 \ |\ x_1 + x_2 \geq 4,\ x_1 \leq 1,\ x_2 \leq 1 \}

Dies entspricht in der Form Ax \leq b dem System


\left[
\begin{array}{rrr}
 - x_1 & -  x_2   & \leq -4 \\
   x_1 &          & \leq  1 \\
       & x_2      & \leq  1 \\
\end{array}
\right]
\;\;

Nach den einzelnen Projektionsschritten ergeben sich folgenden Systeme:



\left[
\begin{array}{rr}
-x_2     & \leq -3 \\
 x_2     & \leq  1 \\
\end{array}
\right]

\;\;

\left[
\begin{align}
0     & \leq -2 \\
\end{align}
\right]

Es offenbart sich also ein Widerspruch, der Polyeder P(A,b) entspricht der leeren Menge. Die resultierenden Matrizen sind gegeben durch


U^{(1)} = \left(
\begin{array}{rrr}
 1 & 1 & 0 \\
 0 & 0 & 1 \\
\end{array}
\right) , \;\;
U^{(2)} = \left(
\begin{array}{rr}
 1 & 1 \\
\end{array}
\right)

Ein Zertifikat für die Nichtzulässigkeit ist also der Vektor e_1 U^{(2)} U^{(1)} = (1, 1, 1).

Lösung von linearen Programmen[Bearbeiten]

Durch Ausnutzen der Dualität der linearen Optimierung lässt sich jedes lineare Programm auf ein Zulässigkeitsproblem reduzieren, welches sich dann durch die Anwendung der Fourier-Motzkin-Elimination lösen lässt. In diesem Fall benötigt man jedoch recht viele neue Variablen und Ungleichungen, was die Anwendung des Verfahrens verlangsamt. Alternativ kann man den folgende Ansatz wählen: Um das Problem \max \{ c^T x \; | \; A x \leq b \} zu lösen, führt man eine zusätzliche Variable y \in \mathbb{R} ein, und fordert zusätzlich, dass y \leq c^T x. Der Wert der Variablen y ist also durch die Optimallösung des Problems beschränkt. Man erhält dadurch einen Polyeder P(\tilde{A},\tilde{b}) mit


\tilde{A} = \left(
\begin{array}{rr}
  A   & 0 \\
 -c^T & 1 \\
\end{array}
\right) \in \mathbb{R}^{m + 1 \times n + 1} ,\ 

\tilde{b} = \left(
\begin{array}{r}
b \\
0 \\
\end{array}
\right) \in \mathbb{R}^{m + 1}

Man projiziert anschließend die ersten n Einträge heraus, sodass man schließlich ein System der Form


\begin{align}
D^{(n)}_{1,n+1} y &\leq d^{(n)}_1 \\
\vdots & \\
D^{(n)}_{l,n+1} y &\leq d^{(n)}_l \\
\end{align}

erhält. Das resultierende Intervall I beschreibt die Menge der möglichen Werte für die Variable y. Es treten folgende Fälle auf:

  1. Das Intervall ist leer. In diesem Fall besitzt das Optimierungsproblem keine zulässige Lösung.
  2. Das Intervall ist nicht nach oben beschränkt. Damit ist auch das Optimierungsproblem unbeschränkt.
  3. Das Intervall ist nicht leer und besitzt ein maximales Element \gamma. Damit ist der Zielfunktionswert der Optimallösung des Problems genau b.

Um eine Lösung x^* mit einem gegebenen Zielfunktionswert y^* := \gamma zu erhalten, geht man wie folgt vor: Zunächst betrachtet man das System nach der n-1-ten Iteration: Es treten nur noch die Variablen y und x_n auf, wobei der Wert von y schon auf y^* festgelegt ist:


\begin{align}
D^{n-1}_{1,n} x_n + D^{n-1}_{1,n+1} y &\leq d^{n-1}_1 \\
\vdots & \\
D^{n-1}_{l,n} x_n + D^{n-1}_{l,n+1} y &\leq d^{n-1}_l \\
\end{align}

Man erhält somit ein (nicht leeres) Intervall von möglichen Lösungen für x_n, von denen man eine beliebige auswählt. Diesen Prozess iteriert man für x_{n-1}, \ldots, x_{1} [A. 2].

Beispiel zur Lösung eines linearen Programms[Bearbeiten]

Zur Illustration des Verfahrens wählen wir das Programm


\begin{align}

\max~             & x_1               \\
\text{so dass }   & x_1 + x_2 \leq 4  \\
                  & x_1 \geq 0        \\
                  & x_2 \geq 0        \\
\end{align}

Um das Problem zu lösen, fügen wir die Variable y zusammen mit der Ungleichung y \leq x_1 zu dem Problem hinzu. Die folgenden Systeme zeigen den Polyeder P(\tilde{A},\tilde{b}), sowie die veränderten Systeme nach der Projektion auf \{x_1=0\} und \{x_2 = 0\}:


\left[
\begin{array}{rrrr}
  x_1 & +  x_2 &     & \leq 4 \\
 -x_1 &        &     & \leq 0 \\
      & -  x_2 &     & \leq 0 \\
 -x_1 &        & + y & \leq 0 \\
\end{array}
\right]
\;\;

\left[
\begin{array}{rr}
-x_2     & \leq 0 \\
 x_2     & \leq 4 \\
 x_2 + y & \leq 4 \\
\end{array}
\right]

\;\;

\left[
\begin{align}
0     & \leq 0 \\
y     & \leq 4 \\
\end{align}
\right]

Damit steht fest, dass die Optimallösung des Problems den Zielfunktionswert 4 hat. Um eine entsprechende Lösung zu erhalten, setzen wir y^*=4 und kehren zum vorletzten Schritt zurück. Es ergibt sich das System


\begin{align}
-x_2     & \leq 0 \\
 x_2     & \leq 4 \\
 x_2     & \leq 0 \\
\end{align}

Es bleibt also nichts anderes übrig, als x_2^* = 0 zu setzen. Der Wert von x_1^* ergibt sich schlussendlich aus dem System


\begin{align}
  x_1 & \leq 4 \\
 -x_1 & \leq 0 \\
 -x_1 & \leq -4 \\
\end{align}

Damit ist die Optimallösung (x_1^*,x_2^*) = (4,0). Diese hat natürlich auch den erwarteten Zielfunktionswert von y^*=4.

Laufzeit[Bearbeiten]

Obwohl die Fourier-Motzkin-Elimination zur Lösung von linearen Programmen verwendet werden kann, gibt man in der Praxis anderen Algorithmen den Vorzug. Das Problem der Fourier-Motzkin-Elimination ist, dass im ungünstigsten Fall die Anzahl der Ungleichungen bzw. die Größe der Matrizen D^{(j)} in jeden Projektionsschritt von vorher m auf \left( \frac{m}{2} \right)^2 anwächst. In diesem Fall ist die Laufzeit des Algorithmus nicht mehr polynomiell. Im Allgemeinen sind außerdem die meisten der erzeugten Ungleichungen redundant. Da dies in der Regel allerdings nicht effizient erkannt werden kann, wird für die Fourier-Motzkin-Elimination weit mehr Speicher gebraucht als nötig wäre, um die Polyeder P(D^{(j)},d^{(j)}) zu beschreiben.

Anmerkungen[Bearbeiten]

  1. Da die Menge R im Allgemeinen sehr groß werden kann, ist es ratsam, die Ungleichungen zunächst so zu skalieren, dass a_{ij} \in \{ \pm 1, 0\} für alle i \in \{1, \ldots m\}. Zur Bestimmung von D und d müssen die Spalten dann nur noch voneinander subtrahiert werden.
  2. Das hier vorgestellte Verfahren des Rückwärtseinsetzens lässt sich stets anwenden, um eine zulässige Lösung des Polyeders zu erhalten.

Einzelnachweise[Bearbeiten]

  1. J.B.J. Fourier aus dem Journal: Analyse des travaux de l'Académie Royale des Sciences pendant l'année 1824, Partie mathématique, 1827.
  2. T.S. Motzkin: Beiträge zur Theorie der Linearen Ungleichungen.

Literatur[Bearbeiten]

  • Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6, S. 155–156.
  • H. P. Williams: Fourier's Method of Linear Programming and its Dual. In: American Mathematical Monthly. 93, 1986, S. 681–695.
  • Unger, Thomas; Dempe, Stefan: Lineare Optimierung, S. 19-23, Vieweg+Teubner 2010, ISBN 978-3-8351-0139-5

Weblinks[Bearbeiten]