Definition - Duales Optimierungsproblem

• Beispiele:
  • Duales Optimierungsproblem der SVM
  • Duales Optimierungsproblem der Soft-Margin SVM
• Konstrukte:
  • Schwache Dualität
  • Starke Dualität
  • KKT-Bedingungen
• Generalisierungen:
  • Allgemeines Optimierungsproblem
  • Konvexes Optimierungsproblem
• Eigenschaften:
  • Zielfunktion des dualen Optimierungsproblems ist immer konkav
  • Lösung des dualen Problems ist kleiner-gleich Wert des primalen Problems (schwache Dualität)
  • Slaters Bedingung impliziert starke Dualität
  • Komplementärer Schlupf
  • KKT-Bedingungen bei konvexem Optimierungsproblem hinreichend für Lösung des dualen Problems
  • Punkt erfüllt KKT genau dann wenn er das primale und duale Problem löst
• Involvierte Definitionen:
  • Allgemeines Optimierungsproblem
  • Duale Funktion
  • Duale Variablen
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (Definition 3.4.10)

⠀

Definition: Duales Optimierungsproblem

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

Sei ein allgemeines Optimierungsproblem (auch primales Problem) gegeben durch:

Sei die duale Funktion des Optimierungsproblems.

Als duales Optimierungsproblem definieren wir: