Dualidad de Wolfe

En optimización matemática , la dualidad de Wolfe , llamada así por Philip Wolfe , es un tipo de problema dual en el que la función objetivo y las restricciones son todas funciones diferenciables . Con este concepto se puede encontrar un límite inferior para un problema de minimización gracias al principio de dualidad débil . ^[1]

Formulación matemática

Para un problema de minimización con restricciones de desigualdad,

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}}$

El problema dual lagrangiano es

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

donde la función objetivo es la función dual de Lagrange. Siempre que las funciones y sean convexas y continuamente diferenciables, el ínfimo se da cuando el gradiente es igual a cero. El problema ${\displaystyle f}$ ${\displaystyle g_{1},\ldots ,g_{m}}$

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

se denomina problema dual de Wolfe. ^[2] Este problema emplea las condiciones KKT como restricción. Además, la restricción de igualdad es no lineal en general, por lo que el problema dual de Wolfe puede ser un problema de optimización no convexo. En cualquier caso, se cumple la dualidad débil. ^[3] ${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)}$

Véase también

• Dualidad lagrangiana
• Dualidad de Fenchel

Referencias

1. Philip Wolfe (1961). "Un teorema de dualidad para programación no lineal". Quarterly of Applied Mathematics . 19 (3): 239–244. doi : 10.1090/qam/135625 .
2. "Capítulo 3. Dualidad en optimización convexa" (PDF) . 30 de octubre de 2011. Consultado el 20 de mayo de 2012 .
3. Geoffrion, Arthur M. (1971). "Dualidad en programación no lineal: un desarrollo simplificado orientado a aplicaciones". SIAM Review . 13 (1): 1–37. doi :10.1137/1013001. JSTOR  2028848.