„Optimierungsproblem“ – Versionsunterschied

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

Ü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 vorigenvorherigen 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

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.

* 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)''.

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.