Home » Mathematik » Lineare Optimierung

Lineare Optimierung

Lineare Optimierung
Lineare Optimierung

Das Folgende setzt Mengenlehre, Topologie und Nichtstandardanalysis voraus. Das Simplex- und das Zentrumsverfahren können ein LP meist in kubischer bzw. quadratischer Zeit lösen.

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 Simplexverfahren1Dantzig, George B.: Lineare Programmierung und Erweiterungen; 1. Aufl.; 1966; Springer; Berlin. ist im schlechtesten Fall 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 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\) ist ggf. zu wiederholen und am Ende rückgängig zu machen. Restriktionen mit \({a}_{i} \le 0\) werden ggf. entfernt.

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}^{*}\).

Wiederholt sich \(c^Tx^* = c^Tx\), werden die Restriktionen mit \({b}_{i} = 0\) um ein \(d \in {}^{\omega}\mathbb{R}_{>0}\) abgeschwächt (also perturbiert). Mit \({b}_{i} := ||{a}_{i}||\) steht \(d\) ggf. nicht im Tableau. Liegt eine mehrfache Ecke ausnahmsweise erneut vor, wird zu jedem \({b}_{i}\) einfach \(||{a}_{i}||\) addiert. Sie zu verlassen kann das Lösen eines LPs mit \(c > 0\) und \(b = 0\) erfordern. Danach werden die Abschwächungen zurückgenommen.

Die Rechteckregel erlaubt \({c}_{j}^{*}, {a}_{ij}^{*}\) und \({b}_{i}^{*}\) einfach zu berechnen2vgl. Vanderbei, Robert J.: Linear Programming; 3rd Ed.; 2008; Springer; New York, S. 63.. Keine Pivotregel kann die evtl. exponentielle Laufzeit verhindern, trotz des Durchmessersatzes für Polytope: Sind diese z. B. vom Klee-Minty- oder Jeroslow-Typ, kann es ein exponentielles „Driften“ mit Auswahl einer jeweils ungünstigen Kante geben. 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: Sei \(z := \grave{m} + n\) 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\}|\) und den Skalierungsfaktor \(s \in [1, 2]\). Es folgt \(\underline{0}_{z} \in \partial P_{\check{r}}\). Nach dem starken Dualitätssatz3a. a. O., S. 60 – 65. löst das LP min \(\{ r \in [0, \check{r}] : (x, y)^T \in P_r\}\) ebenso 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_0\). 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 \(t^o(x^o, y^o, r^o)^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{\grave{z}}\). Dies wird mit \(t^o(x^o, y^o)^T\) wiederholt, bis ggf. \(g \in P_0\) in \(\mathcal{O}({}_z\check{r} {}_e\check{r}dmn)\) berechnet ist. Zahlen der Länge \(\mathcal{O}({\omega})\) lassen sich bekanntlich nur in \(\mathcal{O}(\vartheta)\) abarbeiten.

Das Lösen aller zweidimensionalen LPs \(\text{min}_k r_k\) durch Bisektionsverfahren für \(r_k \in {}^{\omega}\mathbb{R}_{\ge 0}\) und \(k = 1, …, z\) in jeweils \(\mathcal{O}({\vartheta}^2)\) ermittelt \(q \in {}^{\omega}\mathbb{R}^k\) mit \(q_k := \Delta p_k \Delta r_k/r\) und \(r := \text{min}_k \Delta r_k\). Vereinfacht sei \(|\Delta p_1| = … = |\Delta p_{z}|\). Hierbei wäre min \(r_{\grave{z}}\) für \(p^* := p + wq\) mit \(w \in {}^{\omega}\mathbb{R}_{\ge 0}\) ebenso zu lösen. Folgt \(\text{min}_k \Delta r_k r = 0\), wird aufgehört, andernfalls wiederholt bis min \(r = 0\) oder min \(r > 0\) feststeht. Falls erforderlich werden die Restriktionen vorübergehend um einen gleichen kleinen Betrag abgeschwächt.\(\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-Algorithmus4Pan, 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 dauerhaft 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: Das Zentrumsverfahren macht sich zunutze, dass der berechnete geometrische Schwerpunkt und der Inkugelmittelpunkt in \(P_0\) zusammenfallen. Ersterer lässt sich durch (paarweises) Drehen der Koordinatenachsen mithilfe einer einfachen Rotationsmatrix in vergleichbarer Laufzeit absichern. Eventuell ist dazu deren Anzahl auf eine gerade Zahl zu erhöhen. Es ist von Vorteil, dass sich die Berechnungen natürlich auch unabhängig von einer Optimierungsfragestellung durchführen lassen.

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

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

© 2008-2021 by Boris Haase

Seitenbeginn

Literatur

Literatur
1 Dantzig, George B.: Lineare Programmierung und Erweiterungen; 1. Aufl.; 1966; Springer; Berlin.
2 vgl. Vanderbei, Robert J.: Linear Programming; 3rd Ed.; 2008; Springer; New York, S. 63.
3 a. a. O., S. 60 – 65.
4 Pan, Ping-Qi: Linear Programming Computation; 1st Ed.; 2014; Springer; New York, S. 580 f.
5 Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton.
6 vgl. Bertsekas, Dimitri P.: Nonlinear Programming; 3rd Ed.; 2016; Athena Scientific; Belmont, S. 589 ff.