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

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
- 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
- Das Optimierungsproblem
ist ein Optimierungsproblem mit eindeutigem Optimalpunkt
und Optimalwert
.
- Rucksackproblem
- Problem des Handlungsreisenden
- Transportproblem
- Scheduling-Probleme (siehe [4] für eine Ausarbeitung als Optimierungsproblem)
- Parameterschätzung in Statistik/Machine Learning durch Minimierung der Verlustfunktion (engl. loss function) etwa durch die Methode der kleinsten Quadrate oder die Methode der kleinsten absoluten Abweichungen
- Probleme der Graphentheorie wie das Problem der kürzesten Pfade oder der Frage nach optimalen Flüssen und Schnitten in Netzwerken.
Klassifikation von Optimierungsproblemen
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
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
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
- ↑ 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.
- ↑ 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.
- ↑ 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]).
- ↑ 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]).
- ↑ 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;]).



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 22.03. 2025