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\) 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}({\vartheta}^3)\).

Beweis und Algorithmus: Sei \(z := n + m\) und \(d \in [0, 1]\) die Dichte von \(A\). Zuerst werden \({b}^{T}y – {c}^{T}x \le 0, Ax \le b\) sowie \({A}^{T}y \ge c\) normiert und skaliert. \(P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {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\}\) habe den Radius \(\check{r} := s|\min \; \{b_1, …, b_m, -c_1, …, -c_n\}|\) mit dem Skalierungsfaktor \(s \in [1, 2]\). 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\).

Startpunkt sei \(\underline{0}_{z} \in \partial P_{\check{r}}\). Mit \(p_k^* := (\text{min}\,p_k + \text{max}\,p_k)/2\) für \(k = 1, …, \grave{z}\) wird \(g\) durch \(p_0 := (x_0, y_0, r_0)^T\) approximiert, bis \(||\Delta p||_1\) hinreichend klein ist. Die Lösung \(p_0\) wird \(p_0 + q\) geschrieben und das LP in \(q \in {}^{\omega}\mathbb{R}^{\grave{z}}\) usf. gelöst, bis ggf. \(g \in P_0\) in \(\mathcal{O}(d({}_2\check{r})^2mn)\) berechnet ist. Eine Extrapolation in \(\partial P_{\check{r}}\) bestimmt den nächsten Punkt aus dem vorhergehenden. Folgt \(\text{min}_k \Delta r_k r = 0\), wird aufgehört, andernfalls wiederholt bis min \(r = 0\) oder min \(r > 0\) feststeht. Zahlen der Länge \(\mathcal{O}({\omega})\) lassen sich bekanntlich nur in \(\mathcal{O}(\vartheta)\) abarbeiten.\(\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 \(r := {c}^{T}x\) ungefähr halbieren.

Bemerkungen: Simplexverfahren und Face-Algorithmus3Pan, Ping-Qi: Linear Programming Computation; 1st Ed.; 2014; Springer; New York, 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 Zentrumsverfahren Restriktionen nicht transformiert und schneller als alle bekannten (Worst-Case-)LP-Algorithmen in \(\mathcal{O}(\omega^{37/18}\vartheta)\) ist. Seine Implementierungsdetails werden erst veröffentlicht, wenn kein Missbrauch für intransparente oder schlechte Entscheidungen zu befürchten ist.

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 Natur4vgl. 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}({\vartheta}^3)\) 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}({\vartheta}^3)\) 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}({\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\)

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}({\vartheta}^3)\) lösen sowie die Matrizenmultiplikation durch Parallelisierung in \(\mathcal{O}({\vartheta}^2)\) 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\) existiert5vgl. 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 Pan, Ping-Qi: Linear Programming Computation; 1st Ed.; 2014; Springer; New York, S. 580 f.
4 vgl. Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton
5 vgl. Bertsekas, Dimitri P.: Nonlinear Programming; 3rd Ed.; 2016; Athena Scientific; Belmont, S. 589 ff.