Optimalitätskriterium

Optimalitätskriterien spielen eine wichtige Rolle in der mathematischen Optimierung. Sie werden entsprechend ihrer Stärke und den nötigen Voraussetzungen kategorisiert und dazu verwendet, mögliche Optimalpunkte eines Problems aufzufinden (notwendige Kriterien) oder zu entscheiden, ob ein gefundener Punkt tatsächlich ein Optimalpunkt ist (hinreichende Kriterien).

Definition

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x } ein zulässiger Punkt eines Optimierungsproblems und $K$ ein gewisses Kriterium. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K } heißt notwendiges Optimalitätskriterium für eine bestimmte Klasse von Problemen, wenn folgende Aussage gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \text{ ist optimal } \implies K \text{ gilt } } .

oder in verneinter Form

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K \text{ gilt nicht } \implies x \text{ ist nicht optimal } }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K } heißt ein hinreichendes Optimalitätskriterium, wenn folgende Aussage gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K \text{ gilt } \implies x \text{ ist optimal } }

oder in verneinter Form

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \text{ ist nicht optimal } \implies K \text{ gilt nicht } } .

Ein Optimalitätskriterium heißt Optimalitätskriterium erster Ordnung (auch Bedingung erster Ordnung oder kurz B.e.O.; englisch first order condition oder kurz FOC), wenn es Forderungen an die ersten Ableitungen der auftretenden Funktionen stellt. Dementsprechend ist ein Optimalitätskriterium zweiter Ordnung (auch Bedingung zweiter Ordnung oder kurz B.z.O. bzw. B.zw.O., englisch second order condition oder kurz SOC) eines, das Anforderungen an die zweiten Ableitungen stellt. Teilweise werden auch noch Anforderungen an höhere Ableitungen gestellt.

Zu beachten ist, dass noch nicht weiter präzisiert wurde, was genau „optimal“ bedeutet. Dies kann sowohl maximal, minimal oder auch global oder lokal optimal sein.

Beispiele

Notwendig erster Ordnung

Ein typisches Beispiel für ein notwendiges Optimalitätskriterium erster Ordnung findet sich in der unrestringierten Optimierung. Nimmt eine stetig differenzierbare Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f } in einem Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x } ein lokales Minimum an, so verschwindet die Ableitung in diesem Punkt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f'(x)=0 } . Die Problemklasse wäre in diesem Fall das Finden eines Minimums bei stetig differenzierbaren Funktionen auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R} } , der Optimalitätsbegriff der des lokalen Minimums.

Hinreichend erster Ordnung

Ein hinreichendes Kriterium erster Ordnung findet sich bei der Minimierung von strikt konvexen Funktionen. Verschwindet hier die Ableitung in einem Punkt, so ist dieser Punkt ein globales Minimum.

Notwendig zweiter Ordnung

Das Bestimmen von Wendepunkten benutzt notwendige Bedingungen zweiter Ordnung. Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x } ein Wendepunkt, so verschwindet die zweite Ableitung in diesem Punkt.

Hinreichend zweiter Ordnung

Beispiel hierfür wäre das Bestimmen eines lokalen Minimums einer zweimal stetig differenzierbaren Funktion. Ist die erste Ableitung gleich null und die zweite Ableitung echt größer null, dann handelt es sich um ein lokales Minimum.

Wichtige Optimalitätskriterien

Eines der wichtigsten Optimalitätskriterien in der nichtlinearen Optimierung sind die Karush-Kuhn-Tucker-Bedingungen. Im allgemeinen Fall sind sie ein notwendiges Kriterium erster Ordnung. Allerdings benötigen sie zur Geltung noch gewisse Regularitätsvoraussetzungen wie die Abadie CQ, die MFCQ oder die LICQ.

Ist das gestellte Problem konvex, so sind die Karush-Kuhn-Tucker-Bedingungen auch hinreichend für die Optimalität. Ein etwas schwächeres notwendiges Optimalitätskriterium sind die Fritz-John-Bedingungen, diese kommen ohne zusätzliche Regularitätsannahmen aus.

Literatur

• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2. https://books.google.de/books?id=spmzFyso_b8C&hl=de