Optimierte Lösung

Für die optimierte Lösung werden alle Randhyperebenen außer Punkten, Geraden und Hyperebenen der Dimensionalität $d-1$ weggelassen. Der hier gegebene Algorithmus ist für mindestens drei Parameter ($3 \leq d$). Wenn die Lösung nur zwei oder ein Parameter hat, kann ein anderer Algorithmus verwendet werden, bzw. der nachfolgende Algorthmus angepasst werden.

0 Initialisiere die Hyperebenen ($K$ und $E$) mit dem Hyperkörper der maximalen Lösungsmenge (eventuell unter Zuhilfenahme von $v_{max}$)

1 Prüfe $i$:

1.1 Fall 1: Wenn $i$ größer $n$, setze $i$ auf $n$ und gehe zu "8. Lösung ermitteln"

1.2 Sonst: Nehme nächste Ungleichung $U_i$

1.2.1 Erstelle eine orientierte Hyperfläche $H$ für aktuelle Ungleichung $U_i=U[i]$ als Normalgleichung, mit dem Normalenvektor $N$ in Richtung der zulässigen Lösungen. Aus der Ungleichung $U_i$ in der Form $y_i \leq a_1 * x_{i.1} + a_2 * x_{i.2} + \ldots + a_d * x_{i.d}$ wird die Normalengleichung $\vec{x_i} \cdot \vec{a} - y_i = 0$ mit $\vec{x_i} = (x_{i.1}, \ldots, x_{i.d})^T$ und $\vec{a} = (a_{1}, \ldots, a_{d})^T$

2. Prüfe für alle Punkte auf welcher Seite der Hyperflache $H$ sie liegen

2.1 Fall 1: alle Eckpunkte $E_k$ liegen in Richtung des Normalenvektors $N$ oder auf der Hyperebene -> erhöhe Zähler $i$ und gehe zu 1. (die Hyperfläche $H$ schränkt die Lösungsmenge nicht weiter ein, d. h. $H$ ist nicht relevant)

2.2 Fall 2: alle Eckpunkte $E_k$ liegen nicht in Richtung des Normalenvektors $N$ -> erniedrige Zähler $i$ und gehe zu "8. Lösung ermitteln" (durch die Hinzunahme der Ungleichung $U_i$ gäbe es keine Lösungen mehr, bzw. die Ungleichung $U_i$ macht das bisherige Gleichungsystem unlösbar)

2.3 Sonst: einige Eckpunkte $E_k$ liegen in Richtung des Normalenvektors $N$, andere nicht -> gehe zu Schritt 3., bzw. integriere die Hyperfläche $H$ in den konvexer Hyperkörper der möglichen Lösungen

3 ermittle alle (Rand-) Linien/Geraden $L_z$ des Hyperkörpers $K$ zwischen den Eckpunkten $E_o$ nicht in Richtung des Normalenvektors $N$ und Eckpunkten $E_i$ in dessen Richtung (ignoriere Eckpunkte $E_{ho}$ auf $H$)

3.1 für jede dieser Geraden $L_z$: ermittle Schnittpunkte $E_{hn}$ mit der Hyperfläche $H$ und füge sie zum Hyperkörper hinzu

3.2 finde Geraden zwischen den Schnittpunkten auf $H$, welche einen konvexen Körper bilden: für jeden Schnittpunkt $E_{h1}$ auf $H$ ( $\{E_{h1}\} = \{E_{h2}\} = \{E_{ho}\} \cup \{E_{hn}\}$ ) ermittle alle Schnittpunkt $E_{h2}$ auf $H$ die gemeinsam auf mindestens $d-2$ anderen Hyperflächen $H_a$ ($H \neq H_a$) liegen. (Diese Hyperflächen sollten zusammen mit der Hyperfläche $H$ als Schnittfläche eine Gerade haben. Da $H$ die Dimensionalität $d-1$ hat und der Schnitt mit jeder weiteren ($d-1$ dimensionalen) Hyperflächen die Dimensionalität der Schnittfläche um eins verringert.)

3.2.1 ermittle Geraden $G$ zwischen $E_{h1}$ und $E_{h2}$ die gemeinsam auf gemeinsammen anderen Hyperfläche $H_l$ liegen

3.2.2 füge Geraden $G$ zu $K$ und als auf $H$ liegend hinzu

3.2.3 füge $E_{h1}$ und $E_{h2}$ als auf $G$ liegend hinzu

4. entferne alle Eckpunkte $E_k$ die nicht in Richtung des Normalenvektors $N$ von $H$ liegen

5. entferne alle Gerade $G$ die nur noch einen Eckpunkt besitzen

6. entferne alle Hyperflächen auf denen keine Geraden mehr liegen

7. wenn $i < n$: erhöhe Zähler $i$ und gehe zu 1. (sonst 8.)

8. Lösung ermitteln:

8.1. Alternative 1:

8.1.1. Gebe $E$ als Eckpunkte der (konvexen) Lösungsmenge und $i$ als Anzahl der erfüllten Ungleichungen zurück (eine Lösung kann dann aus dem Bereich $E$ ermittelt werden)

8.1. Alternative 2:

8.1.1. Nehme den Mittelpunkt /Schwerpunkt $M$ aller Eckpunkte $E_k$: $M = 1 / \sharp E * \sum_{i=1}^{\sharp E} E_k$

8.1.2. Gebe $M$ als Lösung und $i$ als Anzahl der erfüllten Ungleichungen zurück