Home » Mathematik » Lineare Optimierung

Lineare Optimierung

Lineare Optimierung
Lineare Optimierung

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

Durchmessersatz für Polytope: Jeder 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, überträgt sich der Satz sinngemäß auf Polyeder.

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 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}\). Ein (großes) \(x^+ \in {}^{\omega}\mathbb{R}_{\geq0}\) erreicht \(x^* \in {}^{\omega}\mathbb{R}_{\geq 0}^n\) mit \(x := x^* – {\underline{x}}_n^+\). Gilt \(b \ge 0\) nicht, 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 \({b_k}/{a}_{kj} :=\) min \(\{{b_i}/{a}_{ij} : {a}_{ij} > 0\}\) für jedes \({c}_{j} > 0\) sowie Nichtbasisvariablen \({x}_{j}\) liefert mit \({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.

Diese Aufgabe kann sich auch am Ende stellen, wenn weitere Lösungen des LPs zu bestimmen und mindestens zwei \(c_j = 0\) sind. So wird vermieden, mit mehreren sich stark unterscheidenden, aber nicht nach Optimalitätsgesichtspunkten ausgewählten minimalen Abschwächungen rechnen zu müssen wie bei der lexikographischen Methode. Auch die Regel von Bland ist nicht optimal.

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

Bemerkungen: Der folgende schnelle und numerisch einfache Algorithmus könnte äußerst wichtig sein. Er wurde in 35 Jahren entwickelt und beantwortet (z. B. mithilfe von Gomory-Schnitten) Hilberts zehntes Problem positiv. Das Simplexverfahren erlaubt aber bei entsprechend gestellten kleineren Ausgangsproblemen einfache und genaue Rechnungen mit rationalen Zahlen (bei geeignet genäherten \(||{a}_{i}||\)).

Satz: Das Intexverfahren löst jedes lösbare LP mit Inter-/Extrapolationen in \(\mathcal{O}({\vartheta}^3)\).

Beweis und Algorithmus: Sei \(z := 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, \breve{r}], Ax – b \le \underline{r}_m, c – {A}^{T}y \le \underline{r}_n\}\) habe den Radius \(\breve{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_{\breve{r}}\). Nach dem starken Dualitätssatz3a. a. O., S. 60 – 65. löst das LP min \(\{ r \in [0, \breve{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}\,\check{p}_k + \text{max}\,\check{p}_k\) 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, \breve{r}] : t \in {}^{\omega}\mathbb{R}_{> 0}, t(x_0, y_0)^T \in P_r\}\) approximiert \(g\) besser und erreicht \(r \le \hat{2}\breve{r}\). Dies wird mit \(t^o(x^o, y^o)^T\) wiederholt, bis ggf. \(g \in P_0\) in \(\mathcal{O}({}_2\breve{r}^2dmn)\) berechnet ist.

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 die Berechnung gestoppt, andernfalls wiederholt bis min \(r = 0\) oder min \(r > 0\) feststeht.\(\square\)

Bemerkungen: Zahlen der Länge \(\mathcal{O}({\omega})\) lassen sich bekanntlich nur in \(\mathcal{O}(\vartheta)\) abarbeiten. Das Intexverfahren macht sich zunutze, dass der berechnete geometrische Schwerpunkt und der Inkugelmittelpunkt in \(P_0\) zusammenfallen. Das (paarweise) Drehen der Koordinatenachsen des ersteren wie von \(c\) mithilfe einer einfachen Rotationsmatrix sichert dies in vergleichbarer Laufzeit ab. Falls erforderlich schwächt ein gleicher kleiner Betrag die Restriktionen vorübergehend ab.

Bemerkungen: Absichtliche Rundungsfehler in \(b\) und \(c\) machen jede Lösung eindeutig. Das Intexverfahren hat für endliche \(m\) und \(n\) eine Laufzeit von \(\mathcal{O}(dmn)\). Wird es für verteiltes Rechnen in \({}^{\nu}\mathbb{R}^{\nu}\) optimiert, beträgt sie nur \(\mathcal{O}(1)\). Gilt \(\acute{v}_0 \le \lfloor v_j \rfloor – v_j\) für ganzzahlige Lösungen \(v_j\), bewährt es sich gut für (gemischt-) ganzzahlige Probleme und die (nicht-)konvexe (Pareto-)Optimierung (nach der Natur4Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton.).

Bemerkungen: Simplexverfahren und Face-Algorithmus5Pan, Ping-Qi: Linear Programming Computation; 1st Ed.; 2014; Springer; New York, S. 580 f. lösen LPs für kleine \(m\) und \(n\) schneller. Intexverfahren übertreffen die bekannten (Worst-Case-)LP-Algorithmen in \(\mathcal{O}(\omega^{37/18}\vartheta)\). Ist kein Missbrauch für intransparente oder schlechte Entscheidungen zu befürchten, werden Implementierungsdetails veröffentlicht. Die Überführung ins Komplexe ist einfach, auch für die folgenden Ergebnisse.

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}^2\vartheta)\) 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}^2\vartheta)\) bestimmen.\(\square\)

Folgerung: Die LPs max \(\{{x}_{j} : Ax = 0\}\) liefern alle Lösungen von \(Ax = b\) in \(\mathcal{O}({\omega}^2\vartheta)\). 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 \({A \alpha }_{j} = {({\delta}_{1j}, …, {\delta}_{nj})}^{T}\) in \(\mathcal{O}({\omega}^2\vartheta)\) lösen.\(\square\)

Korollar: Intex- und zweidimensionale Bisektions- oder Newtonverfahren lösen 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\) in polynomieller Laufzeit, 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\)

Korollar: Das LP max \(\{x : y_{\acute{m}} – xy_m = b_{\acute{m}}, y_n = y_0 = 0, x \le x_0 \in {}^{\omega}\mathbb{R}\}\) kann für \(m = 1, …, n\) nach dem Horner-Schema ein \(b_{\acute{n}}x^{\acute{n}} + … + b_1x + b_0 = 0\) lösendes \(x \in {}^{\omega}\mathbb{R}\) in \(\mathcal{O}(\omega\vartheta)\) bestimmen und abbrechende TRn erlauben jedes stetige Ungleichungssystem mit konvexer Lösungsmenge analog zu lösen.\(\square\)

© 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 Vasuki, A: Nature-Inspired Optimization Algorithms; 1st Ed.; 2020; CRC Press; Boca Raton.
5 Pan, Ping-Qi: Linear Programming Computation; 1st Ed.; 2014; Springer; New York, S. 580 f.
6 vgl. Bertsekas, Dimitri P.: Nonlinear Programming; 3rd Ed.; 2016; Athena Scientific; Belmont, S. 589 ff.