Dual (optimering)
Dualitet är ett viktigt begrepp för att analysera matematiska optimeringsproblem.
Dual funktion
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
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
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
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
- Max flöde, minsta snitt -- två problem som är dualer till varandra
Referenser
- Boyd och Vandenberghe: Convex Optimization. Cambridge University Press 2006
- ^ [a b c] Boyd och Vandenberghe, kapitel 5