Karush–Kuhn–Tucker-Bedingungen - Karush–Kuhn–Tucker conditions

In mathematischer Optimierung , die Karush-Kuhn-Tucker (KKT) Bedingungen , die auch als die bekannten Kuhn-Tucker - Bedingungen sind erster Ableitung Tests (manchmal erste Ordnung genannt notwendige Bedingungen für eine Lösung in) nicht - linearer Programmierung sein optimal , dass ein Teil vorgesehen Regelmäßigkeitsbedingungen erfüllt sind.

Unter Zulassen von Ungleichheitsbeschränkungen verallgemeinert der KKT-Ansatz zur nichtlinearen Programmierung die Methode der Lagrange-Multiplikatoren , die nur Gleichheitsbeschränkungen zulässt. Ähnlich dem Lagrange-Ansatz wird das eingeschränkte Maximierungs-(Minimierungs-)Problem in eine Lagrange-Funktion umgeschrieben, deren optimaler Punkt ein Sattelpunkt ist , dh ein globales Maximum (Minimum) über dem Bereich der Auswahlvariablen und ein globales Minimum (Maximum) über die Multiplikatoren, weshalb das Karush-Kuhn-Tucker-Theorem manchmal auch als Sattelpunkt-Theorem bezeichnet wird.

Die KKT-Bedingungen wurden ursprünglich nach Harold W. Kuhn und Albert W. Tucker benannt , die die Bedingungen erstmals 1951 veröffentlichten. Spätere Wissenschaftler entdeckten, dass William Karush die notwendigen Bedingungen für dieses Problem 1939 in seiner Masterarbeit formuliert hatte .

Nichtlineares Optimierungsproblem

Betrachten Sie das folgende nichtlineare Minimierungs- oder Maximierungsproblem :

optimieren ${\displaystyle f(\mathbf{x})}$

unterliegt

${\displaystyle g_{i}(\mathbf{x})\leq 0,}$

${\displaystyle h_{j}(\mathbf{x} )=0.}$

wobei die Optimierungsvariablen von einer gewählten konvexen Teilmenge von , sind die Ziel oder Utility - Funktion sind die Ungleichheits Constraint - Funktionen und sind die Gleichheit Constraint - Funktionen. Die Zahlen von Ungleichheiten und Gleichheiten werden durch bezeichnet und jeweils. Entsprechend dem eingeschränkten Optimierungsproblem kann man die Lagrangesche Funktion bilden ${\displaystyle\mathbf{x}\in\mathbf{X}}$${\displaystyle \mathbb{R} ^{n}}$${\displaystyle f}$${\displaystyle g_{i}\ (i=1,\ldots,m)}$${\displaystyle h_{j}\ (j=1,\ldots,\ell)}$${\displaystyle m}$${\displaystyle \ell}$

${\displaystyle L(\mathbf {x} ,\mathbf {\mu} ,\mathbf {\lambda} )=f(\mathbf {x})+\mathbf {\mu} ^{\top }\mathbf {g } (\mathbf{x})+\mathbf{\lambda} ^{\top}\mathbf{h} (\mathbf{x})}$

wo , . Der Satz von Karush-Kuhn-Tucker besagt dann Folgendes. ${\displaystyle \mathbf{g} (\mathbf{x})=\left(g_{1}(\mathbf{x}),\ldots,g_{m}(\mathbf{x})\right)^{ \oben }}$${\displaystyle \mathbf {h} (\mathbf {x} )=\left(h_{1}(\mathbf{x}),\ldots,h_{\ell}(\mathbf{x})\right)^ {\oben }}$

Satz. Wenn ein Sattelpunkt von in ist , dann ist ein optimaler Vektor für das obige Optimierungsproblem. Nehmen wir an , und , sind konvex in und , dass es existiert , so dass . Dann wird einem optimalen Vektor für das obige Optimierungsproblem ein nicht negativer Vektor zugeordnet , der ein Sattelpunkt von ist . ${\displaystyle (\mathbf{x}^{\ast},\mathbf{\mu}^{\ast})}$${\displaystyle L(\mathbf{x},\mathbf{\mu})}$${\displaystyle\mathbf{x}\in\mathbf{X}}$${\displaystyle \mathbf {\mu} \geq \mathbf {0} }$${\displaystyle\mathbf{x}^{\ast}}$${\displaystyle f(\mathbf{x})}$${\displaystyle g_{i}(\mathbf{x})}$${\displaystyle i=1,\ldots,m}$${\displaystyle\mathbf{x}}$${\displaystyle\mathbf{x}_{0}\in\mathbf{X}}$${\displaystyle \mathbf{g} (\mathbf{x}_{0})<0}$${\displaystyle\mathbf{x}^{\ast}}$${\displaystyle \mathbf {\mu} ^{\ast}}$${\displaystyle L(\mathbf{x}^{\ast},\mathbf{\mu}^{\ast})}$${\displaystyle L(\mathbf{x},\mathbf{\mu})}$

Da die Idee dieses Ansatzes darin besteht, eine unterstützende Hyperebene auf der zulässigen Menge zu finden , verwendet der Beweis des Karush-Kuhn-Tucker-Theorems den Hyperebenen-Separationssatz . ${\displaystyle \mathbf {\Gamma} =\left\{\mathbf {x} \in\mathbf {X} :g_{i}(\mathbf {x} )\leq 0,i=1,\ldots ,m \Recht\}}$

Das den KKT-Bedingungen entsprechende Gleichungs- und Ungleichungssystem wird in der Regel nicht direkt gelöst, außer in den wenigen Spezialfällen, in denen analytisch eine geschlossene Lösung hergeleitet werden kann. Im Allgemeinen können viele Optimierungsalgorithmen als Methoden zur numerischen Lösung des KKT-Gleichungs- und Ungleichungssystems interpretiert werden.

Notwendige Bedingungen

Nehmen Sie an, dass die Zielfunktion und die Randbedingungsfunktionen und an einem Punkt stetig differenzierbar sind . Ist ein lokales Optimum und das Optimierungsproblem erfüllt einige Regularitätsbedingungen (siehe unten), dann existieren Konstanten und , sogenannte KKT-Multiplikatoren, sodass die folgenden vier Gruppen von Bedingungen gelten: ${\displaystyle f:\mathbb{R}^{n}\rightarrow\mathbb{R}}$${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle x^{*}\in\mathbb{R}^{n}}$${\displaystyle x^{*}}$${\displaystyle \mu_{i}\ (i=1,\ldots,m)}$${\displaystyle \lambda_{j}\ (j=1,\ldots,\ell)}$

Stationarität

Zur Minimierung :${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})+\sum_{i=1}^{m}\mu_{i}\nabla g_{i}(x^{*})+\sum_{ j=1}^{\ell}\lambda_{j}\nabla h_{j}(x^{*})=\mathbf {0}}$

Zur Maximierung :${\displaystyle f(x)}$${\displaystyle -\nabla f(x^{*})+\sum_{i=1}^{m}\mu_{i}\nabla g_{i}(x^{*})+\sum_ {j=1}^{\ell}\lambda_{j}\nabla h_{j}(x^{*})=\mathbf {0}}$

Erste Machbarkeit

${\displaystyle g_{i}(x^{*})\leq 0,{\text{ for}}i=1,\ldots ,m}$

${\displaystyle h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell\,\!}$

Doppelte Machbarkeit

${\displaystyle \mu_{i}\geq 0,{\text{ für }}i=1,\ldots,m}$

Komplementäre Schlaffheit

${\displaystyle \sum_{i=1}^{m}\mu_{i}g_{i}(x^{*})=0.}$

Die letzte Bedingung wird manchmal in der entsprechenden Form geschrieben: ${\displaystyle \mu_{i}g_{i}(x^{*})=0,{\text{ for }}i=1,\ldots,m.}$

Im speziellen Fall , dh wenn keine Ungleichheitsbeschränkungen vorliegen, werden die KKT-Bedingungen zu Lagrange-Bedingungen und die KKT-Multiplikatoren werden Lagrange-Multiplikatoren genannt . ${\displaystyle m=0}$

Wenn einige der Funktionen nicht differenzierbar sind, stehen subdifferentielle Versionen von Karush-Kuhn-Tucker (KKT)-Bedingungen zur Verfügung.

Matrixdarstellung

Die notwendigen Bedingungen können mit Jacobi-Matrizen der Constraint-Funktionen geschrieben werden. Sei definiert als und sei definiert als . Lassen Sie und . Dann können die notwendigen Bedingungen geschrieben werden als: ${\displaystyle\mathbf{g}(x):\,\!\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}}$${\displaystyle\mathbf{g}(x)=\left(g_{1}(x),\ldots ,g_{m}(x)\right)^{\top }}$${\displaystyle\mathbf{h}(x):\,\!\mathbb{R}^{n}\rightarrow\mathbb{R}^{\ell}}$${\displaystyle \mathbf {h} (x)=\left(h_{1}(x),\ldots ,h_{\ell}(x)\right)^{\top }}$${\displaystyle {\boldsymbol {\mu}}=\left(\mu_{1},\ldots,\mu_{m}\right)^{\top }}$${\displaystyle {\boldsymbol {\lambda}}=\left(\lambda_{1},\ldots,\lambda_{\ell}\right)^{\top }}$

Stationarität

Zur Maximierung :${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})-D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu}}-D\mathbf {h} (x^ {*})^{\top }{\boldsymbol {\lambda}}=\mathbf {0}}$

Zur Minimierung :${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})+D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu}}+D\mathbf {h} (x^ {*})^{\top }{\boldsymbol {\lambda}}=\mathbf {0}}$

Erste Machbarkeit

${\displaystyle \mathbf {g} (x^{*})\leq \mathbf {0} }$

${\displaystyle \mathbf{h} (x^{*})=\mathbf{0} }$

Doppelte Machbarkeit

${\displaystyle {\boldsymbol {\mu}}\geq\mathbf {0}}$

Komplementäre Schlaffheit

${\displaystyle {\boldsymbol {\mu}}^{\top}\mathbf {g} (x^{*})=0.}$

Regelmäßigkeitsbedingungen (oder Einschränkungsqualifikationen)

Man kann fragen, ob ein Minimiererpunkt des ursprünglichen, eingeschränkten Optimierungsproblems (sofern vorhanden) die obigen KKT-Bedingungen erfüllen muss. Dies ist vergleichbar mit der Frage, unter welchen Bedingungen der Minimierer einer Funktion in einem unbeschränkten Problem die Bedingung erfüllen muss . Für den eingeschränkten Fall ist die Situation komplizierter, und man kann eine Vielzahl von (zunehmend komplizierteren) "Regularität"-Bedingungen angeben, unter denen ein eingeschränkter Minimierer auch die KKT-Bedingungen erfüllt. Einige gängige Beispiele für Bedingungen, die dies garantieren, sind im Folgenden tabellarisch aufgeführt, wobei der LICQ am häufigsten verwendet wird: ${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})=0}$

Zwang	Akronym	Aussage
Qualifizierung von Linearitätsbeschränkungen	LCQ	Wenn und sind affine Funktionen , dann keine andere Bedingung benötigt wird. ${\displaystyle g_{i}}$${\displaystyle h_{j}}$
Qualifizierung der linearen Unabhängigkeitsbeschränkung	LICQ	Die Gradienten der aktiven Ungleichheitsbedingungen und die Gradienten der Gleichheitsbedingungen sind linear unabhängig bei . ${\displaystyle x^{*}}$
Mangasarian-Fromovitz-Beschränkungsqualifizierung	MFCQ	Die Gradienten der Gleichheitsbeschränkungen sind bei linear unabhängig und es existiert ein Vektor derart, dass für alle aktiven Ungleichheitsbeschränkungen und für alle Gleichheitsbeschränkungen. ${\displaystyle x^{*}}$${\displaystyle d\in\mathbb{R}^{n}}$${\displaystyle \nabla g_{i}(x^{*})^{\top }d<0}$${\displaystyle \nabla h_{j}(x^{*})^{\top }d=0}$
Konstante Rangbeschränkungsqualifizierung	CRCQ	Für jede Teilmenge der Gradienten der aktiven Ungleichheitsbeschränkungen und der Gradienten der Gleichheitsbeschränkungen ist der Rang in der Nähe von konstant. ${\displaystyle x^{*}}$
Konstante positive lineare Abhängigkeitsbeschränkungsqualifizierung	CPLD	Für jede Teilmenge von Gradienten aktiver Ungleichheitsbeschränkungen und Gradienten von Gleichheitsbeschränkungen bleibt die Teilmenge von Vektoren, wenn sie mit den Ungleichheitsbeschränkungen assoziierten nicht-negativen Skalaren linear abhängig ist, in einer Umgebung von linear abhängig . ${\displaystyle x^{*}}$${\displaystyle x^{*}}$
Quasi-Normalitätsbeschränkungsqualifizierung	QNCQ	Wenn die Gradienten der aktiven Ungleichheitsbedingungen und die Gradienten der Gleichheitsbedingungen linear abhängig sind mit zugeordneten Multiplizierern für Gleichheiten und für Ungleichheiten, dann gibt es keine Sequenz , so dass und${\displaystyle x^{*}}$${\displaystyle \lambda_{j}}$${\displaystyle \mu_{i}\geq 0}$${\displaystyle x_{k}\to x^{*}}$${\displaystyle \lambda_{j}\neq 0\Rightarrow \lambda_{j}h_{j}(x_{k})>0}$${\displaystyle \mu_{i}\neq 0\Rightarrow \mu_{i}g_{i}(x_{k})>0.}$
Zustand von Slater	SC	Für ein konvexes Problem (dh unter der Annahme , Minimierung, sind konvex und ist affiner), gibt es einen Punkt , so dass und${\displaystyle f,g_{i}}$${\displaystyle h_{j}}$${\displaystyle x}$${\displaystyle h(x)=0}$${\displaystyle g_{i}(x)<0.}$

Die strengen Implikationen lassen sich zeigen

LICQ MFCQ ⇒ CPLD ⇒ QNCQ

und

LICQ CRCQ ⇒ CPLD ⇒ QNCQ

In der Praxis werden schwächere Beschränkungsqualifikationen bevorzugt, da sie für eine breitere Auswahl von Problemen gelten.

Ausreichende Bedingungen

In manchen Fällen reichen auch die notwendigen Bedingungen für die Optimalität aus. Im Allgemeinen reichen die notwendigen Bedingungen für eine Optimalität nicht aus und es werden zusätzliche Informationen benötigt, wie beispielsweise die Second Order Sufficient Conditions (SOSC). Für glatte Funktionen beinhalten SOSC die zweite Ableitung, was ihren Namen erklärt.

Die erforderlichen Bedingungen sind ausreichend für Optimalität , wenn die Zielfunktion eines Maximierungsproblem ist eine konkave Funktion , die Ungleichheitsbedingungen sind kontinuierlich differenzierbare konvexe Funktionen und die Gleichheitsbedingungen sind affine Funktionen . Wenn die Zielfunktion eines Minimierungsproblems eine konvexe Funktion ist , sind auch die notwendigen Bedingungen für die Optimalität ausreichend. ${\displaystyle f}$${\displaystyle g_{j}}$${\displaystyle h_{i}}$${\displaystyle f}$

Es wurde 1985 von Martin gezeigt, dass die breitere Klasse von Funktionen, in denen KKT-Bedingungen globale Optimalität garantieren, die sogenannten Typ-1- Invex-Funktionen sind .

hinreichende Bedingungen zweiter Ordnung

Für glatte, nichtlineare Optimierungsprobleme ist eine hinreichende Bedingung zweiter Ordnung wie folgt gegeben.

Die im obigen Abschnitt gefundene Lösung ist ein beschränktes lokales Minimum, wenn für die Lagrange-Funktion ${\displaystyle x^{*},\lambda^{*},\mu^{*}}$

${\displaystyle L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\mu_{i}g_{i}(x)+\sum_{j =1}^{\ell}\lambda_{j}h_{j}(x)}$

dann,

${\displaystyle s^{T}\nabla_{xx}^{2}L(x^{*},\lambda^{*},\mu^{*})s\geq 0}$

wo ist ein Vektor, der folgendes erfüllt, ${\displaystyle s\neq 0}$

${\displaystyle \left[\nabla_{x}g_{i}(x^{*}),\nabla_{x}h_{j}(x^{*})\right]^{T}s= 0}$

wobei nur die aktiven Ungleichheitsbeschränkungen, die einer strikten Komplementarität entsprechen (dh wo ) angewendet werden. Die Lösung ist ein streng beschränktes lokales Minimum, falls die Ungleichung ebenfalls streng ist. ${\displaystyle g_{i}(x)}$${\displaystyle \mu_{i}>0}$

Wenn , sollte die Taylorentwicklung dritter Ordnung des Lagrange-Operators verwendet werden, um zu überprüfen, ob es sich um ein lokales Minimum handelt. Die Minimierung von ist ein gutes Gegenbeispiel, siehe auch Peano Oberfläche . ${\displaystyle s^{T}\nabla_{xx}^{2}L(x^{*},\lambda^{*},\mu^{*})s=0}$${\displaystyle x^{*}}$${\displaystyle f(x_{1},x_{2})=(x_{2}-x_{1}^{2})(x_{2}-3x_{1}^{2})}$

Wirtschaft

In der mathematischen Ökonomie wird der KKT-Ansatz häufig in theoretischen Modellen verwendet, um qualitative Ergebnisse zu erhalten. Betrachten Sie beispielsweise ein Unternehmen, das seinen Umsatz unter Einhaltung einer Mindestgewinnbeschränkung maximiert. Lassen , die Menge der Ausgangs erzeugt werden (zu wählen), sein , der Umsatz mit einem positiven ersten Ableitung und mit einem Nullwert bei Null - Ausgang, werden die Produktionskosten mit einem positiven ersten Ableitung und mit einem nicht-negativen Wert bei Null - Ausgang, und das positive minimale akzeptable Gewinnniveau sein , dann ist das Problem sinnvoll, wenn die Erlösfunktion abflacht und schließlich weniger steil ist als die Kostenfunktion. Das in der zuvor gegebenen Minimierungsform ausgedrückte Problem lautet ${\displaystyle Q}$${\displaystyle R(Q)}$${\displaystyle C(Q)}$${\displaystyle G_{\min}}$

Minimieren ${\displaystyle -R(Q)}$

unterliegt

${\displaystyle G_{\min}\leq R(Q)-C(Q)}$

${\displaystyle Q\geq 0,}$

und die KKT-Bedingungen sind

${\displaystyle {\begin{ausgerichtet}&\left({\frac {{\text{d}}R}{{\text{d}}Q}}\right)(1+\mu)-\mu\ left({\frac{{\text{d}}C}{{\text{d}}Q}}\right)\leq 0,\\[5pt]&Q\geq 0,\\[5pt]&Q\ left[\left({\frac {{\text{d}}R}{{\text{d}}Q}}\right)(1+\mu)-\mu \left({\frac {{\ text{d}}C}{{\text{d}}Q}}\right)\right]=0,\\[5pt]&R(Q)-C(Q)-G_{\min}\geq 0 ,\\[5pt]&\mu \geq 0,\\[5pt]&\mu [R(Q)-C(Q)-G_{\min}]=0.\end{ausgerichtet}}}$

Da die Beschränkung des minimalen Gewinns verletzen würde, gilt, und daher impliziert die dritte Bedingung, dass die erste Bedingung mit Gleichheit gilt. Die Lösung, dass Gleichheit gibt ${\displaystyle Q=0}$${\displaystyle Q>0}$

${\displaystyle {\frac {{\text{d}}R}{{\text{d}}Q}}={\frac {\mu }{1+\mu}}\left({\frac {{ \text{d}}C}{{\text{d}}Q}}\right).}$

Da dies gegeben und strikt positiv ist, ist diese Ungleichung zusammen mit der Nicht-Negativitätsbedingung für Garantien positiv, sodass das ertragsmaximierende Unternehmen auf einem Produktionsniveau operiert, bei dem der Grenzerlös unter den Grenzkosten liegt – ein Ergebnis, dass ist von Interesse, weil es im Gegensatz zum Verhalten eines gewinnmaximierenden Unternehmens steht, das auf einem Niveau arbeitet, auf dem sie gleich sind. ${\displaystyle {\text{d}}R/{\text{d}}Q}$${\displaystyle {\text{d}}C/{\text{d}}Q}$${\displaystyle\mu}$${\displaystyle\mu}$ ${\displaystyle {\text{d}}R/{\text{d}}Q}$ ${\displaystyle {\text{d}}C/{\text{d}}Q}$

Wertfunktion

Betrachten wir das Optimierungsproblem als Maximierungsproblem mit konstanten Ungleichungsbeschränkungen:

${\displaystyle {\text{Maximieren}}\;f(x)}$

${\displaystyle {\text{vorbehaltlich }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0.}$

Die Wertfunktion ist definiert als

${\displaystyle V(a_{1},\ldots,a_{n})=\sup\limits_{x}f(x)}$

${\displaystyle {\text{vorbehaltlich }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0}$

${\displaystyle j\in\{1,\ldots,\ell\},i\in\{1,\ldots,m\},}$

also ist der bereich von is${\displaystyle V}$${\displaystyle \{a\in\mathbb{R}^{m}\mid {\text{für einige }}x\in X,g_{i}(x)\leq a_{i},i\in\ {1,\ldots,m\}\}.}$

Bei dieser Definition ist jeder Koeffizient die Rate, mit der die Wertfunktion mit zunehmender Zunahme ansteigt. Wenn also jede als Ressourcenbeschränkung interpretiert wird, sagen Ihnen die Koeffizienten, um wie viel die Erhöhung einer Ressource den optimalen Wert unserer Funktion erhöht . Diese Interpretation ist besonders in der Ökonomie wichtig und wird beispielsweise bei Problemen der Nutzenmaximierung verwendet . ${\displaystyle \mu_{i}}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle f}$

Verallgemeinerungen

Mit einem zusätzlichen Multiplikator , der Null sein kann (solange ), vor der KKT-Stationarität werden die Bedingungen zu ${\displaystyle \mu_{0}\geq 0}$${\displaystyle (\mu_{0},\mu,\lambda)\neq 0}$${\displaystyle \nabla f(x^{*})}$

${\displaystyle {\begin{ausgerichtet}&\mu_{0}\,\nabla f(x^{*})+\sum _{i=1}^{m}\mu_{i}\,\ nabla g_{i}(x^{*})+\sum_{j=1}^{\ell}\lambda_{j}\,\nabla h_{j}(x^{*})=0, \\[4pt]&\mu_{j}g_{i}(x^{*})=0,\quad i=1,\dots,m,\end{ausgerichtet}}}$

die als Fritz-John-Bedingungen bezeichnet werden . Diese Optimalitätsbedingungen gelten ohne Einschränkungsqualifikationen und sind äquivalent zu der Optimalitätsbedingung KKT oder (nicht-MFCQ) .

Die KKT-Bedingungen gehören zu einer breiteren Klasse der Notwendigen Bedingungen erster Ordnung (FONC), die nicht-glatte Funktionen unter Verwendung von Teilableitungen ermöglichen .

Siehe auch

• Farkas' Lemma
• Lagrange-Multiplikator
• Die Big-M-Methode für lineare Probleme, die den Simplex-Algorithmus auf Probleme ausdehnt, die "größer-als"-Beschränkungen enthalten.
• Schlupfvariable

Verweise

Weiterlesen

• Andreani, R.; Martinez, JM; Schuverdt, ML (2005). „Über die Beziehung zwischen konstanter positiver linearer Abhängigkeitsbedingung und Quasinormalitätsbeschränkungsqualifikation“. Zeitschrift für Optimierungstheorie und Anwendungen . 125 (2): 473–485. doi : 10.1007/s10957-004-1861-9 . S2CID  122212394 .
• Avriel, Mordechai (2003). Nichtlineare Programmierung: Analyse und Methoden . Dover. ISBN 0-486-43227-0.
• Boltjanski, V.; Martini, H.; Soltan, V. (1998). „Das Kuhn-Tucker-Theorem“ . Geometrische Methoden und Optimierungsprobleme . New York: Springer. S. 78–92. ISBN 0-7923-5454-0.
• Boyd, S.; Vandenberghe, L. (2004). "Optimalitätsbedingungen" (PDF) . Konvexe Optimierung . Cambridge University Press. S. 241–249. ISBN 0-521-83378-7.
• Kemp, MurrayC.; Kimura, Yoshio (1978). Einführung in die Wirtschaftsmathematik . New York: Springer. S.  38–73 . ISBN 0-387-90304-6.
• Rau, Nikolaus (1981). "Lagrange-Multiplikatoren". Matrizen und mathematische Programmierung . London: Macmillan. S. 156–174. ISBN 0-333-27768-6.
• Nocedal, J.; Wright, SJ (2006). Numerische Optimierung . New York: Springer. ISBN 978-0-387-30303-1.
• Sundaram, Rangarajan K. (1996). „Inequality Constraints und das Theorem von Kuhn und Tucker“ . Ein erster Kurs in Optimierungstheorie . New York: Cambridge University Press. S. 145–171. ISBN 0-521-49770-1.

Externe Links

• Karush–Kuhn–Tucker-Bedingungen mit Herleitung und Beispielen
• Beispiele und Tutorials zu den KKT-Bedingungen