Wolfe dualitet

Inom matematisk optimering är Wolfe-dualitet , uppkallad efter Philip Wolfe , en typ av dubbla problem där den objektiva funktionen och begränsningarna alla är differentierbara funktioner . Genom att använda detta koncept kan en nedre gräns för ett minimeringsproblem hittas på grund av den svaga dualitetsprincipen .

Matematisk formulering

För ett minimeringsproblem med ojämlikhetsbegränsningar,

{\begin{aligned}&{\underset {x}{\operatörsnamn {minimera } }}&&f(x)\\&\operatörsnamn {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}

det lagrangiska dubbla problemet är

{\begin{ aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\summa _{j=1}^{m}u_{j}g_{ j}(x)\right)\\&\operatörsnamn {subject\;to} &&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}

där objektivfunktionen är Lagrange-dubbelfunktionen. Förutsatt att funktionerna $f$ och $g_{1},\ldots ,g_{m}$ är konvexa och kontinuerligt differentierbara, inträffar infimum där gradienten är lika med noll . Problemet

{\begin{aligned}&{\underset {x,u}{\operatörsnamn {maximize} }}&&f(x)+\summa _{j=1} ^{m}u_{j}g_{j}(x)\\&\operatörsnamn {subject\;to} &&\nabla f(x)+\summa _{j=1}^{m}u_{j} \nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}

kallas Wolfes dubbla problem. Detta problem använder KKT-villkoren som en begränsning. Likhetsbegränsningen $\nabla f(x)+\summa _{j=1}^{m}u_{j} \nabla g_{j}(x)$ är olinjärt i allmänhet, så Wolfes dubbla problem kan vara ett icke-konvext optimeringsproblem. I alla fall håller svag dualitet.

Se även