Karush-Kuhn-Tucker-Begriffe
In der Mathematik , die Bedingungen von Karush- Kuhn - Tucker oder früher Bedingungen Kuhn-Tucker machen es möglich , Probleme zu lösen Optimierung unter nichtlinearen Einschränkungen von Ungleichheiten.
Oder eine Funktion, die als Zielfunktion bezeichnet wird, und eine Funktion , die als Einschränkungen bezeichnet wird . Es wird angenommen , dass und les ist die Klasse C 1 .
f::R.nicht→R.{\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R}}Gich::R.nicht→R.{\ displaystyle g_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb {R}}1≤ich≤m{\ displaystyle 1 \ leq i \ leq m}f{\ displaystyle f}Gich{\ displaystyle g_ {i}}
Das zu lösende Problem ist wie folgt:
Finden Sie heraus, wer unter den Bedingungen für alles maximiert .
X.∗∈R.nicht{\ displaystyle X ^ {*} \ in \ mathbb {R} ^ {n}}f{\ displaystyle f}Gich((X.∗)≥0{\ displaystyle g_ {i} (X ^ {*}) \ geq 0}ich{\ displaystyle i}
Satz
Wenn unter den Bedingungen für alle ein Maximum zugelassen wird , gibt es Bedingungen, die die folgenden Bedingungen erfüllen, die als Kuhn-Tucker-Bedingungen bezeichnet werden. Wir sagen dann, dass dies der Lagrange-Multiplikator ist, der mit der -ten Bedingung verbunden ist.
f{\ displaystyle f}X.∗{\ displaystyle X ^ {*}}Gich((X.∗)≥0{\ displaystyle g_ {i} (X ^ {*}) \ geq 0}ich{\ displaystyle i}((λich)1≤ich≤m∈R.m{\ displaystyle (\ lambda _ {i}) _ {1 \ leq i \ leq m} \ in \ mathbb {R} ^ {m}}λich{\ displaystyle \ lambda _ {i}}ich{\ displaystyle i}
Bedingungen erster Ordnung
X.∗{\ displaystyle X ^ {*}}ist ein kritischer Punkt von der Lagrange - Funktion des Problems. Mit anderen Worten, wo ist der Gradient oder wieder durch Schreiben der partiellen Ableitungen?
L.λ::X.⟼f((X.)+∑ich=1mλichGich((X.){\ displaystyle L _ {\ lambda}: X \ longmapsto f (X) + \ sum _ {i = 1} ^ {m} \ lambda _ {i} g_ {i} (X)}∇L.λ((X.∗)=0{\ displaystyle \ nabla L _ {\ lambda} (X ^ {*}) = 0}∇{\ displaystyle \ nabla}
∂f∂xk((X.∗)+∑ich=1mλich∂Gich∂xk((X.∗)=0, 1≤k≤nicht{\ displaystyle {\ frac {\ partielle f} {\ partielle x_ {k}}} (X ^ {*}) + \ sum _ {i = 1} ^ {m} \ lambda _ {i} {\ frac { \ partielle g_ {i}} {\ partielle x_ {k}}} (X ^ {*}) = 0, \ 1 \ leq k \ leq n}
Zusätzliche Freigabebedingungen
Für alles ,
ich{\ displaystyle i}1≤ich≤m{\ displaystyle 1 \ leq i \ leq m}
- λich≥0{\ displaystyle \ lambda _ {i} \ geq 0}
-
λich=0{\ displaystyle \ lambda _ {i} = 0}oder .Gich((X.∗)=0{\ displaystyle g_ {i} (X ^ {*}) = 0}
Man kann auch kompakter schreiben, das für alle , .
ich{\ displaystyle i}Mindest[λich,Gich((X.∗)]]=0{\ displaystyle \ min [\ lambda _ {i}, g_ {i} (X ^ {*})] = 0}
Bemerkungen
Die zusätzlichen Freigabebedingungen implizieren, dass wenn , dann . Mit anderen Worten: Wenn die -te Bedingung nicht gesättigt ist , ist der zugehörige Lagrange-Multiplikator Null.
Gich((X.∗)>0{\ displaystyle g_ {i} (X ^ {*})> 0}λich=0{\ displaystyle \ lambda _ {i} = 0}ich{\ displaystyle i}
Der Beweis für dieses Ergebnis beruht im Wesentlichen auf Farkas 'Lemma .
Gegenseitig
Dieser Satz liefert a priori nur notwendige Bedingungen. Unter bestimmten Bedingungen sind dies jedoch auch ausreichende Bedingungen. Dies ist insbesondere dann der Fall , wenn und die Funktionen sind konkav .
f{\ displaystyle f}Gich{\ displaystyle g_ {i}}
Anmerkungen und Referenzen
-
(in) W. Karush, Funktionsminima mehrerer Variablen mit Ungleichungen haben seitliche Einschränkungen , Abt. für Mathematik, Univ. von Chicago, Chicago, Illinois,1939
-
William Karush gab 1939 als erster dieses Ergebnis bekannt. Seine Arbeit wurde jedoch lange nach der Veröffentlichung von Kuhn und Tucker wiederentdeckt.
-
(in) HW Kuhn und AW Tucker, "Nichtlineare Programmierung" , in Proceedings of 2nd Berkeley Symposium , Berkeley, University of California Press,1951( Math Reviews 47303 , online lesen ) , p. 481-492.
-
Weitere Informationen zu den auferlegten Regelmäßigkeitsbedingungen finden Sie unter „ Optimalitätsbedingungen (endliche Dimension) “.
Externer Link
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">