Optimierungsproblem
# Optimierungsproblem

Ein Optimierungsproblem ist ein mathematisches Problem. Die Aufgabe besteht darin, in einer Menge von Alternativen die beste bezüglich eines Zielkriteriums zu bestimmen. 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 $P$ besteht aus einer reellwertigen Zielfunktion $f$, einer zulässigen Menge $M$, Entscheidungsvariablen $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
    $P:\qquad \min _{x}f(x)\quad {\text{s. t.}}\quad x\in M.$
Üblicherweise ist hierbei $P$ in einen Raum $V$, wie etwa den $\mathbb {R} ^{n}$, eingebettet. In diesem Fall gelten $f:V\to \mathbb {R}$, $M\subseteq V$ und $x\in V$. Die Schreibweise ${\text{s. t.}}$ geht auf den englischen Ausdruck subject to zurück und bedeutet, dass bei der Suche nach der Lösung von $P$ nur sogenannte zulässige Punkte $x\in M$ infrage kommen. Da $\min$ die Optimierungsrichtung angibt, läge in diesem Fall ein Minimierungsproblem vor. Bei einem Maximierungsproblem sind Lösungen $x$ mit möglichst großen $f(x)$ gesucht, aber dieser Fall lässt sich durch Negieren von $f$ auf den vorherigen zurückführen. Falls $P$ lösbar ist, so gibt es mindestens einen Optimalpunkt $x^{\star }\in M$ mit $f(x^{\star })\leq f(x)$ für alle $x\in M$ und einen eindeutigen Optimalwert $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 $M$ von $P$ wird in der Regel durch Gleichungen und Ungleichungen beschrieben und kann daher durch
    $M=\{x\in V|\ g_{i}(x)\leq 0,\ h_{j}(x)=0,\ i\in I,\ j\in J\}$
dargestellt werden, wobei $I$ die Indexmenge der Ungleichungsrestriktionen und $J$ die Indexmenge der Gleichungsrestriktionen darstellt. Restriktionen werden auch als Nebenbedingungen oder Constraints bezeichnet.