Karush-Kuhn-Tucker-Bedingungen

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Karush-Kuhn-Tucker-Bedingungen sind ein notwendiges Optimalitätskriterium erster Ordnung in der nichtlinearen Optimierung. Sie sind die Verallgemeinerung der notwendigen Bedingung von Optimierungsproblemen ohne Nebenbedingungen und der Lagrange-Multiplikatoren von Optimierungsproblemen unter Gleichungsnebenbedingungen. Sie wurden zum ersten Mal 1939 in der allerdings unveröffentlichten Master-Arbeit von William Karush aufgeführt.[1] Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker.[2]

Rahmenbedingungen

[Bearbeiten | Quelltext bearbeiten]

Gegeben seien stetig differenzierbare Funktionen , wobei eine nicht-leere offene Teilmenge von ist. Die KKT-Bedingungen ermöglichen Aussagen über ein Optimierungsproblem der Form

wobei die Menge aller Punkte in ist, welche die Nebenbedingungen

erfüllen.

Karush-Kuhn-Tucker-Bedingungen

[Bearbeiten | Quelltext bearbeiten]

Ein Punkt heißt Karush-Kuhn-Tucker-Punkt oder kurz KKT-Punkt des obigen Optimierungsproblems, wenn er die folgenden Bedingungen erfüllt:

Diese Bedingungen werden die Karush-Kuhn-Tucker-Bedingungen oder kurz KKT-Bedingungen genannt. Verwendet man alternativ die Lagrange-Funktion

,

so kann man die erste Zeile formulieren als . Die zweite und dritte Zeile fordert, dass zulässig für das (primale) Problem ist, die vierte fordert Zulässigkeit der dualen Variable für das duale Problem und die letzte Zeile Komplementarität.

Ist der Definitionsbereich , so benötigt man nicht zwangsläufig die Formulierung über und zugehörige Lagrange-Multiplikatoren. Stattdessen lauten die KKT dann:

Optimalitätskriterium

[Bearbeiten | Quelltext bearbeiten]

Ist der Punkt lokales Minimum des Optimierungsproblems und erfüllt er gewisse Regularitätsvoraussetzungen (siehe unten), so gibt es , so dass ein KKT-Punkt ist. Somit sind die KKT-Bedingungen ein notwendiges Optimalitätskriterium. Im Allgemeinen ist nicht eindeutig festgelegt.

Regularitätsvoraussetzungen

[Bearbeiten | Quelltext bearbeiten]

Es gibt unterschiedlichste Regularitätsbedingungen, die sicherstellen, dass die KKT-Bedingungen gelten. Sie unterscheiden sich hauptsächlich in ihrer Allgemeingültigkeit und der Leichtigkeit ihrer Anwendung und Überprüfbarkeit. In Anlehnung an das Englische werden sie auch constraint qualifications genannt.

Beispiele für constraint qualifications sind:

  • Abadie CQ: Der Tangentialkegel und der linearisierte Tangentialkegel stimmen in überein.
  • Lineare Unabhängigkeit – linear independence constraint qualification (LICQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind linear unabhängig im Punkt . Diese CQ liefert Eindeutigkeit bei .
  • Mangasarian-Fromovitz – Mangasarian-Fromovitz constraint qualification (MFCQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv-linear unabhängig im Punkt .
  • Konstanter Rang – constant rank constraint qualification (CRCQ): Für jede Untermenge der Gradienten der aktiven Ungleichungsbedingungen und der Gradienten der Gleichungsbedingungen ist der Rang in einer Umgebung von konstant.
  • Konstante positiv-lineare Abhängigkeit – constant positive-linear dependence constraint qualification (CPLD): Für jede Untermenge der Gradienten der aktiven Ungleichungsbedingungen und der Gradienten der Gleichungsbedingungen im Punkt gilt: falls eine positiv-lineare Abhängigkeit im Punkt vorliegt, dann gibt es eine positiv-lineare Abhängigkeit in einer Umgebung von .

Speziell für konvexe Optimierungsprobleme und fast konvexe Funktionen gibt es die

  • Slater-Bedingung: Es gibt einen zulässigen Punkt, der strikt zulässig bezüglich der Ungleichungsrestriktionen ist. Sie liefert die Regularität aller Punkte des Problems und nicht nur die des untersuchten Punktes.

Man kann zeigen, dass die folgenden beiden Folgerungsstränge gelten

und ,

obwohl MFCQ nicht äquivalent zu CRCQ ist. In der Praxis werden schwächere constraint qualifications bevorzugt, da diese stärkere Optimalitäts-Bedingungen liefern. Insbesondere können die constraint qualifications auch genutzt werden, um sicherzustellen, dass die KKT-Bedingungen mit den Fritz-John-Bedingungen übereinstimmen.

Konvexe Optimierung

[Bearbeiten | Quelltext bearbeiten]

Handelt es sich bei dem Optimierungsproblem um ein konvexes Optimierungsproblem, sind also konvex und affin, so lassen sich stärkere Aussagen treffen. Einerseits kann man dann als Regularitätsbedingung die Slater-Bedingung verwenden, welche die Regularität aller Punkte des Problems liefern, andererseits ist bei konvexen Problemen die KKT-Bedingung auch hinreichendes Optimalitätskriterium. Jeder Punkt, der ein KKT-Punkt ist, ist also lokales (und aufgrund der Konvexität sogar globales) Minimum. Insbesondere ist dazu keine Regularitätsvoraussetzung nötig.

Konvexe Zielfunktion mit linearen Restriktionen

[Bearbeiten | Quelltext bearbeiten]

Ist die Zielfunktion und die Definitionsmenge konvex und sind alle Restriktionen affin, sprich ist und , so ist ohne weitere Regularitätsvoraussetzungen ein KKT-Punkt äquivalent zum globalen Minimum.

Allgemeine Zielfunktion mit linearen Restriktionen

[Bearbeiten | Quelltext bearbeiten]

Sind die Zielfunktion und der Definitionsbereich im Rahmen der obigen Voraussetzungen beliebig und alle Restriktionen affin, so ist die Abadie CQ automatisch erfüllt, da die Linearisierung der linearen Funktionen wieder die Funktionen selbst liefert. Damit ist in diesem Fall ohne weitere Voraussetzungen an die Regularität ein lokales Optimum immer ein KKT-Punkt.

Betrachten wir als Beispiel das nichtlineare Optimierungsproblem

mit der Restriktionsmenge

.

Ein lokales Minimum befindet sich im Punkt . Zuerst überprüft man eine der Regularitätsbedingungen, in diesem Fall LICQ: im lokalen Optimum sind die Ungleichungsrestriktionen aktiv und deren Gradienten sind linear unabhängig. Somit ist die LICQ erfüllt, es existiert also ein KKT-Punkt. Um diesen zu berechnen, stellen wir zunächst fest, dass ist, also ist aufgrund der KKT-Bedingung auf jeden Fall . Die anderen Werte des KKT-Punktes ergeben sich aus dem Gleichungssystem der Gradienten am Punkt

zu . Somit ist ein KKT-Punkt gegeben als .

Da das Problem nicht konvex ist, gilt die Umkehrung jedoch nicht: der Punkt ist zwar ein KKT-Punkt des Problems, aber kein Optimum.

Verallgemeinerungen

[Bearbeiten | Quelltext bearbeiten]

Eine Verallgemeinerung der KKT-Bedingungen sind die Fritz-John-Bedingungen. Sie kommen ohne Regularitätsvoraussetzungen aus, liefern jedoch eine schwächere Aussage. Für konvexe Optimierungsprobleme, bei denen die Funktionen nicht stetig differenzierbar sind, gibt es außerdem die Sattelpunktkriterien der Lagrange-Funktion.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Die Arbeit ist dargestellt in H. Kuhn, Nonlinear Programming. A historical view, in: R. W. Cottle, C. E. Lemke, Nonlinear Programming, SIAM-AMS Proc. 9, American Mathematical Society 1976, S. 1–26
  2. Kuhn, Tucker, Nonlinear programming, in: Jerzey Neyman, Proc. 2. Berkeley Symp. Math. Statistics and Probability, University of California Press 1951, S. 481–492