Theorem - Karush-Kuhn-Tucker-Bedingungen

• Konstrukte/Folgerungen:
  • KKT-Bedingungen bei konvexem Optimierungsproblem hinreichend für Lösung des primalen Problems
  • KKT-Bedingungen bei konvexem Optimierungsproblem hinreichend für Lösung des dualen Problems
  • KKT-Bedingungen bei konvexem Optimierungsproblem hinreichend für starke Dualität
  • Punkt erfüllt KKT genau dann wenn er das primale und duale Problem löst
• Involvierte Definitionen:
  • Allgemeines Optimierungsproblem
  • Duales Optimierungsproblem
  • Starke Dualität
  • Lagrangefunktion
  • Differenzierbarkeit
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (Theorem 3.4.20)

⠀

Theorem: Karush-Kuhn-Tucker-Bedingungen

Sei eine Menge.
Sei eine differenzierbare Zielfunktion.
Seien differenzierbare Funktionen.
Seien beliebige Funktionen.

Es seien ein allgemeines Optimierungsproblem (auch primales Problem) und ein zugehöriges duales Problem gegeben.

Sei eine optimale Lösung des primalen Problems.
Sei eine optimale Lösung des dualen Problems.

Gilt zwischen beiden Probleme starke Dualität, so gilt mit den Karush-Kuhn-Tucker-Bedingungen (kurz KKT-Bedingungen):

üüüü

Anmerkung

Sieht die letzte Zeile nicht stark nach der Lagrangefunktion aus?

Ja. Die letzte Zeile ließe sich auch schreiben als

Uff. Und wie gehe ich jetzt vor, wenn ich einen KKT-Punkt ermitteln soll?

1. Die Gleichungen (I) so weit es geht nach den einzelnen Variablen umstellen. Die Ergebnisse in die übrigen Gleichungen (II, III, IV,V) einsetzen.
2. Jetzt die Gleichungen (IV) betrachten und alle Parameter-Kombinationen aufschreiben, die die Gleichungen (IV) erfüllen. Das schließt auch alle ein.
3. Jede der so gefundenen Parameter-Kombinationen durch (V) überprüfen.
4. Gegebenenfalls so umstellen, dass man bisher unbelegte Parameter belegen kann.
5. Jetzt noch (III) überprüfen und fertig :)