Karush-Kuhn-Tucker-Bedingungen

Die Karush-Kuhn-Tucker-Bedingungen sind ein notwendiges Optimalitätskriterium erster Ordnung in der nichtlinearen Optimierung. Sie sind die Verallgemeinerung der notwendigen Bedingung $\nabla f(x)={\vec {0}}$ 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. Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker.

Rahmenbedingungen

Gegeben seien $m+l+1$ stetig differenzierbare Funktionen $f,g_{1},\ldots ,g_{m},h_{1},\ldots ,h_{l}\!:D\rightarrow \mathbb {R}$, wobei $D$ eine nicht-leere offene Teilmenge von $\mathbb {R} ^{n}$ ist. Die KKT-Bedingungen ermöglichen Aussagen über ein Optimierungsproblem der Form

$\min _{x\in C}f(x),$

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

$g_{i}(x)\leq 0,~1\leq i\leq m,$

$h_{j}(x)=0,~1\leq j\leq l,$

erfüllen.

Aussage

Karush-Kuhn-Tucker-Bedingungen

Ein Punkt $(x^{*},\mu ^{*},\lambda ^{*})\in C\times \mathbb {R} ^{m}\times \mathbb {R} ^{l}$ heißt Karush-Kuhn-Tucker-Punkt oder kurz KKT-Punkt des obigen Optimierungsproblems, wenn er die folgenden Bedingungen erfüllt:

${\begin{alignedat}{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^{*})\leq 0,&&{\text{für }}i=1,\ldots ,m,\\&\mu _{i}^{*}\geq 0,&&{\text{für }}i=1,\ldots ,m,\\&\mu _{i}^{*}g_{i}(x^{*})=0,&&{\text{für }}i=1,\ldots ,m.\end{alignedat}}$

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

$L(x,\mu ,\lambda ):=f(x)+\sum _{i=1}^{m}\mu _{i}g_{i}(x)+\sum _{j=1}^{l}\lambda _{j}h_{j}(x)$,

so kann man die erste Zeile formulieren als $\nabla _{x}L(x^{*},\mu ^{*},\lambda ^{*})=0$. Die zweite und dritte Zeile fordert, dass $x^{*}$ 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 $D=\mathbb {R} _{\geq 0}^{n}$, so benötigt man nicht zwangsläufig die Formulierung über $g_{i}(x^{*})\leq 0$ und zugehörige Lagrange-Multiplikatoren. Stattdessen lauten die KKT dann:

${\begin{alignedat}{3}&\nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}^{*}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}^{*}\nabla h_{j}(x^{*}){\geq }0,\\&g_{i}(x^{*})\leq 0,&&{\text{für }}i=1,\ldots ,m,\\&h_{j}(x^{*})=0,&&{\text{für }}j=1,\ldots ,l,\\&\mu _{i}^{*}\geq 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}^{*}\geq 0,&&{\text{für }}p=1,\ldots ,n.\\\end{alignedat}}$

Optimalitätskriterium

Ist der Punkt $x^{*}$ lokales Minimum des Optimierungsproblems und erfüllt er gewisse Regularitätsvoraussetzungen (siehe unten), so gibt es $\mu ^{*},\lambda ^{*}$, so dass $(x^{*},\mu ^{*},\lambda ^{*})$ ein KKT-Punkt ist. Somit sind die KKT-Bedingungen ein notwendiges Optimalitätskriterium. Im Allgemeinen ist $\mu ^{*},\lambda ^{*}$ 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 constraint qualifications genannt.

Beispiele für constraint qualifications sind:

• Abadie CQ: Der Tangentialkegel und der linearisierte Tangentialkegel stimmen in ${\hat {x}}$ ü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 ${\hat {x}}$. Diese CQ liefert Eindeutigkeit bei $\mu ^{*},\lambda ^{*}$.
• Mangasarian-Fromovitz – Mangasarian-Fromovitz constraint qualification (MFCQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv-linear unabhängig im Punkt ${\hat {x}}$.
• 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 ${\hat {x}}$ 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 ${\hat {x}}$ gilt: falls eine positiv-lineare Abhängigkeit im Punkt ${\hat {x}}$ vorliegt, dann gibt es eine positiv-lineare Abhängigkeit in einer Umgebung von ${\hat {x}}$.

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

${\mbox{LICQ}}\Rightarrow {\mbox{MFCQ}}\Rightarrow {\mbox{CPLD}}$ und ${\mbox{LICQ}}\Rightarrow {\mbox{CRCQ}}\Rightarrow {\mbox{CPLD}}$,

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

Konvexe Optimierung

Handelt es sich bei dem Optimierungsproblem um ein konvexes Optimierungsproblem, sind also $f,g_{1},\ldots ,g_{m}$ konvex und $h_{1},\ldots ,h_{l}$ 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

Ist die Zielfunktion $f(x)$ und die Definitionsmenge $D$ konvex und sind alle Restriktionen affin, sprich ist $g_{i}(x)=a_{i}^{T}x-b_{i}$ und $h_{j}(x)=a_{j}^{T}x-b_{j}$, 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

$\min _{x\in X}[-(x_{1}+1)^{2}-(x_{2}+2)^{2}]$

mit der Restriktionsmenge

$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\}$.

Ein lokales Minimum befindet sich im Punkt $x^{*}=(2,0)$. Zuerst überprüft man eine der Regularitätsbedingungen, in diesem Fall LICQ: im lokalen Optimum sind die Ungleichungsrestriktionen $g_{1},g_{2}$ aktiv und deren Gradienten $\nabla g_{1}(x^{*})=(0,1)^{T},\nabla g_{2}(x^{*})=(4,-1)^{T}$ 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 $g_{3}(x^{*})<0$ ist, also ist aufgrund der KKT-Bedingung $\mu _{3}^{*}g_{3}(x^{*})=0$ auf jeden Fall $\mu _{3}^{*}=0$. Die anderen Werte des KKT-Punktes ergeben sich aus dem Gleichungssystem der Gradienten am Punkt $x^{*}$

${\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}}$

zu $\mu _{1}^{*}={\frac {11}{2}},\,\mu _{2}^{*}={\frac {3}{2}}$. Somit ist ein KKT-Punkt gegeben als $(2,0,{\frac {11}{2}},{\frac {3}{2}},0)$.

Da das Problem nicht konvex ist, gilt die Umkehrung jedoch nicht: der Punkt $(-1,-2,0,0,0)$ 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 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

Weblinks

• 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