Optimierungsproblem

Ein Optimierungsproblem ist ein mathematisches Problem. Die Aufgabe besteht darin, in einer Menge von Alternativen die beste bezüglich eines Zielkriteriums zu bestimmen.[1] Ein Beispiel ist das Problem des Handlungsreisenden, also die Bestimmung einer kürzesten Rundreise durch eine Reihe von Städten. Die Modellierung und das Lösen von Optimierungsproblemen sind Teil der mathematischen Optimierung.

Mathematische Definition und Begriffe

Die Minimierung der Funktion {\displaystyle f(x)=(x-1)^{2}+2} ergibt den Optimalpunkt {\displaystyle x^{\star }=1} und den Optimalwert {\displaystyle v=2}.[2]

Ein Optimierungsproblem {\displaystyle P} besteht aus einer reellwertigen Zielfunktion {\displaystyle f}, einer zulässigen Menge {\displaystyle M}, Entscheidungsvariablen {\displaystyle x} und festen problemdefinierenden Eingangsdaten wie etwa den Abständen zwischen den zu besuchenden Städten des Problems des Handlungsreisenden oder dem Wert der Gegenstände im Rucksackproblem. Es ist gegeben durch

{\displaystyle P:\qquad \min _{x}f(x)\quad {\text{s. t.}}\quad x\in M.}

Üblicherweise ist hierbei {\displaystyle P} in einen Raum {\displaystyle V}, wie etwa den {\displaystyle \mathbb {R} ^{n}}, eingebettet. In diesem Fall gelten {\displaystyle f:V\to \mathbb {R} }, {\displaystyle M\subseteq V} und {\displaystyle x\in V}. Die Schreibweise {\displaystyle {\text{s. t.}}} geht auf den englischen Ausdruck subject to zurück und bedeutet, dass bei der Suche nach der Lösung von {\displaystyle P} nur sogenannte zulässige Punkte {\displaystyle x\in M} infrage kommen. Da {\displaystyle \min } die Optimierungsrichtung angibt, läge in diesem Fall ein Minimierungsproblem vor. Bei einem Maximierungsproblem sind Lösungen {\displaystyle x} mit möglichst großen {\displaystyle f(x)} gesucht, aber dieser Fall lässt sich durch Negieren von {\displaystyle f} auf den vorherigen zurückführen. Falls {\displaystyle P} lösbar ist, so gibt es mindestens einen Optimalpunkt {\displaystyle x^{\star }\in M} mit {\displaystyle f(x^{\star })\leq f(x)} für alle {\displaystyle x\in M} und einen eindeutigen Optimalwert {\displaystyle v=f(x^{\star })}. Zu beachten ist, dass der Optimalpunkt in der Regel ein hochdimensionaler Vektor ist (zum Beispiel die optimale Route im Falle des Problems des Handlungsreisenden) und der Optimalwert eine reelle Zahl ist (etwa die Länge der kürzesten Tour). Die zulässige Menge {\displaystyle M} von {\displaystyle P} wird in der Regel durch Gleichungen und Ungleichungen beschrieben und kann daher durch

{\displaystyle M=\{x\in V|\ g_{i}(x)\leq 0,\ h_{j}(x)=0,\ i\in I,\ j\in J\}}

dargestellt werden, wobei {\displaystyle I} die Indexmenge der Ungleichungsrestriktionen und {\displaystyle J} die Indexmenge der Gleichungsrestriktionen darstellt. Restriktionen werden auch als Nebenbedingungen oder Constraints bezeichnet.

Anmerkungen

Ausgewählte Beispiele

Klassifikation von Optimierungsproblemen

Optimierungsprobleme lassen sich anhand ihrer mathematischen Eigenschaften klassifizieren.

Optimierungsmethoden

→ Hauptartikel: Mathematische Optimierung#Optimierungsmethoden

Einen Algorithmus, der ein Optimierungsproblem löst, nennt man Optimierungsmethode oder Optimierungsalgorithmus. Je nach Klasse des Optimierungsproblems kommen verschiedene Verfahren zum Einsatz. Neben spezialisierten Verfahren, wie etwa dem Dijkstra-Algorithmus zur Bestimmung kürzester Wege gibt es auch allgemeine Lösungsverfahren, welche anwendungsunabhängig basierend auf der Kenntnis der Problemklasse eingesetzt werden können. Am bekanntesten sind vermutlich die Verfahren der nichtlinearen Optimierung zur Bestimmung lokaler Optimalpunkte wie das Gradientenverfahren, das Newtonverfahren und Quasi-Newton-Verfahren. Für die Minimierung der Verlustfunktion im Bereich Machine Learning werden typischerweise leichtfüßige Varianten des Gradientenverfahrens wie das stochastische Gradientenverfahren (stochastic gradient descent) eingesetzt. Für LPs kommen das Simplex-Verfahren sowie Innere-Punkte-Methoden zum Einsatz, wobei letztgenannte auch zur Lösung nichtlinearer konvexer Optimierungsprobleme verwendet werden. Optimierungsprobleme, in denen auch ganzzahlige Variablen auftreten, können exakt mit Branch-and-Bound sowie Branch-and-Cut Methoden gelöst werden. Darüber hinaus können auch anwendungsspezifische Heuristiken wie die Nearest-Neighbor-Heuristik oder allgemeine Metaheuristiken eingesetzt werden, die in der Regel jedoch keine Aussage über die Qualität der gefundenen Lösung treffen.

Einzelnachweise

  1. Oliver Stein: Grundzüge der Globalen Optimierung. 2. Auflage. Springer Spektrum, Berlin / Heidelberg 2021, ISBN 978-3-662-62533-0, doi: Extern 10.1007/978-3-662-55360-2.
  2. Nathan Sudermann-Merx: Einführung in Optimierungsmodelle. Springer, Berlin / Heidelberg 2023, ISBN 978-3-662-67380-5, doi: Extern 10.1007/978-3-662-67381-2.
  3. Bernhard Korte, Jens Vygen: Combinatorial optimization: theory and algorithms (= Algorithms and combinatorics). 5. Auflage. Springer, Berlin Heidelberg 2012, ISBN 978-3-642-24487-2 ( Extern uni-muenchen.de [PDF]).
  4. Christodoulos A. Floudas, Xiaoxia Lin: Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications. In: Annals of Operations Research. Band 139, Nr. 1, Oktober 2005, ISSN Extern 0254-5330, S. 131–162, doi: Extern 10.1007/s10479-005-3446-x ( Extern umich.edu [PDF]).
  5. Stephen P. Boyd, Lieven Vandenberghe: Convex optimization. 29. Auflage. Cambridge University Press, Cambridge / New York / Melbourne / New Delhi / Singapore 2023, ISBN 978-0-521-83378-3 ( Extern stanford.edu [PDF; 6,9 MB;]).
Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 22.03. 2025