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 $f(x)$

under villkoren $g_i(x)\le 0i=1\dots n$

så är den duala funktionen

$d(\lambda )=\underset{x}{\inf }(f(x)+\sum _{i=1}^n{\lambda }_i{g}_i(x))$.

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 $d(\lambda )$

under villkoren $\lambda \ge 0$.

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

$d^{*}\le f^{*}$.

Konvexa problem

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

$d^{*}=f^{*}$.

Ett tillräckligt villkor är att det existerar ett $x^{\prime }$ sådant att $g_i(x^{\prime })<0$ för alla $i$. Om någon $g_i$ 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