Optimalitätskriterium

Begriff der mathematischen Optimierung

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

Bearbeiten

Sei   ein zulässiger Punkt eines Optimierungsproblems und   ein gewisses Kriterium.   heißt notwendiges Optimalitätskriterium für eine bestimmte Klasse von Problemen, wenn folgende Aussage gilt:

 .

oder in verneinter Form

 

  heißt ein hinreichendes Optimalitätskriterium, wenn folgende Aussage gilt:

 

oder in verneinter Form

 .

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

Bearbeiten

Notwendig erster Ordnung

Bearbeiten

Ein typisches Beispiel für ein notwendiges Optimalitätskriterium erster Ordnung findet sich in der unrestringierten Optimierung. Nimmt eine stetig differenzierbare Funktion   in einem Punkt   ein lokales Minimum an, so verschwindet die Ableitung in diesem Punkt:  . Die Problemklasse wäre in diesem Fall das Finden eines Minimums bei stetig differenzierbaren Funktionen auf  , der Optimalitätsbegriff der des lokalen Minimums.

Hinreichend erster Ordnung

Bearbeiten

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

Bearbeiten

Das Bestimmen von Wendepunkten benutzt notwendige Bedingungen zweiter Ordnung. Ist   ein Wendepunkt, so verschwindet die zweite Ableitung in diesem Punkt.

Hinreichend zweiter Ordnung

Bearbeiten

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

Bearbeiten

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

Bearbeiten