| |
| Autor |
  Motivation für Dualität in der Optimierung? |
|
Pter87
Aktiv 
Dabei seit: 09.11.2018
Mitteilungen: 430
 |  Themenstart: 2022-01-25
|
Ich besuche zurzeit eine Einführung in die Optimierung wo es größtenteils um Konvexe Mengen und Funktionen, Polyeder, den Simplex-Algorithmus und Dualitätstheoreme geht.
Welche Gründe gibt es, sich mit Dualität zu beschäftigen? Inwiefern ist es hilfreich eine solche Art von Umformulierung seines linearen Problems zu haben?
In dem Buch welches ich zurzeit für die lineare Optimierung benutze, wird erwähnt, dass das duale Problem für praktische Zwecke sehr sinnvoll ist, da z.B. ein lineares Problem mit sehr vielen Ungleichungen aber wenig Variablen eher in dualer Form gelöst werden sollte, da die Anzahl von Iterationen vom Simplex-Algorithmus viel mehr von der Anzahl an Restriktionen abhängt, als von der Anzahl der Variablen.
|
 Profil
|
Goswin
Senior 
Dabei seit: 18.09.2008
Mitteilungen: 1794
Wohnort: Chile, Ulm
 | Beitrag No.1, eingetragen 2022-01-27
|
\quoteon(2022-01-25 19:16 - Pter87 im Themenstart)
Welche Gründe gibt es, sich mit Dualität zu beschäftigen? Inwiefern ist es hilfreich eine solche Art von Umformulierung seines linearen Problems zu haben?
\quoteoff
Eine duale Umformulierung ist wohl nur wichtig, um duale (und primal-dual gemischte) Algorithmen besser zu verstehen.
\quoteon(2022-01-25 19:16 - Pter87 im Themenstart)
... da die Anzahl von Iterationen vom Simplex-Algorithmus viel mehr von der Anzahl an Restriktionen abhängt, als von der Anzahl der Variablen.
\quoteoff
Das sehe ich (bei zufallsverteilten Daten) auch so, und es gibt dafür sogar einen (für mich) plausiblen Grund: wenn wir \(n\) Variablen und \(m\) Ungleichungen haben, dann ist die Anzahl der Daten, die in einem Einzelschritt untersucht werden, beim standardmäßigen primalen Simplex-Algorithmus \(2n+m\) und beim dualen \(n+2m\).
Aber in der Praxis dürfte es mit \(n\!\gg\! m\) vermutlich wichtiger sein, ob wir eine zulässige Lösung bereits kennen oder nicht.
Und es geht ja auch darum, wie schnell ein Iterationsschritt gemacht wird. Für die Faktorisierung der Basis sollte dann diese möglichst kleindimensional gewählt werden, also vorzugsweise \(\min(n,m)\times\min(n,m)\).
|
Profil
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 2426
 | Beitrag No.2, eingetragen 2022-01-28
|
Hallo Pter87!
Meine Erfahrungen mit Linearer Optimierung liegen schon etwas zurück.
Ich glaube aber bei bestimmten Verfahren ist mal das normale Problem und mal das duale Problem deutlich besser lösbar.
Z.B. Klee Minty bereitet dem Simplexverfahren Probleme.
Andere Verfahren (siehe Vanderbei) lösen dieses Beispiel deutlich schneller.
Siehe mein Matheplanet-Artikel über Lineare Optimierung mit Java:
https://www.matheplanet.de/matheplanet/nuke/html/article.php?sid=1898
(dort Probleme 12 bis 16).
Viele Grüße
Ronald
|
Profil
|
Pter87 hat die Antworten auf ihre/seine Frage gesehen.
Pter87 hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
