Diskussion:Optimierungsproblem

Der grundsätzliche Aufbau

Ein Optimierungsproblem in "Suchprobleme", "eigentliche Optimierungsproblem", ... zu unterteilen ist sehr ungewöhnlich und entspricht nicht der gängigen Literatur/Handhabung in Lehre und Forschung. Ich hätte hier einen Artikel erwartet, der die grundlegenden Komponenten eines Optimierungsproblems definiert (Zielfunktion, (Entscheidungs-)Variablen, zulässige Menge/Restriktionen/Nebenbedingungen), ein Beispiel inkl. Bild präsentiert und die Links zu weiterführenden Themen präsentiert. Die Unterteilung in kontinuierlich/diskret erscheint ebenfalls willkürlich. Warum nicht in stochastisch/deterministisch, unendlichdimensional/endlichdimensional, linear/nichtlinear, ...? Außerdem wird das momentan wichtigste Gebiet der gemischt-ganzzahligen Optimierung (mixed-integer program) komplett unterschlagen, zu dem es auch noch keinen eigenen Artikel gibt. Ich werde hier in den nächsten Tagen einen Vorschlag für eine neue Struktur präsentieren. -- BumbleMath

Mein Vorschlag für eine neue Struktur ist da. Feedback welcome. -- BumbleMath

Die neue Definition ist mMn bereits zu speziell. Als Laie würde ich mich hier fragen, warum man zwei Mengen M und V definiert, statt sich von vornherein auf die zulässigen Lösungen zu beschränken. Und ich verstehe nicht, warum eine bestimmte Lösung aus V zur Problemdefinition gehören muss (der „Vektor von Entscheidungsvariablen $x\in V$“). Außerdem muss V im Allgemeinen kein Vektorraum sein.--Megatherium (Diskussion) 17:20, 6. Dez. 2023 (CET)

Danke für die Anmerkung. Die neue Definition ist nicht speziell, sondern so allgemein, dass sich alle Ausprägungen eines Optimierungsproblems damit beschreiben lassen. $V$ ist keine Menge, sondern ein Vektorraum, welcher die zugrundliegende algebraische Struktur beschreibt, in welcher die Menge $M$ lebt. Kann man gedanklich durch $\mathbb {R} ^{n}$ ersetzen, aber es KANN eben auch etwas viel allgemeineres wie ein Funktionenraum in der Variationsrechnung sein. $M$ ist die zulässige Menge, welche je nach Fall funktional durch Ungleichungen und Gleichungen beschrieben werden kann. Allein das ist eine Kunst für sich, die unter OptimierungsMODELL beschrieben werden sollte, um den Modellierungsaspekt zu stärken. Die Unterscheidung ist also wichtig. Die Definition der Entscheidungsvariablen ist ein essentieller Teil der Definition eines Optimierungsproblems und muss deshalb enthalten sein. --BumbleMath (Diskussion) 08:15, 8. Dez. 2023 (CET)

Ich habe jetzt noch ein konkretes Beispiel für einen Vektorraum angegeben, sodass das V bei Bedarf gedanklich zum Beispiel durch den R^n ersetzt werden kann. --BumbleMath (Diskussion) 18:03, 8. Dez. 2023 (CET)

Ich verstehe noch immer nicht, warum die Menge der Lösungen ein Vektorraum sein muss und was die Entscheidungsvariablen sollen. Für mich sieht die allgemeine Definition eines Optimierungsproblems so aus:

Gegeben ist eine Menge G von Lösungen und eine Zielfunktion $f:G\rightarrow \mathbb {R}$, und gesucht ist ein $x\in G$ mit dem kleinstmöglichen $f(x)$.

Beispiel: Problem des Handlungsreisenden: gesucht eine möglichst kurze Rundreise durch n Städte. Man kann G naheliegenderweise als Menge der Permutationen von n Elementen definieren, und das ist kein Vektorraum. Nebenbedingungen, die eine eingeschränkte Menge von zulässigen Lösungen $M\subseteq G$ definieren würden, muss es auch nicht zwingend geben. Und wozu werden hier diese Entscheidungsvariablen gebraucht? --Megatherium (Diskussion) 17:25, 12. Dez. 2023 (CET)

Hallo Megatherium, danke für deine Nachricht und die Nennung des konkreten Beispiels. Ich glaube zu verstehen, was du meinst. Ich unterteile meine Antwort in drei Punkte (Entscheidungsvariablen, Vektorraum, TSP):

1. Das Wort "Entscheidungsvariable" hat sich etabliert, da "Variable" bereits mehrfach belegt in anderen Disziplinen auftaucht. Er bezeichnet in deinem Beispiel einfach das $x$, wobei $x$ je nach Kontext alles Mögliche sein kann (ein Vektor, eine Funktion, ...). Der Kontext wird über den Vektorraum $V$ definiert, aber dazu später mehr. Das $x$ heißt also Entscheidungsvariable und informiert den Nutzer darüber, dass dies die Variable ist, für welche wir die optimale Belegung suchen, nämlich eine, die zulässig ist und $f(x)$ minimiert.
2. Die Menge der Lösungen selbst muss kein Vektorraum sein. Das hatte ich bereits oben geschrieben. Die zulässige Menge $M$, welche alle zulässigen $x$ enthält, ist jedoch in der Regel immer einen Vektorraum eingebettet. So lebt beispielsweise die zulässige Menge eines LPs im Vektorraum $\mathbb {R} ^{n}$. Es reicht nicht die Zielfunktion nur auf der Menge $M$ oder in deinem Fall $G$ zu definieren, da man beispielsweise für die Definition von Differenzierbarkeit immer auf offenen Mengen arbeitet und auch für Konvexität merkwürdige Randfälle auftreten, wenn man diese nur auf einer abgeschlossenen Menge selbst definiert. Die Minimalforderung wäre also, dass $f$ auf einer offenen Obermenge von $G$ definiert ist, aber warum dann nicht gleich auf einen Vektorraum gehen, der algebraische Struktur mitbringt? Mir ist kein Optimierungsproblem bekannt, das sich nicht in einem Vektorraum darstellen lässt.
3. Damit kommen wir zum TSP. Zunächst lassen sich Permutationen über eine endliche Menge als Funktionen von den natürlichen Zahlen in ebendiese Menge identifizieren und demzufolge auch in einen Vektorraum einbetten, welcher in diesem Fall ein Funktionenraum wäre. Das tut man allerdings in der Praxis nicht. Das TSP wird für state-of-the-art Anwendungen als lineares ganzzahliges Optimierungsproblem formuliert und gelöst. Dazu kann ich die englische Version des TSP-Artikels empfehlen und zwar die Sektion über verschiedene Formulierungen als ILP: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulations

Ich möchte aber nicht alles abwehren. Hast du einen Gegenvorschlag für die Formulierung? Vielleicht finden wir einen Kompromiss? Dein Hauptkritikpunkt ist, dass es aussieht als würden $M$ und $V$ ähnliche Funktionen erfüllen, was verwirrend erscheinen kann, oder? --BumbleMath (Diskussion) 18:59, 12. Dez. 2023 (CET)

So wie ich das verstehe, sollen die Entscheidungsvariablen also den Raum der möglichen Lösungen definieren, man sagt etwa: x ist ein Element von $\mathbb {R} ^{3}$, um festzulegen, dass eine Lösung ein 3-Tupel reeller Zahlen ist. Das finde ich merkwürdig und verwirrend dargestellt, denn dies ist doch mit $G=\mathbb {R} ^{3}$ bereits ausgedrückt.

Mir scheint, der Lösungsraum wird im Hinblick auf eine bestimmte Klasse von Optimierungsproblemen oder auf bestimmte Lösungsverfahren zweckmäßig als Vektorraum dargestellt. Aber da es nicht zwingend so gemacht werden muss, würde ich das erst nachfolgend beschreiben.

Man könnte vielleicht so schreiben:

Ein Optimierungsproblem wird durch einen Lösungsraum $G$ und eine Zielfunktion $f:\rightarrow \mathbb {R}$ gegeben. Man sucht ein $x\in G$ mit dem kleinstmöglichen $f(x)$, also so dass $f(x)=min\{f(h)|h\in G\}$.

Es ist dabei oft sinnvoll, einen Vektorraum $V$ zu definieren, in den die Menge der zulässigen Lösungen $G\subseteq V$ eingebettet ist. Usw. --Megatherium (Diskussion) 14:12, 13. Dez. 2023 (CET)

Ich stimme der Sichtweise von BumbleMath zu, weil es die Sichtweise ist, die sich in der Literatur zu Optimierungsproblemen etabliert hat. Der Raum V legt unter anderem fest, welche Methoden sich grundsätzlich anwenden lassen (Methoden der unendlichdimensionalen Optimierung, der gemischt-ganzzahligen Optimierung, der kontinuierlichen Optimierung ...), aber in der Menge M wird dann diejenige Teilmenge von V definiert, über die die Zielfunktion minimiert werden soll. Vielleicht sollte man nur von einem Raum V anstelle von einem "Vektorraum" sprechen, weil z.B. ganzzahlige Vektoren keinen Vektorraum (im üblichen Sinn) bilden. --Beuteltier23 (Diskussion) 15:41, 13. Dez. 2023 (CET)

Bitte die neue Version prüfen. V muss jetzt kein Vektorraum mehr sein und auch grundsätzlich nicht unbedingt existieren. Dadurch ist die Formulierung hoffentlich noch verständlicher geworden. --BumbleMath (Diskussion) 16:24, 13. Dez. 2023 (CET)

zweiter Absatz

Ich komme mit der Beschreibung des eigentlichen Problems nicht hin:

...ein Problem, das nach der Qualität einer bestmöglichen Lösung 
aus einer Menge von potentiellen Lösungen fragt.

Das Problem besteht nicht darin eine optimale Lösung zu finden, 
sondern lediglich die Güte der Lösung.

Der 2. Satz ist imo erstens unlogisch, (die Güte welcher Lösung, wenn man noch keine gefunden hat bzw. eine große Menge möglicher Lösungen.), und zwotens widerspricht er dem ersten Satz. Ich würde den ganzen 2. Absatz streichen. Jemand was dagegen?

Außerdem sollte noch eingefügt werden, das die Qualität einer Lösung mittels einer Zielfunktion berechnet wird.

Szs 10:59, 11. Mär 2005 (CET)

Durch die neue Version hat sich das Problem erledigt. Danke für den Hinweis. --BumbleMath (Diskussion) 08:44, 6. Dez. 2023 (CET)

Beschränkt auf Informatik?

Ist der Begriff nur auf die theoretische Informatik beschränkt? In den Wirtschaftswissenschaften spricht man jedebfalls auch von Optimierungsproblemen.

Tim

Ja, unzwar seit es genügend leistungfähige Rechner gibt, die diese Lösen können. In den WiWis findet also "nur" die (teilweise) Anwendung statt. --Koethnig 23:33, 28. Apr 2006 (CEST)

Quatsch, der Einwand von Tim ist absolut berechtigt, s. z.B. Lineare_Optimierung - vielleicht DAS klassische Beispiel für Optimierungsprobleme - die eben auch interdisziplinär in Mathematik, Wirtschaft und Informatik (also im OR) untersucht werden. Übrigens schon seit den 1920ger Jahren... --Graf Alge 15:20, 5. Apr. 2011 (CEST)

Im übrigen s. auch noch die viel ausführlichere Beschreibung von Optimierungsproblemen unter Optimierung (Mathematik) - noch ist die Mathematik wohl kein Teilgebiet der theoretischen Informatik... --Graf Alge 17:16, 5. Apr. 2011 (CEST)

Tim hat absolut recht. Die theoretische Informatik würde mir (als Professor für Optimierung im Bereich der Informatik) nicht als natürliche Heimat von Optimierungsproblemen erscheinen. Zunächst ist es in der Mathematik beheimatet und hat viele Anwendungen (Informatik, Ingenieurwissenschaften, Wirtschaftswissenschaften, Machine Learning, ...) -- BumbleMath (ohne (gültigen) Zeitstempel signierter Beitrag von BumbleMath (Diskussion | Beiträge) 15:26, 3. Dez. 2023 (CET))

Dieser Punkt hat sich durch die neue Version hoffentlich ebenfalls in Wohlgefallen aufgelöst. --BumbleMath (Diskussion) 08:44, 6. Dez. 2023 (CET)