PhilKa: /* P, NP, NP-schwer, NP-vollständig und P vs. NP */

2026-04-30T09:58:59Z

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

PhilKa: /* Zusammenfassung */

2026-04-30T09:55:32Z

Zusammenfassung

← Nächstältere Version		Version vom 30. April 2026, 11:55 Uhr
Zeile 205:		Zeile 205:

	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.		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 =		= P, NP, NP-schwer, NP-vollständig und P vs. NP =

PhilKa: /* Zusammenfassung */

2026-04-30T09:55:01Z

Zusammenfassung

Änderungen zeigen

PhilKa: Die Seite wurde neu angelegt: „= 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 '…“

2026-04-14T13:16:48Z

Die Seite wurde neu angelegt: „= 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 '…“

Neue Seite

= 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 <math>x^*</math> ist ein '''globales Minimum''' einer Zielfunktion <math>f(x)</math>, wenn gilt:

<math>
f(x^*) \leq f(x) \quad \forall x \in X
</math>

Dabei ist <math>X</math> der gesamte zulässige Lösungsraum.

Analog liegt ein '''globales Maximum''' vor, wenn:

<math>
f(x^*) \geq f(x) \quad \forall x \in X
</math>

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

=== Lokales Optimum ===
Ein Punkt <math>x^*</math> ist ein '''lokales Minimum''', wenn er innerhalb einer Umgebung <math>U(x^*)</math> minimal ist:

<math>
f(x^*) \leq f(x) \quad \forall x \in U(x^*)
</math>

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

<math>
\max f(x)
</math>

kann umgeschrieben werden zu

<math>
\min -f(x)
</math>

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

=== Minimierung zu Maximierung ===
Analog gilt:

<math>
\min f(x)
</math>

entspricht

<math>
\max -f(x)
</math>

=== 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 ===

<math>
\min_{x \in X} f(x)
</math>

mit:

* <math>x</math> – Entscheidungsvariable bzw. Lösungsvektor
* <math>X</math> – zulässiger Lösungsraum / Menge aller erlaubten Lösungen
* <math>f(x)</math> – Zielfunktion

=== Weitere häufige Schreibweisen ===

{| class="wikitable"
! Notation
! Bedeutung
|-
| <math>\arg\min_{x \in X} f(x)</math>
| Liefert den Punkt, an dem das Minimum angenommen wird
|-
| <math>\arg\max_{x \in X} f(x)</math>
| Liefert den Punkt, an dem das Maximum angenommen wird
|-
| <math>\min f(x)</math>
| Minimaler Funktionswert
|-
| <math>\max f(x)</math>
| 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:

<math>
\sup_{x \in X} f(x)
</math>

Das Supremum muss nicht selbst in der Menge enthalten sein.

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

Notation:

<math>
\inf_{x \in X} f(x)
</math>

Auch das Infimum muss nicht angenommen werden.

=== Beispiel ===
Für die offene Menge <math>X=(0,1)</math> gilt bei <math>f(x)=x</math>:

* <math>\inf f(x)=0</math>, aber kein Minimum vorhanden
* <math>\sup f(x)=1</math>, 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:

<math>
x \in \mathbb{R}^n
</math>

Typische Anwendungsfälle:

* Parameteroptimierung
* Regelungstechnik
* Maschinelles Lernen

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

Beispiel:

<math>
x \in \mathbb{Z}^n
</math>

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 ===

{| class="wikitable"
! 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.

Grundbegriffe der Optimierung - Versionsgeschichte

PhilKa: /* P, NP, NP-schwer, NP-vollständig und P vs. NP */

PhilKa: /* Zusammenfassung */

PhilKa: /* Zusammenfassung */