Lineare Optimierung

Lineare Optimierung
Lineare Optimierung

Das Folgende setzt Mengenlehre, Topologie und Nichtstandardanalysis voraus. Das exponentielle Simplex- und das polynomielle Zentrumsverfahren 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 \(\acute{m}\) 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 := \omega\,{}_{e}\omega, \underline{u}_n := (u, …, u)^T \in{}^{\omega}\mathbb{R}^{n}\) und \({|| \cdot ||}_{1}\) die 1-Norm. Geht \(x \in X \subseteq {}^{\omega}\mathbb{R}^{\omega}\) in den nächsten Schritt über, folgt ihm \({}^{*}\) 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 erzielt \({x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}\). Mit \(x := {x}^{+} – {x}^{-}\) für \({x}^{+}, {x}^{-} \ge 0\) wird \({x}^{*} \in {}^{\omega}\mathbb{R}_{\ge 0}^{2n}\) erreicht. Gilt nicht \(b \ge 0\), liefert das LP max \(\{-h \in {}^{\omega}\mathbb{R}_{\le 0} : Ax – b \le \underline{h}_n\}\) für den Startpunkt \(x_0 := 0\) ein \(x \in {P}_{\ge 0}\). Start- und Zielwert von \(h\) sei \(|\text{min } \{{b}_{1}, …, {b}_{m}\}|\) bzw. 0. Nur ein 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 min \(\{{b}_{k}/{a}_{kj} : {a}_{ij} > 0\}\) für jedes \({c}_{j} > 0\) sowie Nichtbasisvariablen \({x}_{j}\) liefert durch \({x}_{j}^{*} = {x}_{j} + {b}_{k}/{a}_{kj}\) ein nächstes \({x}^{*} \in P_{\ge 0}\). Bei Wahl der steilsten Kante bildet \({a}_{kj}\) das Pivotelement zu dem \({x}_{j}\), das \({c}^{T}{_1}{\Delta x}\) bzw. \({c}_{j}^{2}/\grave{v}_{j}^{2}\) mit \(v_j := ||{A}_{.j}||\) in der \(k\)-ten Restriktion maximiert. Mehrere Maxima erlauben die Pivotregel des Bestwerts max\({}_{k,j} {c}_{j}{b}_{k}/{a}_{kj}\) zu verwenden oder (langsamer) des kleinsten Winkels min \({{_{(1)}}\underline{1}^{T}_n}{_1}{c}^{*}\). Gilt stets \(c^Tx^* = c^Tx\), werden die Restriktionen mit \({b}_{i} = 0\) gleichbehandelt.

Sie werden um den gleichen minimalen Betrag abgeschwächt (also perturbiert). Mit \({b}_{i} := ||{a}_{i}||\) braucht er nicht im Tableau zu stehen. Tritt erneut der wenig wahrscheinliche Fall einer mehrfachen Ecke ein, werden die \({b}_{i}\) von eben einfach um \(||{a}_{i}||\) erhöht. Das Verlassen einer solchen kann das Lösen eines LPs mit \(c > 0\) und \(b = 0\) erfordern. Danach werden die Abschwächungen zurückgenommen. 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 1Vanderbei, Robert J.: Linear Programming; 3rd Ed.; 2008; Springer; New York, S. 63. Keine Pivotregel macht das Simplexverfahren im schlechtesten Fall polynomiell, trotz des Durchmessersatzes für Polytope: Sind diese z. B. vom Klee-Minty- oder Jeroslow-Typ, kann ein exponentielles „Driften“ mit Auswahl einer jeweils ungünstigen Kante für eine erhebliche Abweichung vom kürzesten Pfad sorgen. In Übereinstimmung mit dem Forschungsstand folgt die Behauptung.\(\square\)

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

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. Sei \(d \in [0, 1]\) die Dichte von \(A\) und \(P_r := \{(x, y)^T : x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}, y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m},{b}^{T}y – {c}^{T}x \le r \in [0, \check{r}], Ax – b \le \underline{r}_m, c – {A}^{T}y \le \underline{r}_n\}\) mit dem Radius \(\check{r} := s|\min \; \{b_1, …, b_m, -c_1, …, -c_n\}|\) und dem Skalierungsfaktor \(s \in [1, 2]\). Für die Zahl \(z := \grave{m} + n\) folgt \(\underline{0}_{\acute{z}} \in \partial P_{\check{r}}\). Nach dem starken Dualitätssatz2a.a.O., S. 60 – 65 löst das LP min \(\{r \in [0, \check{r}] : (x, y)^T \in P_r\}\) die 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\}\).

Seine Lösung ist der geometrische Schwerpunkt \(g\) des Polytops \(P_r\). Mit \(p_k^* := (\text{min}\,p_k + \text{max}\,p_k)/2\) für \(k = 1, …, z\) wird \(g\) durch \(p_0 := (x_0, y_0, r_0)^T\) approximiert, bis \(||\Delta p||_1\) hinreichend klein ist. Die Lösung \(t^o(x_1, y_1, r_1)^T\) des zweidimensionalen LPs min \(\{r \in [0, \check{r}] : t \in {}^{\omega}\mathbb{R}_{> 0}, t(x_0, y_0)^T \in P_r\}\) approximiert \(g\) besser und erreicht \(r \le \check{r}/\sqrt{z}\). Dies wird mit \(t^o(x_1, y_1)^T\) wiederholt, bis ggf. \(g \in P_0\) in \(\mathcal{O}({}_z\check{r} {}_e\check{r}dmn)\) berechnet ist. Schließlich lassen sich Zahlen der Länge \(\mathcal{O}({\omega})\) nur in \(\mathcal{O}(\vartheta)\) abarbeiten.\(\square\)

Bemerkungen: Wird das Zentrumsverfahren für verteiltes Rechnen in \({}^{\nu}\mathbb{R}^{\nu}\) optimiert, beträgt seine Laufzeit nur \(\mathcal{O}(1)\). Werden nach Lösen des stetigen Problems einige \(p_k\) durch \(\lfloor p_k \rfloor\) bzw. \(\lceil p_k \rceil\) ersetzt, bewährt es sich gut für (gemischt-)ganzzahlige Probleme und die (nicht-)konvexe (Pareto-)Optimierung (nach der Natur3vgl. Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton). Rundungsfehler sind durch eine nach Klein modifizierte Kahan-Babuška-Neumaier-Summierung klein zu halten. Die Überführung ins Komplexe ist einfach. All dies gilt auch für das Folgende.

Folgerung: 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\)

Folgerung: Das LP max \(\{\nu|\lambda_j| + ||x_j||_1: Ax_j = \lambda_j x_j, |\lambda_j| \in [0, r_j], x_j \in {[-1, 1]}^{n*}\}\) kann für jedes \(j = 1, …, n\) den Eigenwert \(\lambda_j \in {}^{\omega}\mathbb{R}\) und den Eigenvektor \(x_j \in {}^{\omega}\mathbb{R}^{n}\) der Matrix \(A \in {}^{\omega}\mathbb{R}^{n \times n}\) in \(\mathcal{O}(\omega{\vartheta}^2)\) bestimmen.\(\square\)

Folgerung: Das LP min \(\{r \in [0, s \, \text{max } \{|{b}_{1}|, …, |{b}_{m}|\}] : \pm(Ax – b) \le \underline{r}_m\}\) kann ein \(x \in {}^{\omega}\mathbb{R}^{n}\) jedes lösbaren linearen Gleichungssystems (LGS) \(Ax = b\) in \(\mathcal{O}(\omega{\vartheta}^2)\) 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\)

Folgerung: 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}(\omega{\vartheta}^2)\) lösen sowie die Matrizenmultiplikation durch Parallelisierung in \(\mathcal{O}(\omega{\vartheta})\) ausführen.\(\square\)

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 Zentrums- 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\) existiert4vgl. Bertsekas, Dimitri P.: Nonlinear Programming; 3rd Ed.; 2016; Athena Scientific; Belmont, S. 589 ff. mit\({f}_{i}(x) < 0\) für alle \(i > 1).\square\)

Bitte nachfolgend lineares Programm eingeben (Trennzeichen Leerzeichen, letzte Zeile Zielfunktion, erste Spalte rechte Seiten wie im Beispiel): Es kommt nicht auf die Anzahl der korrekten Dezimalstellen an, sondern auf die Zeitkomplexität und die Anzahl der Schritte des Simplexverfahrens!

© 2008-2020 by Boris Haase

Seitenbeginn

Literatur

Literatur
1 Vanderbei, Robert J.: Linear Programming; 3rd Ed.; 2008; Springer; New York, S. 63
2 a.a.O., S. 60 – 65
3 vgl. Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton
4 vgl. Bertsekas, Dimitri P.: Nonlinear Programming; 3rd Ed.; 2016; Athena Scientific; Belmont, S. 589 ff.