Dual (optimering)

Från Wikipedia
Hoppa till: navigering, sök

Dualitet är ett viktigt begrepp för att analysera matematiska optimeringsproblem.

Dual funktion[redigera | redigera wikitext]

Varje optimeringsproblem har en dual funktion. Givet ett optimeringsproblem

minimera f(x) \,
under villkoren g_i(x)\le 0 \quad i = 1\ldots n

så är den duala funktionen[1]

d(\lambda) = \inf_x \left( f(x) + \sum_{i=1}^n \lambda_i g_i(x) \right).

Den duala funktionen är en konkav funktion.

Det duala problemet[redigera | redigera wikitext]

Det duala problemet, eller dualen till ett minimeringsproblem är maximerandet av den duala funktionen:

maximera d(\lambda) \,
under villkoren \lambda \ge 0 \,.

Om d^* är det optimala värdet för det duala problemet och f^* det optimala värdet för det ursprungliga problemet gäller alltid att

d^* \le f^*.[1]

Konvexa problem[redigera | redigera wikitext]

Konvexa optimeringsproblem är problem sådana att f och g_i är konvexa funktioner. För dessa problem gäller under vissa förutsättningar att

d^* = f^* \,.[1]

Ett tillräckligt villkor är att det existerar ett x'\, sådant att g_i(x') < 0 \, för alla i. Om någon g_i skulle råka vara en affin funktion behövs inte strikt olikhet för den funktionen.

Tillämpningar[redigera | redigera wikitext]

Sambandet mellan det ursprungliga (ibland kallat det primala) problemet och dess dual har många konsekvenser. Det ger bland annat upphov till speciella numeriska metoder.

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ [a b c] Boyd och Vandenberghe, kapitel 5