Quelltext der Seite Karush-Kuhn-Tucker-Bedingungen

Die '''Karush-Kuhn-Tucker-Bedingungen''' sind ein [[Optimalitätskriterium|notwendiges Optimalitätskriterium erster Ordnung]] in der [[Nichtlineare Optimierung|nichtlinearen Optimierung]]. Sie sind die Verallgemeinerung der notwendigen Bedingung <math>\nabla f(x) = \vec{0}</math> von [[Optimierungsproblem|Optimierungsproblemen]] ohne Nebenbedingungen und der [[Lagrange-Multiplikator]]en von Optimierungsproblemen unter Gleichungsnebenbedingungen. Sie wurden zum ersten Mal 1939 in der allerdings unveröffentlichten Master-Arbeit von [[William Karush]] aufgeführt.<ref>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</ref> Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von [[Harold W. Kuhn]] und [[Albert W. Tucker]].<ref>Kuhn, Tucker, Nonlinear programming, in: Jerzey Neyman, Proc. 2. Berkeley Symp. Math. Statistics and Probability, University of California Press 1951, S. 481–492</ref>

== Rahmenbedingungen ==
Gegeben seien <math>m+l+1</math> [[stetig differenzierbar|stetig differenzierbare]] Funktionen <math>f,g_1,\ldots,g_m,h_1,\ldots,h_l\!:D\rightarrow\mathbb{R}</math>, wobei <math>D</math> eine nicht-leere offene Teilmenge von <math>\mathbb{R}^n</math> ist. Die KKT-Bedingungen ermöglichen Aussagen über ein Optimierungsproblem der Form

:<math> \min_{x \in C}f(x), </math>

wobei <math>C\subseteq D</math> die Menge aller Punkte in <math>\mathbb{R}^n</math> ist, welche die Nebenbedingungen

:<math>g_i(x) \leq 0, ~ 1 \leq i \leq m,</math>
:<math>h_j(x) = 0, ~ 1 \leq j \leq l,</math>

erfüllen.

== Aussage ==
=== Karush-Kuhn-Tucker-Bedingungen ===
Ein Punkt <math> (x^*,\mu^*,\lambda^*)\in C\times\mathbb{R}^m\times\mathbb{R}^l</math>  heißt '''Karush-Kuhn-Tucker-Punkt''' oder kurz '''KKT-Punkt''' des obigen Optimierungsproblems, wenn er die folgenden Bedingungen erfüllt:
:<math>\begin{alignat}{3}
&\nabla f(x^*) + \sum_{i=1}^m \mu^*_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda^*_j \nabla h_j(x^*)=0, \\
&h_j(x^*) = 0, &&\text{für }j = 1, \ldots, l, \\ 
&g_i(x^*) \le 0, &&\text{für } i = 1, \ldots, m, \\
&\mu^*_i \ge 0, &&\text{für }i = 1, \ldots, m, \\
&\mu^*_i g_i (x^*) = 0, &&\text{für }i = 1,\ldots, m.
\end{alignat}
</math>
Diese Bedingungen werden die '''Karush-Kuhn-Tucker-Bedingungen''' oder kurz '''KKT-Bedingungen''' genannt. Verwendet man alternativ die Lagrange-Funktion
:<math> L(x,\mu,\lambda):= f(x)+\sum_{i=1}^m\mu_ig_i(x)+\sum_{j=1}^l\lambda_jh_j(x)</math>,

so kann man die erste Zeile formulieren als <math> \nabla_xL(x^*, \mu^*, \lambda^*)=0 </math>. Die zweite und dritte Zeile fordert, dass <math> x^* </math> zulässig für das (primale) Problem ist, die vierte fordert Zulässigkeit der dualen Variable für das [[Lagrange-Dualität|duale Problem]] und die letzte Zeile [[Komplementaritätsbedingung|Komplementarität]].

Ist der Definitionsbereich <math> D = \mathbb{R}^{n}_{\ge 0} </math>, so benötigt man nicht zwangsläufig die Formulierung über <math>g_i(x^*) \le 0</math> und zugehörige Lagrange-Multiplikatoren. Stattdessen lauten die KKT dann:
:<math>\begin{alignat}{3}
&\nabla f(x^*) + \sum_{i=1}^m \mu^*_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda^*_j \nabla h_j(x^*){\ge}0,\\
&g_i(x^*) \le 0, &&\text{für } i = 1, \ldots, m,\\
&h_j(x^*) = 0, &&\text{für } j = 1, \ldots, l ,\\
&\mu^*_i \ge 0, &&\text{für } i = 1, \ldots, m,\\
&\mu^*_i g_i (x^*) = 0, &&\text{für }\; i = 1,\ldots,m,\\
&x^*\cdot\left(\nabla f(x^*) + \sum_{i=1}^m \mu^*_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda^*_j \nabla h_j(x^*)\right)=0, &\;&\text{für } p=1,\ldots,n,\\
&x_p^* \ge 0, &&\text{für } p = 1, \ldots, n.\\
\end{alignat}</math>

=== Optimalitätskriterium ===

Ist der Punkt <math> x^* </math> lokales Minimum des Optimierungsproblems und erfüllt er gewisse Regularitätsvoraussetzungen (siehe unten), so gibt es <math> \mu^*, \lambda^* </math>, so dass <math> (x^*, \mu^*, \lambda^*) </math> ein KKT-Punkt ist. Somit sind die KKT-Bedingungen ein [[Optimalitätskriterium|notwendiges Optimalitätskriterium]]. Im Allgemeinen ist <math> \mu^*, \lambda^* </math> nicht eindeutig festgelegt.

== Regularitätsvoraussetzungen ==
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 {{lang|en|constraint qualifications}} genannt.

Beispiele für {{lang|en|constraint qualifications}} sind:
* ''[[Abadie CQ]]'': Der [[Tangentialkegel]] und der [[linearisierter Tangentialkegel|linearisierte Tangentialkegel]] stimmen in <math>\hat{x}</math> überein.
* ''[[Linear independence constraint qualification|Lineare Unabhängigkeit – {{lang|en|linear independence constraint qualification}} (LICQ):]]'' Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind [[Lineare Unabhängigkeit|linear unabhängig]] im Punkt <math>\hat{x}</math>. Diese CQ liefert Eindeutigkeit bei <math> \mu^*, \lambda^* </math>.
* ''[[MFCQ|Mangasarian-Fromovitz – {{lang|en|Mangasarian-Fromovitz constraint qualification}} (MFCQ):]]'' Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv-linear unabhängig im Punkt <math>\hat{x}</math>.
* ''Konstanter Rang – {{lang|en|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 <math>\hat{x}</math> konstant.
* ''Konstante positiv-lineare Abhängigkeit – {{lang|en|constant positive-linear dependence constraint qualification}} (CPLD):'' Für jede Untermenge der Gradienten der aktiven Ungleichungsbedingungen und der Gradienten der Gleichungsbedingungen im Punkt <math>\hat{x}</math> gilt: falls eine positiv-lineare Abhängigkeit im Punkt <math>\hat{x}</math> vorliegt, dann gibt es eine positiv-lineare Abhängigkeit in einer Umgebung von <math>\hat{x}</math>.
Speziell für [[konvexe Optimierung]]sprobleme und [[Fast-konvexe Funktion|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

:<math>\mbox{LICQ} \Rightarrow \mbox{MFCQ} \Rightarrow \mbox{CPLD}</math> und <math>\mbox{LICQ} \Rightarrow \mbox{CRCQ} \Rightarrow \mbox{CPLD}</math>,

obwohl MFCQ nicht äquivalent zu CRCQ ist. In der Praxis werden schwächere {{lang|en|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 ==
=== Konvexe Optimierung ===
Handelt es sich bei dem Optimierungsproblem um ein [[Konvexe Optimierung|konvexes Optimierungsproblem]], sind also <math>f,g_1,\ldots,g_m</math> konvex und <math>h_1,\ldots,h_l</math> 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 [[Optimalitätskriterium|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 ===
Ist die Zielfunktion <math> f(x) </math> und die Definitionsmenge <math> D </math> konvex und sind alle Restriktionen affin, sprich ist <math> g_i(x)=a_i^Tx-b_i </math> und <math> h_j(x)=a_j^Tx-b_j </math>, so ist ohne weitere Regularitätsvoraussetzungen ein KKT-Punkt äquivalent zum globalen Minimum.

=== Allgemeine Zielfunktion mit linearen Restriktionen ===
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 ==
Betrachten wir als Beispiel das nichtlineare Optimierungsproblem
:<math> \min_{x \in X}[-(x_1+1)^2-(x_2+2)^2] </math>

mit der Restriktionsmenge
:<math> X= \{x \in \mathbb{R}^2 \, | \, g_1(x)=x_2\leq 0, \, g_2(x)=x_1^2-x_2-4\leq 0, \, g_3(x)=-x_1^2+x_2+1\leq 0\} </math>.

Ein lokales Minimum befindet sich im Punkt <math> x^*=(2,0) </math>. Zuerst überprüft man eine der Regularitätsbedingungen, in diesem Fall [[LICQ]]: im lokalen Optimum sind die Ungleichungsrestriktionen <math> g_1, g_2 </math> aktiv und deren Gradienten <math> \nabla g_1(x^*)=(0,1)^T, \nabla g_2(x^*)=(4,-1)^T </math> 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 <math> g_3(x^*)<0 </math> ist, also ist aufgrund der KKT-Bedingung <math> \mu_3^*g_3(x^*)=0 </math> auf jeden Fall <math> \mu_3^* =0</math>. Die anderen Werte des KKT-Punktes ergeben sich aus dem Gleichungssystem der Gradienten am Punkt <math> x^* </math>
:<math> \begin{pmatrix} -6 \\ -4 \end{pmatrix}+\mu_1^*\begin{pmatrix} 0 \\ 1 \end{pmatrix}+\mu_2^*\begin{pmatrix} 4 \\ -1 \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \end{pmatrix} </math>

zu <math> \mu_1^*=\tfrac{11}{2}, \,\mu_2^*=\tfrac{3}{2} </math>. Somit ist ein KKT-Punkt gegeben als <math> (2,0,\tfrac{11}{2},\tfrac{3}{2},0) </math>.

Da das Problem nicht konvex ist, gilt die Umkehrung jedoch nicht: der Punkt <math> (-1,-2,0,0,0) </math> ist zwar ein KKT-Punkt des Problems, aber kein Optimum.

== Verallgemeinerungen ==
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 [[Lagrange-Dualität|Sattelpunktkriterien der Lagrange-Funktion]].

== 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 https://books.google.de/books?id=spmzFyso_b8C&hl=de]
== Weblinks ==
* [https://web.stanford.edu/~boyd/cvxbook/ Buch ''Convex Optimization'' von Stephen Boyd und Lieven Vandenberghe (PDF)] (engl.)
* Buch Bazaraa, Mokhtar S. ; Sherali, Hanif D. ; Shetty, C. M.: Nonlinear Programming. 2. Hoboken, NJ, USA : [[John Wiley & Sons]], Inc., 2006. – 871 S. [[doi:10.1002/0471787779]]. – ISBN 9780471787778

== Einzelnachweise ==
<references />

[[Kategorie:Nichtlineare Optimierung]]