Karush-Kuhn-Tucker-Bedingungen

(Weitergeleitet von KKT-Bedingungen)

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

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

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

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

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.

Spezialfälle

Bearbeiten

Konvexe Optimierung

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

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

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.

Beispiel

Bearbeiten

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

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.

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

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