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 funktionenBoyd och Vandenberghe, kapitel 5 . 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 . 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 . 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
Kategori:Optimeringslära Kategori:Matematiska och kvantitativa metoder (nationalekonomi)