Dual (optimering)
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]
- Max flöde, minsta snitt -- två problem som är dualer till varandra
Referenser[redigera | redigera wikitext]
- Boyd och Vandenberghe: Convex Optimization. Cambridge University Press 2006