imported>Graph Pixel: Tippfehler korrigiert.

2026-03-12T10:42:34Z

Tippfehler korrigiert.

Neue Seite

Ein '''Optimierungsproblem''' ist ein mathematisches Problem. Die Aufgabe besteht darin, in einer Menge von Alternativen die beste bezüglich eines Zielkriteriums zu bestimmen.<ref>{{Literatur |Autor=Oliver Stein |Titel=Grundzüge der Globalen Optimierung |Auflage=2. |Verlag=Springer Spektrum |Ort=Berlin / Heidelberg |Datum=2021 |ISBN=978-3-662-62533-0 |DOI=10.1007/978-3-662-55360-2}}</ref> 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 [[Mathematische Optimierung|mathematischen Optimierung]].

__TOC__

== Mathematische Definition und Begriffe ==
[[Datei:Optimalpunkt Optimalwert.jpg|mini|400x400px|Die Minimierung der Funktion <math>f(x) = (x-1)^2+2</math> ergibt den Optimalpunkt <math>x^\star=1</math> und den Optimalwert <math>v=2</math>.<ref>{{Literatur |Autor=Nathan Sudermann-Merx |Titel=Einführung in Optimierungsmodelle |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2023 |ISBN=978-3-662-67380-5 |DOI=10.1007/978-3-662-67381-2}}</ref> ]]

Ein Optimierungsproblem <math>P</math> besteht aus einer [[Reellwertige Funktion|reellwertigen]] '''Zielfunktion''' <math>f </math>, einer '''zulässigen Menge''' <math>M</math>, '''Entscheidungsvariablen''' <math>x</math> 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
: <math display="block">P:\qquad\min_x f(x)\quad\text{s. t.}\quad x\in M.</math>
Üblicherweise ist hierbei <math>P</math> in einen [[Raum (Mathematik)|Raum]] <math>V</math>, wie etwa den <math>\mathbb{R}^n</math>, eingebettet. In diesem Fall gelten <math>f:V\to \mathbb{R}</math>, <math>M\subseteq V</math> und <math>x\in V</math>. Die Schreibweise <math>\text{s. t.}</math> geht auf den englischen Ausdruck ''subject to'' zurück und bedeutet, dass bei der Suche nach der Lösung von <math>P</math> nur sogenannte '''zulässige Punkte''' <math>x\in M</math> infrage kommen. Da <math>\min</math> die Optimierungsrichtung angibt, läge in diesem Fall ein '''Minimierungsproblem''' vor. Bei einem '''Maximierungsproblem''' sind Lösungen <math>x</math> mit möglichst großen <math>f(x)</math> gesucht, aber dieser Fall lässt sich durch Negieren von <math>f</math> auf den vorherigen zurückführen. Falls <math>P</math> lösbar ist, so gibt es mindestens einen '''Optimalpunkt''' <math>x^\star\in M</math> mit <math>f(x^\star) \le f(x)</math> für alle <math>x\in M</math> und einen eindeutigen '''Optimalwert''' <math>v=f(x^\star)</math>. Zu beachten ist, dass der Optimal''punkt'' in der Regel ein hochdimensionaler Vektor ist (zum Beispiel die optimale Route im Falle des Problems des Handlungsreisenden) und der Optimal''wert'' eine [[reelle Zahl]] ist (etwa die Länge der kürzesten Tour). Die zulässige Menge <math>M</math> von <math>P</math> wird in der Regel durch Gleichungen und Ungleichungen beschrieben und kann daher durch
: <math display="block">M = \{x\in V|\ g_i(x)\le 0,\ h_j(x)=0,\ i\in I,\ j\in J\}</math>
dargestellt werden, wobei <math>I</math> die Indexmenge der '''Ungleichungsrestriktionen''' und <math>J</math> 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 [[Kombinatorische Optimierung|kombinatorischen Optimierung]] wie beispielsweise bei der Formulierung des Problems des Handlungsreisenden.<ref>{{Literatur |Autor=Bernhard Korte, Jens Vygen |Titel=Combinatorial optimization: theory and algorithms |Nummer= |Auflage=5. |Verlag=Springer |Ort=Berlin Heidelberg |Datum=2012 |Reihe=Algorithms and combinatorics |ISBN=978-3-642-24487-2 |Online=https://www.mathematik.uni-muenchen.de/~kpanagio/KombOpt/book.pdf |Abruf=2024-01-21}}</ref>
* Die funktionale Beschreibung eines Optimierungsproblems, das heißt die Wahl der Funktionen <math>f</math>, <math>g_i</math> und <math>h_j</math>, 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]].
{{Siehe auch|Optimierungsmodell}}

== Ausgewählte Beispiele ==

* Das Optimierungsproblem <math>P:\qquad \min_{x\in\mathbb{R}^2} x_1^2+x_2\quad\text{s. t.}\quad x_2\ge -1</math> ist ein Optimierungsproblem mit eindeutigem Optimalpunkt <math>x^\star=(0,-1)</math> und Optimalwert <math>v = -1</math>.
* [[Rucksackproblem]]
* [[Problem des Handlungsreisenden]]
* [[Transportproblem]]
* [[Scheduling|Scheduling-Probleme]] (siehe <ref>{{Literatur |Autor=Christodoulos A. Floudas, Xiaoxia Lin |Titel=Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications |Sammelwerk=Annals of Operations Research |Band=139 |Nummer=1 |Datum=2005-10 |ISSN=0254-5330 |Seiten=131–162 |Online=https://lin.engin.umich.edu/wp-content/uploads/sites/551/2021/10/Mixed-Integer-Linear-Programming-in-Process-Scheduling.pdf |DOI=10.1007/s10479-005-3446-x}}</ref> für eine Ausarbeitung als Optimierungsproblem)
* Parameterschätzung in Statistik/Machine Learning durch Minimierung der [[Verlustfunktion (Statistik)|Verlustfunktion]] (engl. ''loss function'') etwa durch die [[Methode der kleinsten Quadrate]] oder die [[Median-Regression|Methode der kleinsten absoluten Abweichungen]]
* Probleme der [[Graphentheorie]] wie das Problem der [[Kürzester Pfad|kürzesten Pfade]] oder der Frage nach optimalen [[Flüsse und Schnitte in Netzwerken|Flüssen und Schnitten in Netzwerken]].

== Klassifikation von Optimierungsproblemen ==

Optimierungsprobleme lassen sich anhand ihrer mathematischen Eigenschaften klassifizieren.

* Falls <math>V</math> unendlichdimensional ist, ist <math>P</math> ein ''unendlichdimensionales Optimierungsproblem''. Dies tritt etwa in der [[Variationsrechnung]] oder der [[Optimale Steuerung|optimalen Steuerung]] auf. Im Folgenden gehen wir von endlichdimensionalen Optimierungsproblemen aus.
* Falls <math>P</math> mehrere Zielfunktionen besitzt, sprechen wir von der [[Mehrzieloptimierung]] und bezeichnen <math>P</math> als ''multikriterielles Optimierungsproblem''. Im Folgenden gehen wir von Optimierungsproblemen mit einer Zielfunktion aus. Diese werden auch ''skalare Optimierungsprobleme'' genannt.
* Falls <math>P</math> keine Restriktionen besitzt, d. h. falls <math>M=V</math> gilt, ist <math>P</math> ein ''unrestringiertes Optimierungsproblem'', andernfalls ist <math>P</math> ein ''restringiertes Optimierungsproblem''.
* Falls <math>V=\mathbb B^n </math> gilt, d. h. alle Entscheidungsvariablen binär sind, <math>P</math> keine Restriktionen besitzt und die Zielfunktion <math>f</math> quadratisch ist, so spricht man von ''[[Quadratische unrestringierte binäre Optimierung|quadratischer unrestringierter binärer Optimierung]] (QUBO)''.
* Falls <math>V=\mathbb R^n</math> gilt und die Zielfunktion <math>f</math> sowie die Funktionen <math>g_i,\ i\in I,</math> und <math>h_j,\ j\in J,</math> linear sind, ist <math>P</math> ein ''(kontinuierliches) [[Lineare Optimierung|lineares Optimierungsproblem]] (LP)''.
* Falls <math>V=\mathbb R^n</math> gilt, die die Gleichungen definierende Funktionen <math>h_j,\ j\in J,</math> linear sind, und die Zielfunktion <math>f</math> sowie ggf. Funktionen <math>g_i,\ i\in I,</math> quadratisch sind, ist <math>P</math> ein ''(kontinuierliches) [[Quadratische Optimierung|quadratisches Optimierungsproblem]] (QP)'' bzw. ein ''(kontinuierliches) [[Quadratische Optimierung|quadratisches Optimierungsproblem mit quadratischen Nebenbedingungen]]'' (''QCQP)''.
* Falls <math>V=\mathbb R^n</math> gilt und <math>M</math> eine [[konvexe Menge]] ist sowie die Zielfunktion <math>f</math> eine [[Konvexe und konkave Funktionen|konvexe Funktion]], ist <math>P</math> ein [[Konvexe Optimierung|''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 <math>g_i,\ i\in I,</math> nicht selbst konvex sein müssen, um eine konvexe zulässige Menge zu definieren<ref>{{Literatur |Autor=Stephen P. Boyd, Lieven Vandenberghe |Titel=Convex optimization |Auflage=29. |Verlag=Cambridge University Press |Ort=Cambridge / New York / Melbourne / New Delhi / Singapore |Datum=2023 |ISBN=978-0-521-83378-3 |Online=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |Format=PDF |KBytes=6900 |Abruf=2023-12-07}}</ref>. Spezialfälle für konvexe Optimierungsprobleme sind [[Konisches Programm|''konische Optimierungsprobleme'']] (insbesondere [[Semidefinite Programmierung|''semi-definite'']] und [[SOCP|''Second-Order-Cone Probleme'']]) und ''[[Geometrisches Programm|geometrische Optimierungsprobleme]]''.
* Falls <math>V=\mathbb R^n</math> gilt und beliebig viele der Funktionen <math>f</math>, <math>g_i,\ i\in I,</math> und <math>h_j,\ j\in J,</math> beliebig nichtlinear (jedoch meistens stetig differenzierbar) sind, ist <math>P</math> ein ''[[Nichtlineare Optimierung|nichtlineares Optimierungsproblem]] (NLP).''
* Falls <math>V=\mathbb Z^n</math> gilt und die Zielfunktion <math>f</math> sowie die Funktionen <math>g_i,\ i\in I,</math> und <math>h_j,\ j\in J,</math> linear sind, ist <math>P</math> ein ''[[Ganzzahlige lineare Optimierung|ganzzahliges lineares Optimierungsproblem]] (ILP).''
* Falls <math>V=\mathbb{R^n} \times \mathbb{Z^m}</math> gilt, d. h. falls einige der Entscheidungsvariablen kontinuierlich und andere ganzzahlig sind, und die Zielfunktion <math>f</math> sowie die Funktionen <math>g_i,\ i\in I,</math> und <math>h_j,\ j\in J,</math> linear sind, ist <math>P</math> ein ''[[Gemischt-ganzzahlige Optimierung#Gemischt-ganzzahlige lineare Optimierungsprobleme|gemischt-ganzzahliges lineares Optimierungsproblem]] (MILP oder MIP).''
* Falls <math>V=\mathbb{R^n} \times \mathbb{Z^m}</math> gilt und beliebig viele der Funktionen <math>f</math>, <math>g_i,\ i\in I,</math> und <math>h_j,\ j\in J,</math> quadratisch sind, ist <math>P</math> ein ''[[Gemischt-ganzzahlige Optimierung|gemischt-ganzzahliges quadratisches Optimierungsproblem]] (MIQP oder ggf. MIQCP)''
* Falls <math>V=\mathbb{R^n} \times \mathbb{Z^m}</math> gilt und beliebig viele der Funktionen <math>f</math>, <math>g_i,\ i\in I,</math> und <math>h_j,\ j\in J,</math> beliebig nichtlinear sind, ist <math>P</math> ein ''[[Gemischt-ganzzahlige Optimierung#Mathematische Definition|gemischt-ganzzahliges nichtlineares Optimierungsproblem]] (MINLP)''
* Falls <math>V=\mathbb Z^n</math> gilt, ist <math>P</math> ein [[Kombinatorische Optimierung|''kombinatorisches Optimierungsproblem'']].
* Falls <math>V=\mathbb R^n</math> gilt und <math>P</math> ([[Abzählbare Menge|abzählbar]]) unendlich viele Gleichungsrestriktionen besitzt, ist <math>P</math> ein ''[[semi-infinites Optimierungsproblem]] (SIP)''.

== Optimierungsmethoden ==
{{Hauptartikel|Mathematische Optimierung#Optimierungsmethoden}}
Einen Algorithmus, der ein Optimierungsproblem löst, nennt man [[Mathematische Optimierung#Optimierungsmethoden|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 [[Maschinelles Lernen|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-Verfahren|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 [[Metaheuristik]]en eingesetzt werden, die in der Regel jedoch keine Aussage über die Qualität der gefundenen Lösung treffen.

== Weblinks ==
{{Wiktionary}}
* {{DNB-Portal|4390818-4|TEXT=Literatur zum}}

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4390818-4|LCCN=|NDL=|VIAF=}}

[[Kategorie:Optimierung]]
[[Kategorie:Mathematik]]

Optimierungsproblem - Versionsgeschichte

imported>Graph Pixel: Tippfehler korrigiert.