Lemma - Duales Optimierungsproblem ist immer konvex

• Bewiesen durch:
  • Zielfunktion des dualen Optimierungsproblems ist immer konkav
• Involvierte Definitionen:
  • Duales Optimierungsproblem
  • Konvexes Optimierungsproblem
  • Konkave Funktion
  • Projektionsabbildung
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (Lemma 3.4.11)

⠀

Lemma: Duales Optimierungsproblem ist immer konvex

Sei ein duales Optimierungsproblem wie folgt gegeben:

Dann gilt: das Optimierungsproblem ist konvex.

Beweis

Da die Zielfunktion des dualen Optimierungsproblems immer konkav ist ist konvex und da

auch folgendem Minimierungsproblem entspricht

mit .

und da es sich bei der Ungleichheitsbedingung um die Negation einer einfachen Projektion handelt, ist linear. Denn

Und da lineare Funktionen stets konvex sind, sind auch die konvex.

Nach Definition ist damit auch das Optimierungsproblem konvex, was zu zeigen war.