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: Ein durch \(m\) Restriktionen gegebenes \(n\)-dimensionales Polytop mit \(m, n \in {}^{\omega}\mathbb{N}_{\ge2}\) hat einen Durchmesser von maximal \(2(m + n - 3)\).

Beweis: Wir können maximal \(\acute{m}\) Hyperebenen zu einem unvollständigen Zyklus (der Dimension 2) zusammenstellen und haben \(n - 2\) Ausweichmöglichkeiten zur Seite (in den restlichen Dimensionen) zu berücksichtigen. Da wir jede Teilstrecke mit maximal zwei Kanten passieren können, ergibt sich der Faktor 2. Der Satz lässt sich auf Polyeder sinngemäß übertragen, wenn wir also nur die endliche Beschränkung fallen lassen.\(\square\)

Definition: Sei \(\omega\) der angestrebte Grenzwert aller Variablen in Landau-Notation und \(\vartheta := \ell \omega\). Ein Verfahren ist polynomiell (exponentiell), wenn seine Rechenzeit in Sekunden und (oder) sein Speicherbedarf in Bits \(\mathcal{O}({\omega}^{\mathcal{O}(1)}) (\mathcal{O}({e}^{|\mathcal{O}(\omega)|}))\) ist.

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\}\). Dualisieren wir es oder setzen \(x := {x}^{+} - {x}^{-}\) mit \({x}^{+}, {x}^{-} \ge 0\), erreichen wir \(x \ge 0\). Wir lösen zuerst max \(\{-z : Ax - b \le {(z, ..., z)}^{T} \in {}^{\omega}\mathbb{R}^{m}, z \ge 0\}\), um ein zulässiges \(x\) zu erhalten, falls \(b \ge 0\) nicht gilt. Start- und Zielwert sind \(z := |\text{min } \{{b}_{1}, ..., {b}_{m}\}|\) bzw. \(z = 0\). Wie im ersten Fall starten wir mit \(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 \; ({d}_{j} = 0)\) mit \({a}_{ij} \le 0\) für alle \(i\), ist das LP positiv unbeschränkt (können wir \({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\)) können wir 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. Die Variablen mit \({}^{*}\) seien die des jeweils nächsten Schritts. Dann ist durch \({x}_{j}^{*} = {x}_{j} + {b}_{k}/{a}_{kj}\) die potentielle nächste zulässige Ecke \({x}^{*}\) gegeben. Bei Wahl der steilsten Kante ist das \({a}_{kj}\) das Pivotelement zu dem \({x}_{j}\) darunter, das \({d}^{T}\Delta x/||\Delta x||\) bzw. \({d}_{j}^{2}/(1 + ||{A}_{.j}{||}^{2})\) mit \(\Delta x := {x}^{*} - x\) in der \(k\)-ten Restriktion maximiert.

Bei mehreren Maxima können wir die Pivotregel des Bestwerts max\({}_{k,j} {d}_{j}{b}_{k}/{a}_{kj}\) oder (weniger gut) des kleinsten Winkels min \({(1, ..., 1)}^{T}d^{*}/||(\sqrt{n}) d^{*}||\) verwenden. Können wir die Zielfunktion nicht auf direktem Wege maximieren, behandeln wir die Restriktionen mit \({b}_{i} = 0\) gleich, indem wir sie um einen identischen, aber minimalen Betrag abschwächen (perturbieren). Diesen brauchen wir im Tableau selbst nicht zu notieren: Wir setzen hier 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}||\). Der Aufwand eine mehrfache Ecke verlassen zu können, wonach wir die Abschwächungen zurücknehmen, entspricht einem LP mit \(d > 0\) und \(b = 0\). Die Zielfunktion wächst auf dem zurückgelegten Weg (quasi) streng monoton. Danach können wir \({d}_{j}^{*}, {a}_{ij}^{*}\) und \({b}_{i}^{*}\) nach der Rechteckregel einfach berechnen (vgl. [775], S. 63).

Das Simplexverfahren ist im schlechtesten Fall trotz des Durchmessersatzes für Polytope unter allen Pivotregeln nicht polynomiell, da ein exponentielles "Driften" durch ein Polytop vom Klee-Minty- oder Jeroslow-Typ oder anders konstruiert werden kann, das durch Zwang zur Auswahl der jeweils ungünstigeren Kante vom kürzesten Pfad erheblich abweicht. Dies steht im Einklang mit existierenden Beweisen und es 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\) und \(v := ({{x}^{T}, {y}^{T})}^{T} \in {}^{\omega}\mathbb{R}^{m+n}\) haben die Startwerte \({h}_{0} := |\text{min } \{{b}_{1}, ..., {b}_{m}, {-d}_{1}, ..., {-d}_{n}\}|\) und 0. Wir berechnen das LP min \(\{h \in [0, {h}_{0}] : 0 \le x \in {}^{\omega}\mathbb{R}^{n}, 0 \le y \in {}^{\omega}\mathbb{R}^{m}, {b}^{T}y - {d}^{T}x \le h, Ax - b \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}^{m}, d - {A}^{T}y \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}^{n}\}\) über das (duale) Programm min \(\{{b}^{T}y : 0 \le y \in {}^{\omega}\mathbb{R}^{m}, {A}^{T}y \ge d\}\) zu dem (primalen) Programm max \(\{{d}^{T}x : d \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}\).

Wir interpolieren nacheinander alle \({v}_{k}^{*} := (\text{max } {v}_{k} + \text{min } {v}_{k})/2\) (wenige Male) und extra- bzw. interpolieren eventuell \({v}^{*}\) aus \(v\). Wir ermitteln die Richtung \(u \in {}^{\omega}\mathbb{R}^{m+n}\) nach Lösen aller LPs min \({h}_{k}\) in \({h}_{k}, {v}_{k} \in {}^{\omega}\mathbb{R}_{\ge 0}\) mit \({u}_{k} := \Delta {v}_{k} \Delta {h}_{k}/\text{min} \; \Delta {h}_{k}\). Wir lösen min \(h\) in \(h, s \in {}^{\omega}\mathbb{R}_{\ge 0}\) mit \({v}^{*} := v + su\) und festem \(v\). Das Bisektionsverfahren löst die zweidimensionalen LPs in \(\mathcal{O}({\vartheta}^{2})\). Nach erneuter Interpolation extrapolieren wir in \(\mathcal{O}(\omega\vartheta) \; ({{v}^{T}, h)}^{T}\) durch \({({v}^{*T}, {h}^{*})}^{T}\) in den Rand des Polytops.

Eventuell starten wir mit \(v \ne 0\) oder verzichten auf die zweidimensionalen LPs. Sind \(x\) und \(y\) optimal oder lässt sich \(h\) nicht weiter minimieren, stoppen wir das Verfahren. Können wir \(v\) nicht verlassen, schwächen wir alle Restriktionen außer \(v \ge 0\) ein wenig ab und machen dies am Ende eines Durchlaufs rückgängig. Da \(\Delta h\) bei jedem Durchlauf in \(\mathcal{O}({\omega\vartheta}^{2})\) ungefähr die Hälfte von \(h\) ist, folgt aus dem starken Dualitätssatz ([775], S. 60 - 65) die Behauptung.\(\square\)

Bemerkungen: Simplexverfahren und Face-Algorithmus ([916], S. 580 f.) lösen das LP für kleine \(m\) und \(n\) eventuell schneller. Wir können den aktuellen Bestand der Restriktionen bzw. Variablen 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. Wir haben lediglich eventuell \(h\) anzupassen, da wir zusätzliche Variable mit 0 initialisieren können.

Korollar: Jedes lösbare lineare Gleichungssystem (LGS) \(Ax = b\) mit \(x \in {}^{\omega}\mathbb{R}^{n}\) lässt sich als LP min \(\{h \in [0, \text{max } \{|{b}_{1}|, ..., |{b}_{m}|\}] : \pm(Ax - b) \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}^{m}\}\) in \(\mathcal{O}({\vartheta}^{3})\) lösen.\(\square\)

Korollar: Jedes lösbare LP min \(\{h \in [0, 1] : \pm(Ax - \lambda x) \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}^{n}\}\) kann einen Eigenvektor \(x \in {}^{\omega}\mathbb{R}^{n} \setminus \{0\}\) der Matrix \(A \in {}^{\omega}\mathbb{R}^{n \times n}\) zum Eigenwert \(\lambda \in {}^{\omega}\mathbb{R}\) 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}\) zur Bestimmung der Inversen \({A}^{-1}\) der regulären Matrix \(A\) lässt sich 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: Werden ausschließlich endliche Fließkommazahlen verwendet und ist \(q \in [0, 1]\) die Dichte von \(A\), gilt oben überall max \(\{\mathcal{O}(qmn), \mathcal{O}(m + n)\}\) bzw. max \(\{\mathcal{O}(q{n}^{2}), \mathcal{O}(n)\}\) statt \(\mathcal{O}({\vartheta}^{3}).\square\)

Bemerkungen: Die vier Korollare lassen sich leicht ins Komplexe überführen. Das Intexverfahren ist numerisch sehr stabil, da wir die Ausgangsdaten nur wenig ändern. Besonderer Sorgfalt in numerischer Hinsicht bedarf jedoch sein sich stark verringernder zulässiger Bereich. Es lässt sich im \({}^{c}\mathbb{R}^{c}\) modifiziert durch verteiltes Rechnen in \(\mathcal{O}(1)\) lösen. 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\) (s. [939], S. 589 ff.).\(\square\)

Programmtext des Simplexverfahrens

© 2008-2018 by Boris Haase


Valid XHTML 1.0 • Haftungsausschluss • mail@boris-haase.de • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • Seitenbeginn