Grundbegriffe der Optimierung

Grundbegriffe der Optimierung

Die Optimierung beschäftigt sich mit der systematischen Suche nach einer Lösung, welche eine gegebene Zielfunktion unter bestimmten Randbedingungen bestmöglich erfüllt. In der Informatik, Mathematik und im Operations Research bildet sie die Grundlage zahlreicher Verfahren zur Entscheidungsunterstützung, Planung und Steuerung technischer sowie wirtschaftlicher Systeme.

Globales und lokales Optimum

Ein Optimum bezeichnet den besten erreichbaren Wert einer Zielfunktion innerhalb des zulässigen Lösungsraums.

Globales Optimum

Ein Punkt $x^{*}$ ist ein globales Minimum einer Zielfunktion $f(x)$, wenn gilt:

$f(x^{*})\le f(x)\mathrm{\forall }x\in X$

Dabei ist $X$ der gesamte zulässige Lösungsraum.

Analog liegt ein globales Maximum vor, wenn:

$f(x^{*})\ge f(x)\mathrm{\forall }x\in X$

Das globale Optimum stellt somit die beste Lösung über den gesamten Suchraum dar.

Lokales Optimum

Ein Punkt $x^{*}$ ist ein lokales Minimum, wenn er innerhalb einer Umgebung $U(x^{*})$ minimal ist:

$f(x^{*})\le f(x)\mathrm{\forall }x\in U(x^{*})$

Ein lokales Optimum ist nur im direkten Umfeld optimal, nicht zwangsläufig jedoch global.

Bedeutung in der Praxis

Viele Optimierungsprobleme – insbesondere nichtlineare oder kombinatorische – besitzen mehrere lokale Optima. Die Herausforderung vieler Optimierungsverfahren besteht darin, das globale statt nur eines lokalen Optimums zu finden.

Umwandlung eines Maximierungsproblems in ein Minimierungsproblem und umgekehrt

Da viele Optimierungsalgorithmen nur für Minimierungsprobleme formuliert sind, werden Maximierungsprobleme häufig umgeformt.

Maximierung zu Minimierung

Ein Maximierungsproblem

$\max f(x)$

kann umgeschrieben werden zu

$\min -f(x)$

Die Maximierung einer Funktion entspricht somit der Minimierung ihres negativen Wertes.

Minimierung zu Maximierung

Analog gilt:

$\min f(x)$

entspricht

$\max -f(x)$

Vorteil

Durch diese Transformation können Algorithmen einheitlich für einen Problemtyp implementiert werden.

Notationen

In der Optimierung existieren standardisierte mathematische Notationen zur Beschreibung von Problemen.

Allgemeine Form eines Optimierungsproblems

$\underset{x\in X}{\min }f(x)$

mit:

• $x$ – Entscheidungsvariable bzw. Lösungsvektor
• $X$ – zulässiger Lösungsraum / Menge aller erlaubten Lösungen
• $f(x)$ – Zielfunktion

Weitere häufige Schreibweisen

Notation	Bedeutung
$\arg \underset{x\in X}{\min }f(x)$	Liefert den Punkt, an dem das Minimum angenommen wird
$\arg \underset{x\in X}{\max }f(x)$	Liefert den Punkt, an dem das Maximum angenommen wird
$\min f(x)$	Minimaler Funktionswert
$\max f(x)$	Maximaler Funktionswert

Supremum und Infimum

Nicht jede Funktion nimmt ihr Maximum oder Minimum tatsächlich an. Zur Beschreibung solcher Fälle werden die Begriffe Supremum und Infimum verwendet.

Supremum

Das Supremum einer Menge ist ihre kleinste obere Schranke.

Notation:

$\underset{x\in X}{\sup }f(x)$

Das Supremum muss nicht selbst in der Menge enthalten sein.

Infimum

Das Infimum ist die größte untere Schranke einer Menge.

Notation:

$\underset{x\in X}{\inf }f(x)$

Auch das Infimum muss nicht angenommen werden.

Beispiel

Für die offene Menge $X=(0,1)$ gilt bei $f(x)=x$:

• $\inf f(x)=0$, aber kein Minimum vorhanden
• $\sup f(x)=1$, aber kein Maximum vorhanden

Kontinuierliche, diskrete und kombinatorische Optimierung

Optimierungsprobleme lassen sich anhand ihres Lösungsraums klassifizieren.

Kontinuierliche Optimierung

Bei der kontinuierlichen Optimierung können Entscheidungsvariablen beliebige reelle Werte innerhalb eines Bereichs annehmen.

Beispiel:

$x\in {\mathbb{ℝ}}^n$

Typische Anwendungsfälle:

• Parameteroptimierung
• Regelungstechnik
• Maschinelles Lernen

Diskrete Optimierung

Bei der diskreten Optimierung dürfen Variablen nur diskrete Werte annehmen, beispielsweise ganze Zahlen.

Beispiel:

$x\in {\mathbb{\mathbb{Z}}}^n$

Typische Anwendungsfälle:

• Produktionsplanung
• Ressourcenallokation
• Ganzzahlige lineare Optimierung

Kombinatorische Optimierung

Die kombinatorische Optimierung ist ein Spezialfall der diskreten Optimierung, bei dem aus einer endlichen Menge diskreter Kombinationen die beste ausgewählt wird.

Typische Probleme:

• Traveling Salesman Problem
• Rucksackproblem
• Graphfärbung
• Scheduling-Probleme

Vergleich

Typ	Lösungsraum	Beispiel
Kontinuierlich	Reelle Zahlen	Parameteroptimierung
Diskret	Ganze Zahlen / diskrete Werte	Ganzzahlige Programmierung
Kombinatorisch	Endliche Kombinationen / Strukturen	TSP, Rucksackproblem

Zusammenfassung

Die Grundbegriffe der Optimierung bilden das Fundament für das Verständnis moderner Optimierungsverfahren. Insbesondere die Unterscheidung zwischen lokalen und globalen Optima, die mathematische Notation von Optimierungsproblemen sowie die Klassifikation verschiedener Problemtypen sind essenziell für die Auswahl geeigneter Lösungsalgorithmen.