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
under villkoren

så är den duala funktionen[1]

.

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
under villkoren .

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

.[1]

Konvexa problem[redigera | redigera wikitext]

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

.[1]

Ett tillräckligt villkor är att det existerar ett sådant att för alla . Om någon 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