Dual (optimering)

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

Varje optimeringsproblem har en dual funktion. Givet ett optimeringsproblem

minimera ${\displaystyle f(x)\,}$

under villkoren ${\displaystyle g_{i}(x)\leq 0\quad i=1\ldots n}$

så är den duala funktionen^[1]

${\displaystyle 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, eller dualen till ett minimeringsproblem är maximerandet av den duala funktionen:

maximera ${\displaystyle d(\lambda )\,}$

under villkoren ${\displaystyle \lambda \geq 0\,}$.

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

${\displaystyle d^{*}\leq f^{*}}$.^[1]

Konvexa optimeringsproblem är problem sådana att ${\displaystyle f}$ och ${\displaystyle g_{i}}$ är konvexa funktioner. För dessa problem gäller under vissa förutsättningar att

${\displaystyle d^{*}=f^{*}\,}$.^[1]

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

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.

• Max flöde, minsta snitt -- två problem som är dualer till varandra

• Boyd och Vandenberghe: Convex Optimization. Cambridge University Press 2006