Homepage von Boris Haase




Euklidische Geometrie • Gerechtes Verteilen • Lineare Optimierung • Mengenlehre • Nichtstandardanalysis • Ratschläge • Topologie • Zahlentheorie • Zeitrechnung  (Vorherige | Nächste)



Lineare Optimierung

Lineare Optimierung

Im Folgenden setzen wir Mengenlehre 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 := \ell \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\). Benötigt ein Verfahren eine Rechenzeit in Sekunden und einen 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.

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 \(\{{d}^{T}x : d \in {}^{\omega}\mathbb{R}^{n}, x \in P\}\). Dessen Dualisierung erreicht \({x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}\). Setzen wir \(x := {x}^{+} - {x}^{-}\) mit \({x}^{+}, {x}^{-} \ge 0\), erzielen wir \({x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{2n}\). Wir lösen max \(\{-z : Ax - b \le {(z, ..., z)}^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}\}\), um zuerst ein zulässiges \(x\) zu erhalten, falls \(b \ge 0\) nicht gilt. Der Startwert für \(z\) sei \(|\text{min } \{{b}_{1}, ..., {b}_{m}\}|\), sein Zielwert 0 und der Startpunkt \(x := 0\). Ein geeigneter Pivotschritt ergibt \({b}^{*} \ge 0\).

Seien \(i, j, k \in {}^{\omega}\mathbb{N}^{*}\) und sei \({a}_{i}^{T}\) der \(i\)-te Zeilenvektor von \(A\). Gilt \({d}_{j} \le 0\) für alle \(j\), ist das LP gelöst. Gibt es ein \({d}_{j} > 0\) mit \({a}_{ij} \le 0\) für alle \(i\), ist das LP positiv unbeschränkt. Existiert ein \({d}_{j} = 0\) mit \({a}_{ij} \le 0\) für alle \(i\), lassen sich \({d}_{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\). Wir teilen eventuell alle \({a}_{i}^{T}x \le {b}_{i}\) durch \(||{a}_{i}||\) und alle \({d}_{j}\) bzw. \({a}_{ij}\) durch min \(|{a}_{ij}|\) für \({a}_{ij} \ne 0\) sowie jedes \(j\). Letzteres machen wir am Ende rückgängig.

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

Bei mehreren Maxima lässt sich die Pivotregel des Bestwerts max\({}_{k,j} {d}_{j}{b}_{k}/{a}_{kj}\) oder eventuell weniger erfolgreich des kleinsten Winkels min \({(1, ..., 1)}^{T}d^{*}/||(\sqrt{n}) d^{*}||\) verwenden. Kann die Zielfunktion nicht auf direktem Wege maximiert werden, behandeln wir die Restriktionen mit \({b}_{i} = 0\) gleich, indem wir sie um einen identischen, aber minimalen Betrag abschwächen, also perturbieren. Diesen brauchen wir im Tableau selbst nicht zu notieren: Wir setzen einfach \({b}_{i} = ||{a}_{i}||\).

Tritt erneut eine mehrfache Ecke auf, obwohl dies nicht sehr wahrscheinlich ist, erhöhen wir die \({b}_{i}\) von eben einfach um \(||{a}_{i}||\). Eine mehrfache Ecke zu verlassen, wonach wir die Abschwächungen zurücknehmen, kann das Lösen eines LPs mit \(d > 0\) und \(b = 0\) erfordern. Die Zielfunktion wächst auf dem zurückgelegten Weg ansonsten streng monoton. Schließlich lassen sich \({d}_{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 ein exponentielles "Driften" durch ein Polytop (z. B. vom Klee-Minty- oder Jeroslow-Typ) konstruiert werden kann, das vom kürzesten Pfad erheblich abweicht, indem es die Auswahl einer jeweils ungünstigen Kante erzwingt. 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 normieren und skalieren wir \({b}^{T}y - {d}^{T}x \le 0, Ax \le b\) und \({A}^{T}y \ge d\). Die Höhe \(h\) habe den Startwert \({h}_{0} := |\text{min } \{{b}_{1}, ..., {b}_{m}, {-d}_{1}, ..., {-d}_{n}\}|/r\) mit dem Reduktionsfaktor \(r \in \; ]0, 1[\). 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 - {d}^{T}x \le h, Ax - b \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, d - {A}^{T}y \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}\) mit \(\underline{v} := {v}^{T}\) den zulässigen inneren Startpunkt \(v := ({\underline{x}, \underline{y}, h)}^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1}\), z. B. \(({\underline{0}, \underline{0}, {h}_{0})}^{T}\). Es identifiziert die zueinander dualen LPs max \(\{{d}^{T}x : d \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 d\}\).

Wir interpolieren nacheinander alle \({v}_{k}^{*} := (\text{max } {v}_{k} + \text{min } {v}_{k})/2\), bis alle \(|\Delta{v}_{k}|\) hinreichend klein sind. In \(\mathcal{O}(\omega\vartheta)\) extrapolieren wir dann \(v\) über \({v}^{*}\) in den Polytoprand. Das \(r\)-fache der über \({v}^{*}\) hinausgehenden Strecke legt den neuen Ausgangspunkt \(v\) fest. Folgt min\({}_{k} {h}_{k} t = 0\) aus \(t :=\) min\({}_{k} \Delta{h}_{k}\), hören wir auf. Dann beginnen wir von vorn, bis min \(h = 0\) oder min \(h > 0\) feststeht. Da sich \(h\) bei fast jedem Durchlauf in \(\mathcal{O}({\omega\vartheta}^{2})\) wenigstens halbiert, liefert der starke Dualitätssatz ([775], S. 60 - 65) die Behauptung.\(\square\)

Korollar: Ist weder ein primal zulässiges \(x\) noch eine duale Lösung \(y\) zu berechnen, lässt sich die Laufzeit des LPs max \(\{{d}^{T}x : d \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}\) mit \(h := {d}^{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}({\ell\omega}^{4,5})\) ist. Nach dem Initialisieren zusätzlicher Variablen (mit 0) ist eventuell \(h\) anzupassen. Eine Erhöhung der Rechengenauigkeit kann sinnvoll sein.

Korollar: Das LP max \(\{{||x - {x}^{o}||}_{1} : {d}^{T}x = {d}^{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: Das LP max \(\{{||x||}_{1} : Ax = \lambda x, x \in {[-1, 1]}^{n}\}\) kann einen Eigenvektor \(x \ne 0\) jeder Matrix \(A \in {}^{\omega}\mathbb{R}^{n \times n}\) mit dem Eigenwert \(\lambda \in {}^{\omega}\mathbb{R}\) in \(\mathcal{O}({\omega\vartheta}^{2})\) bestimmen.\(\square\)

Korollar: Das LP min \(\{h \in [0, 1 + \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.\(\square\)

Korollar: Sei \({\alpha }_{j}\) der \(j\)-te Spaltenvektor der Matrix \({A}^{-1} \in {}^{\omega}\mathbb{R}^{n \times n}\) und sei \({\delta}_{ij}\) das Kronecker-Delta. Jedes LGS \({A \alpha }_{j} = {({\delta}_{1j}, ..., {\delta}_{nj})}^{T}\) lässt sich zur Berechnung der Inversen \({A}^{-1}\) der regulären Matrix \(A\) für \(j = 1, ..., n\) in \(\mathcal{O}({\vartheta}^{3})\) lösen. Ob \(A\) regulär ist, lässt sich ebenfalls in \(\mathcal{O}({\vartheta}^{3})\) bestimmen.\(\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 wir Rundungsfehler auch durch Rückgriff auf die Ausgangsdaten und eine nach Klein modifizierte Kahan-Babuška-Neumaier-Summierung insbesondere gegen Ende klein halten können. Wird es für verteiltes Rechnen in \({}^{c}\mathbb{R}^{c}\) 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}^{c-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

© 2008-2018 by Boris Haase


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