Fuerte dualidad

La dualidad fuerte es una condición en la optimización matemática en la que el objetivo óptimo primal y el objetivo óptimo dual son iguales. Por definición, la dualidad fuerte se cumple si y solo si la diferencia entre los objetivos duales es igual a cero. Esto se contrapone a la dualidad débil (el problema primal tiene un valor óptimo mayor o igual que el problema dual; en otras palabras, la diferencia entre los objetivos duales es mayor o igual a cero).

Condiciones suficientes

Cada una de las siguientes condiciones es suficiente para que se cumpla la dualidad fuerte:

$F=F^{**}$ donde es la función de perturbación que relaciona los problemas primal y dual y es el biconjugado de (se deduce por construcción de la brecha de dualidad ) $F$ $F^{**}$ $F$
$F$ es convexa y semicontinua inferiormente (equivalente al primer punto según el teorema de Fenchel-Moreau )
El problema primal es un problema de optimización lineal.
Condición de Slater para un problema de optimización convexa . ^{[ 1 ]}^{[ 2 ]}

Fuerte dualidad y complejidad computacional

Bajo ciertas condiciones (denominadas "calificación de restricciones"), si un problema es resoluble en tiempo polinomial, entonces posee dualidad fuerte (en el sentido de dualidad lagrangiana ). Queda por determinar si lo contrario también es cierto, es decir, si la dualidad fuerte implica resoluble en tiempo polinomial. ^{[ 3 ]}

Véase también

Referencias

^ Borwein, Jonathan; Lewis, Adrian (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2.ª ed.). Springer. ISBN 978-0-387-29570-1.
^ Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Consultado el 3 de octubre de 2011 .
^ Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv : 1012.5568 [ math.OC ].

[borwein-1] Borwein, Jonathan; Lewis, Adrian (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2.ª ed.). Springer. ISBN 978-0-387-29570-1.

[boyd-2] Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Consultado el 3 de octubre de 2011 .

[3] Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv : 1012.5568 [ math.OC ].

[ 1 ]

[ 2 ]

[ 3 ]