Konvexe Optimierung

Optimalitätsbedingungen

Karush-Kuhn-Tucker-Bedingungen

Die Karush-Kuhn-Tucker-Bedingungen (auch bekannt als die KKT-Bedingungen) sind notwendig für die Optimalität einer Lösung in der nichtlinearen Optimierung. Sie sind die Verallgemeinerung der Lagrange-Multiplikatoren für die dynamische Optimierung und finden in der fortgeschrittenen neoklassischen Theorie Anwendung.

Notwendige Bedingungen

Sei die Zielfunktion und die konvexen Funktionen mit und die affinen Funktionen mit sind Nebenbedingungs-Funktionen. Es sei ein zulässiger Punkt, das heißt es gilt . Des Weiteren nimmt man an, dass die aktiven Funktionen g_i differenzierbar im Punkt sind, die Funktionen h_j sind stetig differenzierbar im Punkt . Falls ein lokales Minimum ist, dann existieren Konstanten , mit und mit so dass

für alle

Außerdem gilt

für alle

und die Komplementaritätsbedingung ist erfüllt:

Regularitäts-Bedingungen

Für die obige notwendige Bedingung darf das duale Skalar gleich Null sein. In solchen Fällen spricht man von degeneriert oder abnormal. Dann spielt die notwendige Bedingung keine Rolle für die Eigenschaften der Funktion, nur die Geometrie der Nebenbedingungen ist relevant.

Es existieren mehrere Bedingungen, welche sicherstellen sollen, dass die Lösung nicht-degeneriert ist, das heißt . Diese werden Constraint Qualifications genannt.

Hinreichende Bedingungen

Sei die Zielfunktion und die konvexen Funktionen mit und die affinen Funktionen mit sind Nebenbedingungs-Funktionen. Es sei ein zulässiger Punkt, das heißt es gilt . Des Weiteren nimmt man an, dass die aktiven Gradienten und die Gradienten linear unabhängig sind. Falls ein lokales Minimum ist, dann existieren Konstanten , mit und mit so dass

für alle

dann ist der Punkt ein globales Minimum.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Konvexe Optimierung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung