Theorema Magnum MCMXLVIII: das Simplex-Verfahren

Von Thilo / 15. Oktober 2020 / 14 Kommentare / Seite 2 von 2 / Auf einer Seite lesen

Interesse an dieser Arbeit zeigte zunächst das amerikanische Militär, speziell die Luftwaffe, die militärische Einsätze optimieren wollte. Mathematischer Hintergrund dafür war die Spieltheorie, die John von Neumann und der Ökonom Oskar Morgenstern entwickelt hatten. (Ihr Buch „Theory of Games and Economic Behaviour“ war 1944 erschienen. Sie vertraten die Auffassung, dass sich die Ökonomie in Richtung einer formalen, mathematisch geprägten Wissenschaft entwickeln würde wie die Physik, die ihr in dieser Entwicklung schon einige Jahrhunderte voraus sei.) In der Spieltheorie kann die lineare Optimierung dazu verwendet werden, optimale Strategien in komplizierten Zwei-Personen-Nullsummenspielen zu berechnen. Von Neumann und Morgenstern entwickelten in diesem Zusammenhang dann auch das Simplexverfahren weiter.

Bild: https://lclub-mathematicians.blogspot.com/2011/05/george-dantzig.html

« Vorherige Seite

Seite 1 / 2

Kommentare (14)

#1 Frank Wappler
15. Oktober 2020

Thilo schrieb (15. Oktober 2020):
> […] Lösung von Problemen der Form $\text{max}_{x \in {\bf R}^n} \left\{ c^T x \mid A x \le b, x \ge 0 \right\}$ für eine gegebene Matrix $A$ und Vektoren $b$ und $c$ […]

Die (Vergleichs-)Operatoren $\le$ bzw. $\ge$ haben in dieser zitierten Problemform offenbar eine Bedeutung, die von der üblichen, den (unmittelbaren) Vergleich zweier (reeller) Zahlen symbolisierenden abweicht bzw. für $n \ge 2$ darüber hinausgeht.

Welcher Zusammenhang besteht zwischen Lösungen von Problemen der zitierten Form und Lösung von Problemen der Form $\text{max}_{x \in {\bf R}^n} \left\{ c^T x \mid x^T (A x) \le x^T b, x^T x \ge 0 \right\}$ , ebenfalls für gegebene Matrix $A$ und Vektoren $b$ und $c$ , und mit Vergleichs-Operatoren $\le$ bzw. $\ge$ in der üblichen Bedeutung ?

p.s.
> Die anschauliche Idee besteht nun darin, sich schrittweise von einer Ecke zu einer benachbarten mit besserem Zielfunktionswert zu hangeln, bis es keinen besseren Nachbarn mehr gibt. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist diese lokal optimale Ecke dann auch global optimal.

Eine anschauliche Begriffsbildung von “Konvexität” (eines Polytops mit geeigneter “Zielfunktion” bzw. “Kosten”-Struktur) besteht entsprechend wohl darin, dass sich von einer (bzw. von jeder) Anfangs-Ecke, die mindestens zwei verschiedene Nachbarecke mit besserem Zielfunktionswert hat, zu (nicht unbedingt zur Anfangs-Ecke unmittelbar benachbarten) zwei weiteren Ecken unter ständiger Verbesserung des Zielfunktionswertes (oder zumindest: ohne den Zielfunktionswert in irgendeinem Hangelschritt zu verschlechtern) hangeln lässt,
so dass, falls sich von der einen dieser beiden weiteren Ecken nicht durchgängig verbessernd (oder zumindest nie verschlechternd) zur anderen hangeln lässt,
sich von jeder dieser beiden stets noch zu (mindestens) einer vierten Ecke durchgängig verbessernd (oder zumindest nie verschlechternd) hangeln lässt.

Merkwürdig nur, dass der (bislang geprägte) Begriff der kausalen Konvexität anders (und damit wohl auch weniger anschaulich) definiert ist …
#2 Thilo
15. Oktober 2020

Es steht ja in derselben Zeile, dass die Ungleichungen komponentenweise zu verstehen sind. Durch Anwenden von x^T bekommt man offensichtlich eine schwächere Ungleichung. Bspw.ist für reelle Zahlen stets x^Tx nichtnegativ, was für die einzelnen Komponenten von x natürlich nicht immer gilt.
#3 Thilo
15. Oktober 2020

Bei kausaler Konvexität geht es einfach um Konvexität in Lorentz-Mannigfaltigkeiten. Hier, bei der linearen Optimierung, geht es um Konvexität im euklidischen R^n, der ja eine Riemannsche Mannigfaltigkeit ist.
#4 Thilo
15. Oktober 2020

Es ist tatsächlich so, dass wenn eine Ecke einen besseren Wert liefert als eine andere, es dann möglich sein muß, sich schrittweise von der schlechteren über jeweils benachbarte Ecken bis zur besseren zu bewegen und dabei in jedem Schritt das Ergebnis zu verbessern. Das ist wohl der springende Punkt in Dantzigs Beweis (den ich mir aber nicht angesehen habe).
#5 Alenx Groonwold
USA
15. Oktober 2020

Where to buy a ready-made dating site – Interested in any options
#6 Frank Wappler
15. Oktober 2020

hilo schrieb (#2, 15. Oktober 2020):
> Es steht ja in derselben Zeile, dass die Ungleichungen komponentenweise zu verstehen sind.

Oh — in meinem Browser steht das zwar nicht in der selben Zeile, aber (immerhin) im selben Satz.
Es ist wohl nur ein (insbesondere mein) Vorurteil oder eine Idealvorstellung, dass $\LateX$ -Ausdrücke hinsichtlich ihres mathematischen Inhaltes einigermaßen selbsterklärend dastünden;
wie meinetwegen $\text{max}_{x \in {\mathbb R}^n} \left\{ c^T x \mid \forall k \in \mathbb N, k \le n : (\bf e_k)^T (A x) \le (\bf e_k)^T b, (\bf e_k)^T x \ge 0, \text{ mit } (\bf e_j)^T \bf e_k = \delta^{\text{Kronecker}}_{jk}\right\}$ .

p.s.
Thilo schrieb (#3, 15. Oktober 2020):
> Hier, bei der linearen Optimierung, geht es um Konvexität im euklidischen R^n […]

Ja aber: Bei der “anschaulichen Idee [der Problemlösung]”, die im obigen ScienceBlog-Beitrag erläutert wurde und auf die ich mich im Kommentar #1 bezog, geht es offenbar um … bestimmte geordnete Teilmengen (“Hangel-Pfade”) einer durch Werte der “Zielfunktion” zumindest halb-geordneten Menge. (Zumindest halb-geordnet, weil es ja u.a. immerhin denkbar ist, dass einige bestimmte verschiedene Ecken dennoch den genau gleichen Zielfunktions-Wert haben.)

Für ganz allgemeine halb-geordnete Mengen, und insbesondere im Extremfall sogenannter “Zäune”, versagt die beschriebene “anschaulichen Idee [der Problemlösung]” jedoch “offensichtlich”.
Und damit im Zusammenhang steht die Feststellung, dass manche (insbesondere beschränkte) halb-geordnete Mengen nicht nur ein einziges “Maximum” haben, das durch “schrittweise zielführendes Hangeln” zwangsläufig erreicht würde, sondern mehrere verschiedene (lokale) Maxima, von denen höchstens eines “das globale Maximum” sein könnte.

Deshalb: Gibt es eine spezielle Bezeichnung für die Eigenschaft mancher (aber eben nicht aller) (beschränkter) halb-geordneter Mengen, genau nur ein einziges Maximum (und/oder genau nur ein einziges Minimum) zu besitzen? — Etwa: “(Halbordnungs-)Konvexität” ?

> Bei kausaler Konvexität geht es einfach um Konvexität in Lorentz-Mannigfaltigkeiten.

Bei Kausal-Beziehungen handelt es sich in erster Linie jeweils um die (kausale) Halbordnung einer Ereignismenge. Und folglich lässt sich auch dafür untersuchen, welche beschränkten Teilmengen wie viele Maxima haben. (Diese Aufgabenstellung mag übrigens im Zusammenhang mit anderen Mathlog-Beiträgen bekannt vorkommen.)

Der (bislang geprägte und im Kommentar #1 verlinkte) Begriff der “kausalen Konvexität” bezieht sich zwar ausdrücklich auf die kausale Halbordnung einer gegebenen Ereignismenge, die Anzahl “lokaler Maxima” spielt dabei aber offenbar keine Rolle.
#7 Frank Wappler
15. Oktober 2020

Frank Wappler schrieb (#6, 15. Oktober 2020):
> [T]hilo schrieb (#2, 15. Oktober 2020): […]

(Bitte um Entschuldigung für meinen Schreib- bzw. Kopierfehler im Kommentar #6.)

> Bei der “anschaulichen Idee [der Problemlösung]”, die im obigen ScienceBlog-Beitrag erläutert wurde und auf die ich mich im Kommentar #1 bezog, geht es offenbar um … bestimmte geordnete Teilmengen (“Hangel-Pfade”) einer durch Werte der “Zielfunktion” zumindest halb-geordneten Menge. (Zumindest halb-geordnet, weil es ja u.a. immerhin denkbar ist, dass einige bestimmte verschiedene Ecken dennoch den genau gleichen Zielfunktions-Wert haben.)

Eine halb-geordnete Menge ganz wesentlich auch deshalb, weil (sicherlich, im Allgemeinen) nicht jede Ecke eines Polytops (im euklidischen $\bf R^n$ ) unmittelbarer Nachbar jeder anderen Ecke des selben Polytops ist.

(Allerdings ist wohl jede Simplex-Ecke direkt zu jeder anderen benachbart. … Im obigen ScienceBlog-Artikel ging’s aber allgemein um Polyeder, und nicht ausdrücklich nur um Tetraeder, Dreiecke, oder höher-dimensionale Simplices.)
#8 Vielen Dank
16. Oktober 2020

In einem Simplex-Verfahren wird jeweils eine Zeile (A_i) des linearen Gleichungssystems A*x=b mit einer reellen Zahl multipliziert und von einer anderen Zeile (A_j) abgezogen, so dass die neue Zeile A_j := A_j – a * A_i die alte Zeile Z_j ersetzt aber eine Dimension weniger hat bzw. ein x_k=0 ist.
Wird das Verfahren m-mal angewendet, so dass die Matrix A zur Einheitsmatrix I wird, wird b zu b’ und I*x=b’ ist für x=(x_1,x_2,x_3, …) sofort lösbar. Als Nebenprodukt erhält man die inverse Matrix von A, wenn die auf A angewendeten arithmetischen Operationen auf eine neben A stehende Einheitsmatrix I angewendet werden.
Das ist so erschreckend einfach, dass auszubildende Mathematiker diesen Algorithmus spätestens nach 2 Semestern Hochschul-Mathe-Training selber finden müssen.
Tun sie aber nicht, weswegen ihnen dieses Verfahren und viele andere Verfahren von Mathe-Professoren beigebracht werden müssen.

Thilos Liste Theorema Magna ist ein schöner Beweis, dass seit Beginn des 19ten Jahrhunderts in Mathe-Hochschulen Gehirne nicht mathematisch trainiert werden, so dass Mathe-Studenten schon nach dem ersten Mathe-Semester so konditioniert sind, dass ihnen in Mathe-Klausuren Beweise über unbewiesene Vermutungen zufließen, so wie George Dantzig die Beweise der unbewiesenen Vermutungen seines Dozenten Neyman zuflossen. Das hat sich rumgesprochen, so dass außer Fluss-Talenten niemand Mathematik studieren will
(Rechnen ist Handwerk, Beweisen ist Kunst)

Im Sinne der (Linearen) Optimierung bzw. wegen demokratischer Prozessökonomiegründe dürfen deutsche Landesregierungen Steuergelder nicht verschwenderisch verprassen, indem einer minimalen Mathe-Fluss-Talent-Menge, deren Minimalität eine ökonomische Nebenbedingung (Schuldengrenze) der Simplex-Methode verletzt, Mathe-Professoren (Vorlesungskurse) und Mathe-Doktoranden (Übungskurse) langjährig viel zu teuer zur Verfügung stellen.
Aus undemokratischen Prestigegründen tun sie es trotzdem und zwingen Mediziner in den für sie sinnlosen Analysis-I-Grundkurs, um die ökonomische Nebenbedingung jährlich einzuhalten.

Vielen Dank!
#9 echt?
16. Oktober 2020

Vielen Dank für den schönen Artikel!
#10 Thilo
16. Oktober 2020

@Frank Wappler: Alles richtig und das ist auch der Grund, warum Dantzigs Satz nicht trivial ist. Er hat bewiesen, dass auf dem konvexen Polytop die lokalen Maxima auch globale Maxima sind, was tatsächlich nicht offensichtlich ist.
#11 Jan
16. Oktober 2020

@Frank Wappler(#6):
Naja, ob das wirklich selbsterklärend ist, sei mal dahingestellt (persönlich finde ich die Darstellung im Artikel oben wesentlich klarer). Aber es ist auf jeden Fall nicht äquivalent.

Zunächst einmal ist die Matrix A im allgemeinen nicht quadratisch, du brauchst also zwei Sätze von Basisvektoren.

Und die Bedingung x ≥ 0 aus dem Artikel ist nur dann äquivalent zu deiner entsprechenden Bedingung, wenn die Basisvektoren (modulo Permutation) die kanonischen Einheitsvektoren sind. Das forderst du nicht explizit, also muss der Leser davon ausgehen, dass eine beliebige Orthonormalbasis zulässig ist. Das wird noch dadurch verstärkt, dass du explizit die Bedingung anführt, dass es sich um eine Orthonormalbasis handelt; würdest du implizit davon ausgehen, dass es sich um die kanonische Orthonormalbasis handelt, wäre diese Bedingung trivialerweise erfüllt, und damit wäre es überflüssig sie anzuführen.

Analoges gilt natürlich auch für die andere Ungleichung.
#12 Frank Wappler
17. Oktober 2020

Thilo schrieb (#10, 16. Oktober 2020):
> @Frank Wappler: Alles richtig […]

Vielen Dank!
Sofern ich diese Erwiderung großzügig auslegen darf, würden wir folglich

• diese Art von Teilmengen-Konvexität (einer Teilmenge $A \subset S$ hinsichtlich der Halbordnung $\mathcal P \equiv (S, \le_{\mathcal P})$ ) :
$\qquad \forall a, b, c \in S \mid a \le_{\mathcal P} b \le_{\mathcal P} c :$
$\qquad \qquad (a, c \in A) \Rightarrow (b \in A)$
auch “relative Konvexität (der Menge $A$ bezüglich ihrer Obermenge $S$ , hinsichtlich der Halbordnung $\mathcal P$)” nennen; und dagegen

• die Eigenschaft der Halbordnung $\mathcal P \equiv (S, \le_{\mathcal P})$ :
$\qquad \qquad \forall x, y \in S :$
$\qquad \qquad \qquad \exists a, b \in S \mid (a \le_{\mathcal P} x), (a \le_{\mathcal P} y), (x \le_{\mathcal P} b), (y \le_{\mathcal P} b)$
“schwache intrinsische Konvexität (der Halbordnung $\mathcal P$, an sich)”, sowie

• die Eigenschaft der Halbordnung $\mathcal P \equiv (S, \le_{\mathcal P})$ :
$\qquad \forall x, y \in S :$
$\qquad \exists a, b \in S \mid (a \le_{\mathcal P} x), (a \le_{\mathcal P} y), (x \le_{\mathcal P} b), (y \le_{\mathcal P} b),$
$\qquad \qquad (\forall j \in S : ((j \le_{\mathcal P} x), (j \le_{\mathcal P} y)) \Rightarrow ((a \le_{\mathcal P} j) \text{ oder } (j \le_{\mathcal P} a))),$
$\qquad \qquad (\forall k \in S : ((x \le_{\mathcal P} k), (y \le_{\mathcal P} k)) \Rightarrow ((a \le_{\mathcal P} k) \text{ oder } (k \le_{\mathcal P} a)))$
“starke intrinsische Konvexität (der Halbordnung $\mathcal P$, an sich)”.

p.s.
Dass sich Deine oben zitierte Erwiederung auch auf den bislang (am 13. Oktober 2020) erreichten Stand meiner Argumentation zum Unterschied zwischen von Theorien und Modellen bezöge, wäre bestimmt eine zu großzügige Auslegung.
#13 Frank Wappler
17. Oktober 2020

Jan schrieb (#11, 16. Oktober 2020):
> @Frank Wappler(#6): Naja, ob das wirklich selbsterklärend ist, sei mal dahingestellt (persönlich finde ich die Darstellung im Artikel oben wesentlich klarer). Aber es ist auf jeden Fall nicht äquivalent.

Okay. (Das ist immerhin auch eine Antwort auf meine Frage aus #6.)

> Zunächst einmal ist die Matrix A im allgemeinen nicht quadratisch, […]

Das hatte ich zwar nicht ausdrücklich bedacht, aber das Superskript- ${}^T$ soll ja (bisweilen) wahre Wunder wirken.
#14 Theorema Magnum – Mathlog
30. April 2021

[…] Die Leray-Spektralsequenz Konditionierung linearer Gleichungssysteme Das Simplex-Verfahren Das WKS-Abtasttheorem Adelische Poisson-Summation Der Vergleichssatz von Rauch Die Berechnung des […]