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.

P, NP, NP-schwer, NP-vollständig und P vs. NP

Überblick

Die Begriffe P, NP, NP-schwer und NP-vollständig stammen aus der theoretischen Informatik und dienen dazu, Probleme nach ihrer algorithmischen Schwierigkeit einzuordnen. Sie beschreiben nicht einzelne Programme, sondern Klassen von Problemen.

Besonders wichtig sind diese Begriffe bei Optimierungsproblemen, da viele praktische Probleme nicht effizient exakt lösbar sind und daher heuristische oder approximative Verfahren eingesetzt werden.

P

P steht für polynomial time.

Ein Entscheidungsproblem liegt in der Klasse P, wenn es mit einem deterministischen Algorithmus in polynomialer Zeit gelöst werden kann.

Das bedeutet: Die Laufzeit wächst höchstens polynomial mit der Eingabegröße, zum Beispiel:

$$\begin{gathered} O(n), \\ O(n^2), \\ O(n^3) \end{gathered}$$

Probleme in P gelten als effizient lösbar.

Beispiel

Die Frage, ob eine Zahl gerade ist, kann sehr schnell entschieden werden. Auch viele Sortier- und Suchprobleme liegen in P.

NP

NP steht für nondeterministic polynomial time, auf Deutsch etwa: nichtdeterministisch polynomiell.

Ein Entscheidungsproblem liegt in NP, wenn eine gegebene Lösung in polynomialer Zeit überprüft werden kann.

Wichtig ist:

• Die Lösung muss nicht schnell gefunden werden können.
• Aber wenn eine mögliche Lösung gegeben ist, kann sie schnell überprüft werden.

Beispiel

Beim Traveling-Salesman-Problem als Entscheidungsproblem lautet die Frage:

Gibt es eine Rundreise mit einer Länge von höchstens 100 km?

Wenn eine konkrete Route gegeben ist, kann man ihre Länge leicht berechnen und prüfen, ob sie höchstens 100 km beträgt. Daher liegt dieses Entscheidungsproblem in NP.

NP-schwer

Ein Problem ist NP-schwer beziehungsweise NP-hard, wenn jedes Problem aus NP in polynomialer Zeit auf dieses Problem reduziert werden kann.

Anschaulich bedeutet das:

Ein NP-schweres Problem ist mindestens so schwierig wie die schwierigsten Probleme aus NP.

Wichtig ist: Ein NP-schweres Problem muss selbst nicht in NP liegen. Es kann also auch ein Optimierungsproblem sein und muss nicht zwingend ein Entscheidungsproblem sein.

Beispiel

Das Optimierungsproblem des Traveling Salesman Problems lautet:

Finde die kürzeste Rundreise durch alle Städte.

Dieses Optimierungsproblem ist NP-schwer.

NP-vollständig

Ein Problem ist NP-vollständig, wenn zwei Bedingungen erfüllt sind:

1. Das Problem liegt in NP.
2. Das Problem ist NP-schwer.

Formal:

$\text{NP-vollständig}=\text{NP}\cap \text{NP-schwer}$

NP-vollständige Probleme sind also die schwierigsten Probleme innerhalb der Klasse NP.

Beispiel

Das Entscheidungsproblem des Traveling Salesman Problems:

Gibt es eine Rundreise mit einer Länge von höchstens K?

ist NP-vollständig.

Unterschied zwischen NP-schwer und NP-vollständig

Begriff	Bedeutung	Muss in NP liegen?	Beispiel
NP	Lösungen sind schnell überprüfbar	Ja	TSP als Entscheidungsproblem
NP-schwer	Mindestens so schwer wie alle Probleme in NP	Nein	TSP als Optimierungsproblem
NP-vollständig	In NP und zugleich NP-schwer	Ja	TSP als Entscheidungsproblem

P vs. NP

Das P-vs.-NP-Problem ist eines der bekanntesten offenen Probleme der Informatik.

Die zentrale Frage lautet:

Gilt P = NP?

Oder anders formuliert:

Kann jedes Problem, dessen Lösung schnell überprüft werden kann, auch schnell gelöst werden?

Bedeutung von P = NP

Falls P = NP gelten würde, dann könnten alle Probleme in NP effizient gelöst werden. Das hätte weitreichende Folgen, zum Beispiel für:

• Optimierung
• Kryptographie
• Logistik
• Planung
• Künstliche Intelligenz

Viele heute als schwer geltende Probleme könnten dann effizient gelöst werden.

Bedeutung von P ≠ NP

Die meisten Fachleute vermuten, dass gilt:

$P\ne NP$

Das würde bedeuten:

Es gibt Probleme, deren Lösungen schnell überprüft, aber nicht schnell gefunden werden können.

Dies erklärt, warum für viele schwierige Optimierungsprobleme keine effizienten exakten Algorithmen bekannt sind.

Grafische Einordnung

Falls $P\ne NP$ gilt, ergibt sich folgende typische Einordnung:

Probleme
├── P
│   └── effizient lösbare Probleme
│
├── NP
│   ├── P
│   └── NP-vollständige Probleme
│
└── NP-schwere Probleme
    ├── NP-vollständige Probleme
    └── weitere, nicht zwingend in NP liegende Probleme

Relevanz für Optimierungsprobleme

Viele praktische Optimierungsprobleme sind NP-schwer. Dazu gehören beispielsweise:

• Routenplanung
• Produktionsplanung
• Scheduling
• Rucksackproblem
• Zuordnungsprobleme
• viele gemischt-ganzzahlige Optimierungsprobleme

Da exakte Verfahren bei großen Instanzen oft zu langsam sind, werden in der Praxis häufig approximative Verfahren eingesetzt, zum Beispiel:

• Heuristiken
• Metaheuristiken
• Greedy-Verfahren
• Branch-and-Bound mit Abbruchkriterien
• evolutionäre Algorithmen

Merksätze

• P: Probleme sind schnell lösbar.
• NP: Lösungen sind schnell überprüfbar.
• NP-schwer: Mindestens so schwer wie alle Probleme in NP.
• NP-vollständig: In NP und NP-schwer.
• P vs. NP: Offene Frage, ob schnelles Überprüfen auch schnelles Lösen bedeutet.

Siehe auch

• Optimierungsverfahren
• Heuristische Optimierungsverfahren
• Metaheuristische Verfahren
• Branch-and-Bound-Verfahren
• Multi-Objective Optimization