Fuerte dualidad

La dualidad fuerte es una condición de optimización matemática en la que el objetivo óptimo primario y el objetivo óptimo dual son iguales. Por definición, la dualidad fuerte se cumple si y solo si la brecha de dualidad es igual a 0. Esto se opone a la dualidad débil (el problema primario tiene un valor óptimo menor o igual que el problema dual, en otras palabras, la brecha de dualidad es mayor o igual a cero).

Condiciones suficientes

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

• ${\displaystyle F=F^{**}}$donde es la función de perturbación que relaciona los problemas primal y dual y es el biconjugado de (sigue por la construcción de la brecha de dualidad ) ${\displaystyle F}$ ${\displaystyle F^{**}}$ ${\displaystyle F}$
• ${\displaystyle F}$es convexa y semicontinua inferior (equivalente al primer punto por 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

En determinadas condiciones (denominadas "calificación de restricción"), si un problema es solucionable en tiempo polinomial, entonces tiene dualidad fuerte (en el sentido de dualidad lagrangiana ). No está claro si la dirección opuesta también se cumple, es decir, si la dualidad fuerte implica solucionabilidad en tiempo polinomial. ^[3]

Véase también

• Optimización convexa

Referencias

1. Borwein, Jonathan; Lewis, Adrian (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2.ª edición). Springer. ISBN 978-0-387-29570-1.
2. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Recuperado el 3 de octubre de 2011 .
3. Manyem, Prabhu (2010). "Brecha de dualidad, complejidad computacional y completitud de NP: un estudio". arXiv : 1012.5568 [math.OC].