Homepage von Boris Haase




Vorherige

#55: Verbesserung lineare Optimierung vom 23.05.2020

Das Folgende setzt Mengenlehre, Topologie und Nichtstandardanalysis voraus. Das exponentielle Simplex- und das polynomielle Intexverfahren (Inter-/Extrapolation) lösen lineare Programme (LPs).

Durchmessersatz für Polytope: Der Durchmesser eines durch \(m\) Restriktionen gegebenen \(n\)-dimensionalen Polytops mit \(m, n \in {}^{\omega}\mathbb{N}_{\ge 2}\) ist maximal \(2(m + n - 3)\).

Beweis: Maximal \(m - 1\) Hyperebenen lassen sich zu einem unvollständigen Zyklus der Dimension 2 zusammenstellen und es gibt maximal \(n - 2\) Ausweichmöglichkeiten zur Seite in den restlichen Dimensionen. Das Überwinden jeder minimalen Strecke benötigt maximal zwei Kanten und liefert den Faktor 2.\(\square\)

Bemerkung: Fällt die endliche Beschränkung weg, lässt sich der Satz sinngemäß auf Polyeder übertragen.

Definition: Sei \(\vartheta := {_e}\omega \omega\) und \({|| \cdot ||}_{1}\) die 1-Norm. Jeder in den nächsten Schritt übergegangenen Variablen \(x \in X \subseteq {}^{\omega}\mathbb{R}^{\omega}\) folgt \({}^{*}\) mit \(\Delta x := {x}^{*} - x\). Der Einheitsvektor von \(x\) ist \({_1}{x} := x/||x||\), wobei \(_1{0}\) undefiniert ist. Seien \(x, y \in X \) in \((x, y, ...)^T\) Zeilenvektoren. Benötigt ein Verfahren Rechenzeit in Sekunden und Speicher in Bits von \(\mathcal{O}({\omega}^{\mathcal{O}(1)})\), ist es polynomiell. Ist eine der beiden Größen \(\mathcal{O}({e}^{|\mathcal{O}(\omega)|})\), ist es exponentiell. Das Eigenprodukt (bisher: Determinante) einer quadratischen Matrix sei das Produkt ihrer Eigenwerte.\(\triangle\)

Satz: Das Simplexverfahren ist exponentiell.

Beweis und Algorithmus: Sei \(P := \{x \in {}^{\omega}\mathbb{R}^{n} : Ax \le b, b \in {}^{\omega}\mathbb{R}^{m}, A \in {}^{\omega}\mathbb{R}^{m \times n}, m, n \in {}^{\omega}\mathbb{N}^{*}\}\) der zulässige Bereich des LPs max \(\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in P\}\), dessen Dualisierung \({x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}\) erzielt. Mit \(x := {x}^{+} - {x}^{-}\) für \({x}^{+}, {x}^{-} \ge 0\) wird \({x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{2n}\) erreicht. Mit Startpunkt \(x := 0\) liefert das Lösen von max \(\{-z : Ax - b \le {(z, ..., z)}^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}\}\) ein zulässiges \(x\), falls \(b \ge 0\) nicht gilt. Start- und Zielwert von \(z\) sei \(|\text{min } \{{b}_{1}, ..., {b}_{m}\}|\) bzw. 0.

Ein geeigneter Pivotschritt bewirkt \({b}^{*} \ge 0\). Seien \(i, j, k \in {}^{\omega}\mathbb{N}^{*}\) und sei \({a}_{i}^{T}\) der \(i\)-te Zeilenvektor von \(A\). Gilt \({c}_{j} \le 0\) für alle \(j\), ist das LP gelöst. Gibt es ein \({c}_{j} > 0\) mit \({a}_{ij} \le 0\) für alle \(i\), ist das LP positiv unbeschränkt. Existiert ein \({c}_{j} = 0\) mit \({a}_{ij} \le 0\) für alle \(i\), lassen sich \({c}_{j}\) und \({A}_{.j}\) wie die \({b}_{i}\) und \({a}_{i}\) mit \({a}_{ij} < 0\) vorerst entfernen. Unlösbar ist auch \({a}_{ij}{x}_{j} \ge 0 > {b}_{i}\) für alle \(j\). Das eventuelle Teilen aller \({a}_{i}^{T}x \le {b}_{i}\) durch \(||{a}_{i}||\) und aller \({c}_{j}\) bzw. \({a}_{ij}\) durch min \(|{a}_{ij}|\) für \({a}_{ij} \ne 0\) sowie jedes \(j\) wird am Ende rückgängig gemacht.

Die Normierung mit \(||{a}_{i}||\) wird eventuell wiederholt. Überflüssige Restriktionen (mit \({a}_{i} \le 0\)) lassen sich stets entfernen. Die Wahl eines minimalen Quotienten \({b}_{k}/{a}_{kj}\) für \({a}_{ij} > 0\) und jedes \({c}_{j} > 0\) sowie Nichtbasisvariablen \({x}_{j}\) liefert durch \({x}_{j}^{*} = {x}_{j} + {b}_{k}/{a}_{kj}\) die potenzielle nächste zulässige Ecke \({x}^{*}\). Bei Wahl der steilsten Kante bildet \({a}_{kj}\) das Pivotelement zu dem \({x}_{j}\), das \({c}^{T}{_1}{\Delta x}\) bzw. \({c}_{j}^{2}/(1 + {||{A}_{.j}||}^{2})\) in der \(k\)-ten Restriktion maximiert.

Mehrere Maxima erlauben die Verwendung der Pivotregel des Bestwerts max\({}_{k,j} {c}_{j}{b}_{k}/{a}_{kj}\) oder (langsamer) des kleinsten Winkels min \({{_{(1)}}(1, ..., 1)}^{T}{_1}{c}^{*}\). Die Unmöglichkeit die Zielfunktion direkt zu maximieren führt zur Gleichbehandlung der Restriktionen mit \({b}_{i} = 0\) durch Abschwächung (also Perturbation) um den gleichen minimalen Betrag, der mit \({b}_{i} := ||{a}_{i}||\) nicht im Tableau zu stehen braucht.

Tritt erneut eine mehrfache Ecke auf, obwohl dies nicht sehr wahrscheinlich ist, werden die \({b}_{i}\) von eben einfach um \(||{a}_{i}||\) erhöht. Das Verlassen einer mehrfachen Ecke kann das Lösen eines LPs mit \(c > 0\) und \(b = 0\) erfordern. Die Zielfunktion wächst auf dem zurückgelegten Weg ansonsten streng monoton. Schließlich lassen sich \({c}_{j}^{*}, {a}_{ij}^{*}\) und \({b}_{i}^{*}\) nach der Rechteckregel einfach berechnen (vgl. [775], S. 63).

Trotz des Durchmessersatzes für Polytope macht keine Pivotregel das Simplexverfahren im schlechtesten Fall polynomiell, da die Konstruktion eines Polytops (z. B. vom Klee-Minty- oder Jeroslow-Typ) ein exponentielles "Driften" mit Auswahl einer jeweils ungünstigen Kante erzwingen kann, das vom kürzesten Pfad erheblich abweicht. In Übereinstimmung mit dem Forschungsstand folgt die Behauptung.\(\square\)

Satz: Das Intexverfahren löst jedes lösbare LP in \(\mathcal{O}({\vartheta}^{3})\).

Beweis und Algorithmus: Zuerst werden \({b}^{T}y - {c}^{T}x \le 0, Ax \le b\) sowie \({A}^{T}y \ge c\) normiert und skaliert. Die Höhe \(h\) habe den Startwert \(h_0 := s |\min \; \{b_1, ..., b_m, -d_1, ..., -d_n\}|\) mit dem Steigerungsfaktor \(s \in \, ]1, 2]\). Das LP min \(\{h \in [0, h_0] : x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}, y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m},{b}^{T}y - {c}^{T}x \le h, Ax - b \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, c - {A}^{T}y \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}\) hat \(k\) Restriktionen und den zulässigen inneren Startpunkt \((x_0, y_0, h_0/s)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1}\), z. B. \((0, 0, h_0/s)^{T}\). Es identifiziert die zueinander dualen LPs max \(\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}\) und min \(\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\}\).

Der Punkt \(p := (x, y, h)^T\) approximiere den Schwerpunkt des Teilpolytops \(P^*\) zu \(p_k^* := (\min p_k + \max p_k)/2\), bis \({|| \Delta p ||}_{1}\) hinreichend klein ist. Hier hat \(x\) Vorrang vor \(y\). Dann wird \(p\) über \({p}^{*}\) in \(\partial P^*\) als \(t\) extrapoliert. Mit \(p := p^* + (t - p^*)/s\) wird \(\partial P^*\) gemieden. Folgt min\({}_{k} {h}_{k} r = 0\) aus \(r :=\) min\({}_{k} \Delta{h}_{k}\), wird aufgehört, andernfalls wiederholt, bis min \(h = 0\) oder min \(h > 0\) feststeht. Da fast jeder Durchlauf \(h\) in \(\mathcal{O}({\omega\vartheta}^{2})\) wenigstens halbiert, liefert der starke Dualitätssatz ([775], S. 60 - 65) die Behauptung.\(\square\)

Folgerung: Ist weder ein primal zulässiges \(x\) noch eine duale Lösung \(y\) zu berechnen, lässt sich die Laufzeit des LPs max \(\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}\) mit \(h := {c}^{T}x\) ungefähr halbieren.\(\square\)

Bemerkungen: Simplexverfahren und Face-Algorithmus ([916], S. 580 f.) lösen das LP für kleine \(m\) und \(n\) eventuell schneller. Der aktuelle Bestand der Restriktionen bzw. Variablen lässt sich einfach verändern, da das Intexverfahren ein nicht-transformierendes Verfahren und schneller als alle bekannten (Worst-Case-)LP-Algorithmen in \(\mathcal{O}({{_e}\omega \omega}^{19/6})\) ist. Seine Implementierungsdetails werden erst veröffentlicht, wenn kein Missbrauch für intransparente oder schlechte Entscheidungen zu befürchten ist.

Korollar: Das LP max \(\{{||x - {x}^{o}||}_{1} : {c}^{T}x = {c}^{T}{x}^{o}, Ax \le b, x - {x}^{o} \in {[-1, 1]}^{n}, x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}\) kann zur ersten Lösung \({x}^{o}\) ggf. eine zweite in \(\mathcal{O}({\omega\vartheta}^{2})\) bestimmen, wobei \({y}^{o}\) analog behandelt werden kann.\(\square\)

Korollar: Die Eigenwerte \(\lambda \in {}^{\omega}\mathbb{R}\) der Matrix \(A \in {}^{\omega}\mathbb{R}^{n \times n}\) und deren Eigenvektoren \(x \ne 0\) sind o. B. d. A. gerade die in \(\mathcal{O}({\omega\vartheta}^{2})\) ermittelbaren Lösungen der LPs max \(\{\lambda \in [0, h_0]: Ax = \pm\lambda x, x \in {[-1, 1]}^{n} \setminus \{0\}\}.\square\)

Korollar: Das LP min \(\{h \in [0, s \, \text{max } \{|{b}_{1}|, ..., |{b}_{m}|\}] : \pm(Ax - b) \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}\}\) kann ein \(x \in {}^{\omega}\mathbb{R}^{n}\) jedes lösbaren linearen Gleichungssystems (LGS) \(Ax = b\) in \(\mathcal{O}({\vartheta}^{3})\) bestimmen. Die LPs max \(\{{x}_{j} : Ax = 0\}\) liefern alle Lösungen des LGS. Die Matrix \(A\) ist genau dann regulär, wenn das LP max \(\{{||x||}_{1} : Ax = 0\} = 0\) ist.\(\square\)

Korollar: Sei \({\alpha }_{j} := {A}_{.j}^{-1}\) für \(j = 1, ..., n\) zur Matrix \({A}^{-1} \in {}^{\omega}\mathbb{R}^{n \times n}\) und sei \({\delta}_{ij}\) das Kronecker-Delta. Für reguläres \(A\) ist das Eigenprodukt \(\ne 0\) und lässt sich jedes LGS \({A \alpha }_{j} = {({\delta}_{1j}, ..., {\delta}_{nj})}^{T}\) in \(\mathcal{O}({\vartheta}^{3})\) lösen.\(\square\)

Korollar: Ist \(q \in [0, 1]\) die Dichte von \(A\), gilt oben bei Verwendung von ausschließlich endlichen reellen Zahlen überall max \(\{\mathcal{O}(qmn), \mathcal{O}(m + n)\}\) bzw. max \(\{\mathcal{O}(q{n}^{2}), \mathcal{O}(n)\}\) statt \(\mathcal{O}({\vartheta}^{3})\) bzw. \(\mathcal{O}({\omega\vartheta}^{2}).\square\)

Bemerkungen: Diese fünf Korollare lassen sich leicht ins Komplexe überführen. Das Intexverfahren ist numerisch sehr stabil, da sich Rundungsfehler auch durch Rückgriff auf die Ausgangsdaten und eine nach Klein modifizierte Kahan-Babuška-Neumaier-Summierung insbesondere gegen Ende klein halten lassen. Wird es für verteiltes Rechnen in \({}^{\nu}\mathbb{R}^{\nu}\) optimiert, beträgt seine Laufzeit nur \(\mathcal{O}(1)\). Es eignet sich außerdem gut für (gemischt-)ganzzahlige Probleme und die (nicht-)konvexe (Pareto-)Optimierung.

Korollar: Jedes lösbare konvexe Programm min \(\{{f}_{1}(x) : x \in {}^{\omega}\mathbb{R}^{n}, {({f}_{2}(x), ..., {f}_{m}(x))}^{T} \le 0\}\) mit konvexen Funktionen \({f}_{i} \in {}^{\omega}\mathbb{R}\) für \(i = 1, …, m\) lässt sich durch Intex- und zweidimensionale Bisektions- oder Newtonverfahren in polynomieller Laufzeit lösen, wenn die Anzahl der Operanden \({x}_{j}\) der \({f}_{i} \le {\omega}^{\nu-3}\) ist und ein \(x\) existiert mit\({f}_{i}(x) < 0\) für alle \(i > 1\) (vgl. [939], S. 589 ff.).\(\square\)

Programmtext des Simplexverfahrens

© 23.05.2020 by Boris Haase


Valid XHTML 1.0 • Datenschutz • Haftungsausschluss • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • MWiki • Seitenbeginn