www.wikidata.de-de.nina.az

Karush Kuhn Tucker Bedingungen Die sind ein notwendiges Optimalitätskriterium erster Ordnung in der nichtlinearen Optimi

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 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 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.

Aussage Bearbeiten

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

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

  • 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 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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Karush Kuhn Tucker Bedingungen sind ein notwendiges Optimalitatskriterium erster Ordnung in der nichtlinearen Optimierung Sie sind die Verallgemeinerung der notwendigen Bedingung f x 0 displaystyle 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 unveroffentlichten Master Arbeit von William Karush aufgefuhrt 1 Bekannter wurden diese jedoch erst 1951 nach einem Konferenz Paper von Harold W Kuhn und Albert W Tucker 2 Inhaltsverzeichnis 1 Rahmenbedingungen 2 Aussage 2 1 Karush Kuhn Tucker Bedingungen 2 2 Optimalitatskriterium 3 Regularitatsvoraussetzungen 4 Spezialfalle 4 1 Konvexe Optimierung 4 2 Konvexe Zielfunktion mit linearen Restriktionen 4 3 Allgemeine Zielfunktion mit linearen Restriktionen 5 Beispiel 6 Verallgemeinerungen 7 Literatur 8 Weblinks 9 EinzelnachweiseRahmenbedingungen BearbeitenGegeben seien m l 1 displaystyle m l 1 nbsp stetig differenzierbare Funktionen f g 1 g m h 1 h l D R displaystyle f g 1 ldots g m h 1 ldots h l D rightarrow mathbb R nbsp wobei D displaystyle D nbsp eine nicht leere offene Teilmenge von R n displaystyle mathbb R n nbsp ist Die KKT Bedingungen ermoglichen Aussagen uber ein Optimierungsproblem der Form min x C f x displaystyle min x in C f x nbsp wobei C D displaystyle C subseteq D nbsp die Menge aller Punkte in R n displaystyle mathbb R n nbsp ist welche die Nebenbedingungen g i x 0 1 i m displaystyle g i x leq 0 1 leq i leq m nbsp h j x 0 1 j l displaystyle h j x 0 1 leq j leq l nbsp erfullen Aussage BearbeitenKarush Kuhn Tucker Bedingungen Bearbeiten Ein Punkt x m l C R m R l displaystyle x mu lambda in C times mathbb R m times mathbb R l nbsp heisst Karush Kuhn Tucker Punkt oder kurz KKT Punkt des obigen Optimierungsproblems wenn er die folgenden Bedingungen erfullt f x i 1 m m i g i x j 1 l l j h j x 0 h j x 0 fur j 1 l g i x 0 fur i 1 m m i 0 fur i 1 m m i g i x 0 fur i 1 m displaystyle begin alignedat 3 amp nabla f x sum i 1 m mu i nabla g i x sum j 1 l lambda j nabla h j x 0 amp h j x 0 amp amp text fur j 1 ldots l amp g i x leq 0 amp amp text fur i 1 ldots m amp mu i geq 0 amp amp text fur i 1 ldots m amp mu i g i x 0 amp amp text fur i 1 ldots m end alignedat nbsp Diese Bedingungen werden die Karush Kuhn Tucker Bedingungen oder kurz KKT Bedingungen genannt Verwendet man alternativ die Lagrange Funktion L x m l f x i 1 m m i g i x j 1 l l j h j x displaystyle L x mu lambda f x sum i 1 m mu i g i x sum j 1 l lambda j h j x nbsp so kann man die erste Zeile formulieren als x L x m l 0 displaystyle nabla x L x mu lambda 0 nbsp Die zweite und dritte Zeile fordert dass x displaystyle x nbsp zulassig fur das primale Problem ist die vierte fordert Zulassigkeit der dualen Variable fur das duale Problem und die letzte Zeile Komplementaritat Ist der Definitionsbereich D R 0 n displaystyle D mathbb R geq 0 n nbsp so benotigt man nicht zwangslaufig die Formulierung uber g i x 0 displaystyle g i x leq 0 nbsp und zugehorige Lagrange Multiplikatoren Stattdessen lauten die KKT dann f x i 1 m m i g i x j 1 l l j h j x 0 g i x 0 fur i 1 m h j x 0 fur j 1 l m i 0 fur i 1 m m i g i x 0 fur i 1 m x f x i 1 m m i g i x j 1 l l j h j x 0 fur p 1 n x p 0 fur p 1 n displaystyle begin alignedat 3 amp 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 amp g i x leq 0 amp amp text fur i 1 ldots m amp h j x 0 amp amp text fur j 1 ldots l amp mu i geq 0 amp amp text fur i 1 ldots m amp mu i g i x 0 amp amp text fur i 1 ldots m amp 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 amp amp text fur p 1 ldots n amp x p geq 0 amp amp text fur p 1 ldots n end alignedat nbsp Optimalitatskriterium Bearbeiten Ist der Punkt x displaystyle x nbsp lokales Minimum des Optimierungsproblems und erfullt er gewisse Regularitatsvoraussetzungen siehe unten so gibt es m l displaystyle mu lambda nbsp so dass x m l displaystyle x mu lambda nbsp ein KKT Punkt ist Somit sind die KKT Bedingungen ein notwendiges Optimalitatskriterium Im Allgemeinen ist m l displaystyle mu lambda nbsp nicht eindeutig festgelegt Regularitatsvoraussetzungen BearbeitenEs gibt unterschiedlichste Regularitatsbedingungen die sicherstellen dass die KKT Bedingungen gelten Sie unterscheiden sich hauptsachlich in ihrer Allgemeingultigkeit und der Leichtigkeit ihrer Anwendung und Uberprufbarkeit In Anlehnung an das Englische werden sie auch constraint qualifications genannt Beispiele fur constraint qualifications sind Abadie CQ Der Tangentialkegel und der linearisierte Tangentialkegel stimmen in x displaystyle hat x nbsp uberein Lineare Unabhangigkeit linear independence constraint qualification LICQ Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind linear unabhangig im Punkt x displaystyle hat x nbsp Diese CQ liefert Eindeutigkeit bei m l displaystyle mu lambda nbsp Mangasarian Fromovitz Mangasarian Fromovitz constraint qualification MFCQ Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv linear unabhangig im Punkt x displaystyle hat x nbsp Konstanter Rang constant rank constraint qualification CRCQ Fur jede Untermenge der Gradienten der aktiven Ungleichungsbedingungen und der Gradienten der Gleichungsbedingungen ist der Rang in einer Umgebung von x displaystyle hat x nbsp konstant Konstante positiv lineare Abhangigkeit constant positive linear dependence constraint qualification CPLD Fur jede Untermenge der Gradienten der aktiven Ungleichungsbedingungen und der Gradienten der Gleichungsbedingungen im Punkt x displaystyle hat x nbsp gilt falls eine positiv lineare Abhangigkeit im Punkt x displaystyle hat x nbsp vorliegt dann gibt es eine positiv lineare Abhangigkeit in einer Umgebung von x displaystyle hat x nbsp Speziell fur konvexe Optimierungsprobleme und fast konvexe Funktionen gibt es die Slater Bedingung Es gibt einen zulassigen Punkt der strikt zulassig bezuglich der Ungleichungsrestriktionen ist Sie liefert die Regularitat aller Punkte des Problems und nicht nur die des untersuchten Punktes Man kann zeigen dass die folgenden beiden Folgerungsstrange gelten LICQ MFCQ CPLD displaystyle mbox LICQ Rightarrow mbox MFCQ Rightarrow mbox CPLD nbsp und LICQ CRCQ CPLD displaystyle mbox LICQ Rightarrow mbox CRCQ Rightarrow mbox CPLD nbsp obwohl MFCQ nicht aquivalent zu CRCQ ist In der Praxis werden schwachere constraint qualifications bevorzugt da diese starkere Optimalitats Bedingungen liefern Insbesondere konnen die constraint qualifications auch genutzt werden um sicherzustellen dass die KKT Bedingungen mit den Fritz John Bedingungen ubereinstimmen Spezialfalle BearbeitenKonvexe Optimierung Bearbeiten Handelt es sich bei dem Optimierungsproblem um ein konvexes Optimierungsproblem sind also f g 1 g m displaystyle f g 1 ldots g m nbsp konvex und h 1 h l displaystyle h 1 ldots h l nbsp affin so lassen sich starkere Aussagen treffen Einerseits kann man dann als Regularitatsbedingung die Slater Bedingung verwenden welche die Regularitat aller Punkte des Problems liefern andererseits ist bei konvexen Problemen die KKT Bedingung auch hinreichendes Optimalitatskriterium Jeder Punkt der ein KKT Punkt ist ist also lokales und aufgrund der Konvexitat sogar globales Minimum Insbesondere ist dazu keine Regularitatsvoraussetzung notig Konvexe Zielfunktion mit linearen Restriktionen Bearbeiten Ist die Zielfunktion f x displaystyle f x nbsp und die Definitionsmenge D displaystyle D nbsp konvex und sind alle Restriktionen affin sprich ist g i x a i T x b i displaystyle g i x a i T x b i nbsp und h j x a j T x b j displaystyle h j x a j T x b j nbsp so ist ohne weitere Regularitatsvoraussetzungen ein KKT Punkt aquivalent 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 erfullt da die Linearisierung der linearen Funktionen wieder die Funktionen selbst liefert Damit ist in diesem Fall ohne weitere Voraussetzungen an die Regularitat ein lokales Optimum immer ein KKT Punkt Beispiel BearbeitenBetrachten wir als Beispiel das nichtlineare Optimierungsproblem min x X x 1 1 2 x 2 2 2 displaystyle min x in X x 1 1 2 x 2 2 2 nbsp mit der Restriktionsmenge X x R 2 g 1 x x 2 0 g 2 x x 1 2 x 2 4 0 g 3 x x 1 2 x 2 1 0 displaystyle 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 nbsp Ein lokales Minimum befindet sich im Punkt x 2 0 displaystyle x 2 0 nbsp Zuerst uberpruft man eine der Regularitatsbedingungen in diesem Fall LICQ im lokalen Optimum sind die Ungleichungsrestriktionen g 1 g 2 displaystyle g 1 g 2 nbsp aktiv und deren Gradienten g 1 x 0 1 T g 2 x 4 1 T displaystyle nabla g 1 x 0 1 T nabla g 2 x 4 1 T nbsp sind linear unabhangig Somit ist die LICQ erfullt es existiert also ein KKT Punkt Um diesen zu berechnen stellen wir zunachst fest dass g 3 x lt 0 displaystyle g 3 x lt 0 nbsp ist also ist aufgrund der KKT Bedingung m 3 g 3 x 0 displaystyle mu 3 g 3 x 0 nbsp auf jeden Fall m 3 0 displaystyle mu 3 0 nbsp Die anderen Werte des KKT Punktes ergeben sich aus dem Gleichungssystem der Gradienten am Punkt x displaystyle x nbsp 6 4 m 1 0 1 m 2 4 1 0 0 displaystyle 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 nbsp zu m 1 11 2 m 2 3 2 displaystyle mu 1 frac 11 2 mu 2 frac 3 2 nbsp Somit ist ein KKT Punkt gegeben als 2 0 11 2 3 2 0 displaystyle 2 0 frac 11 2 frac 3 2 0 nbsp Da das Problem nicht konvex ist gilt die Umkehrung jedoch nicht der Punkt 1 2 0 0 0 displaystyle 1 2 0 0 0 nbsp ist zwar ein KKT Punkt des Problems aber kein Optimum Verallgemeinerungen BearbeitenEine Verallgemeinerung der KKT Bedingungen sind die Fritz John Bedingungen Sie kommen ohne Regularitatsvoraussetzungen aus liefern jedoch eine schwachere Aussage Fur konvexe Optimierungsprobleme bei denen die Funktionen nicht stetig differenzierbar sind gibt es ausserdem die Sattelpunktkriterien der Lagrange Funktion Literatur BearbeitenFlorian 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 amp hl deWeblinks BearbeitenBuch 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 amp Sons Inc 2006 871 S doi 10 1002 0471787779 ISBN 9780471787778Einzelnachweise Bearbeiten 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 Kuhn Tucker Nonlinear programming in Jerzey Neyman Proc 2 Berkeley Symp Math Statistics and Probability University of California Press 1951 S 481 492 Abgerufen von https de wikipedia org w index php title Karush Kuhn Tucker Bedingungen amp oldid 236014498