Optimierungsproblem

mathematisches Problem
(Weitergeleitet von Zulässige Menge)

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

Bearbeiten
 
Die Minimierung der Funktion   ergibt den Optimalpunkt   und den Optimalwert  .[2]

Ein Optimierungsproblem   besteht aus einer reellwertigen Zielfunktion  , einer zulässigen Menge  , Entscheidungsvariablen   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

 

Üblicherweise ist hierbei   in einen Raum  , wie etwa den  , eingebettet. In diesem Fall gelten  ,   und  . Die Schreibweise   geht auf den englischen Ausdruck subject to zurück und bedeutet, dass bei der Suche nach der Lösung von   nur sogenannte zulässige Punkte   infrage kommen. Da   die Optimierungsrichtung angibt, läge in diesem Fall ein Minimierungsproblem vor. Bei einem Maximierungsproblem sind Lösungen   mit möglichst großen   gesucht, aber dieser Fall lässt sich durch Negieren von   auf den vorherigen zurückführen. Falls   lösbar ist, so gibt es mindestens einen Optimalpunkt   mit   für alle   und einen eindeutigen Optimalwert  . 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   von   wird in der Regel durch Gleichungen und Ungleichungen beschrieben und kann daher durch

 

dargestellt werden, wobei   die Indexmenge der Ungleichungsrestriktionen und   die Indexmenge der Gleichungsrestriktionen darstellt. Restriktionen werden auch als Nebenbedingungen oder Constraints bezeichnet.

Anmerkungen

Bearbeiten
  • Anstatt ein Optimierungsproblem algebraisch, also durch Gleichungen und Ungleichungen, zu beschreiben, ist es manchmal auch üblich, die Problemstellung in der Sprache der Graphentheorie zu formulieren. Dies passiert insbesondere oft in der kombinatorischen Optimierung wie beispielsweise bei der Formulierung des Problem des Handlungsreisenden.[3]
  • Die funktionale Beschreibung eines Optimierungsproblems, das heißt die Wahl der Funktionen  ,   und  , ist in der Regel nicht eindeutig, sondern das Ergebnis eines Modellierungsprozesses, welcher eine ausreichend genaue Beschreibung der Anwendung bei einer möglichst guten Lösbarkeit des resultierenden Problems gewährleisten soll. Steht die Modellierung im Vordergrund, so spricht man auch von einem Optimierungsmodell.

Ausgewählte Beispiele

Bearbeiten

Klassifikation von Optimierungsproblemen

Bearbeiten

Optimierungsprobleme lassen sich anhand ihrer mathematischen Eigenschaften klassifizieren.

  • Falls   unendlichdimensional ist, ist   ein unendlichdimensionales Optimierungsproblem. Dies tritt etwa in der Variationsrechnung oder der optimalen Steuerung auf. Im Folgenden gehen wir von endlichdimensionalen Optimierungsproblemen aus.
  • Falls   mehrere Zielfunktionen besitzt, sprechen wir von der Mehrzieloptimierung und bezeichnen   als multikriterielles Optimierungsproblem. Im Folgenden gehen wir von Optimierungsproblemen mit einer Zielfunktion aus. Diese werden auch skalare Optimierungsprobleme genannt.
  • Falls   keine Restriktionen besitzt, d. h. falls   gilt, ist   ein unrestringiertes Optimierungsproblem, andernfalls ist   ein restringiertes Optimierungsproblem.
  • Falls   gilt, d. h. alle Entscheidungsvariablen binär sind,   keine Restriktionen besitzt und die Zielfunktion   quadratisch ist, so spricht man von quadratischer unrestringierter binärer Optimierung (QUBO).
  • Falls   gilt und die Zielfunktion   sowie die Funktionen   und   linear sind, ist   ein (kontinuierliches) lineares Optimierungsproblem (LP).
  • Falls   gilt, die die Gleichungen definierende Funktionen   linear sind, und die Zielfunktion   sowie ggf. Funktionen   quadratisch sind, ist   ein (kontinuierliches) quadratisches Optimierungsproblem (QP) bzw. ein (kontinuierliches) quadratisches Optimierungsproblem mit quadratischen Nebenbedingungen (QCQP).
  • Falls   gilt und   eine konvexe Menge ist sowie die Zielfunktion   eine konvexe Funktion, ist   ein konvexes Optimierungsproblem. Man beachte, das die Zielfunktion nicht zwangsläufig differenzierbar sein muss, da auf das Subdifferential zurückgegriffen werden kann und auch die Funktionen   nicht selbst konvex sein müssen, um eine konvexe zulässige Menge zu definieren[5]. Spezialfälle für konvexe Optimierungsprobleme sind konische Optimierungsprobleme (insbesondere semi-definite und Second-Order-Cone Probleme) und geometrische Optimierungsprobleme.
  • Falls   gilt und beliebig viele der Funktionen  ,   und   beliebig nichtlinear (jedoch meistens stetig differenzierbar) sind, ist   ein nichtlineares Optimierungsproblem (NLP).
  • Falls   gilt und die Zielfunktion   sowie die Funktionen   und   linear sind, ist   ein ganzzahliges lineares Optimierungsproblem (ILP).
  • Falls   gilt, d. h. falls einige der Entscheidungsvariablen kontinuierlich und andere ganzzahlig sind, und die Zielfunktion   sowie die Funktionen   und   linear sind, ist   ein gemischt-ganzzahliges lineares Optimierungsproblem (MILP oder MIP).
  • Falls   gilt und beliebig viele der Funktionen  ,   und   quadratisch sind, ist   ein gemischt-ganzzahliges quadratisches Optimierungsproblem (MIQP oder ggf. MIQCP)
  • Falls   gilt und beliebig viele der Funktionen  ,   und   beliebig nichtlinear sind, ist   ein gemischt-ganzzahliges nichtlineares Optimierungsproblem (MINLP)
  • Falls   gilt, ist   ein kombinatorisches Optimierungsproblem.
  • Falls   gilt und   (abzählbar) unendlich viele Gleichungsrestriktionen besitzt, ist   ein semi-infinites Optimierungsproblem (SIP).

Optimierungsmethoden

Bearbeiten

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.

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Oliver Stein: Grundzüge der Globalen Optimierung. 2. Auflage. Springer Spektrum, Berlin / Heidelberg 2021, ISBN 978-3-662-62533-0, doi: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: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 (uni-muenchen.de [PDF; abgerufen am 21. Januar 2024]).
  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 0254-5330, S. 131–162, doi:10.1007/s10479-005-3446-x (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 (stanford.edu [PDF; 6,9 MB; abgerufen am 7. Dezember 2023]).