Dualidad débil

En matemáticas aplicadas , la dualidad débil es un concepto de optimización que establece que la brecha de dualidad siempre es mayor o igual que 0. Esto significa que para cualquier problema de minimización, llamado problema primal , la solución al problema primal siempre es mayor o igual que la solución al problema de maximización dual . ^{[ 1 ] : 225} Alternativamente, la solución a un problema de maximización primal siempre es menor o igual que la solución al problema de minimización dual. En resumen: la dualidad débil establece que cualquier solución factible para el problema dual es una cota inferior para la solución del problema primal. ^{[ 2 ]}

La dualidad débil se contrapone a la dualidad fuerte , que establece que el objetivo óptimo primal y el objetivo óptimo dual son iguales . La dualidad fuerte solo se cumple en ciertos casos. ^{[ 3 ]}

Muchos algoritmos de aproximación primal-dual se basan en el principio de dualidad débil. ^{[ 4 ]}

Consideremos un problema de programación lineal ,

dónde${\displaystyle A}$es${\displaystyle m\times n}$y${\displaystyle b}$es${\displaystyle m\times 1}$. El problema dual de ( 1 ) es

El teorema de la dualidad débil establece que${\displaystyle c^{\top }x^{*}\leq b^{\top }y^{*}}$para cada solución${\displaystyle x^{*}}$al problema primal ( 1 ) y cada solución${\displaystyle y^{*}}$al problema dual ( 2 ).

Es decir, si${\displaystyle (x_{1},x_{2},....,x_{n})}$es una solución factible para el programa lineal de maximización primal y${\displaystyle (y_{1},y_{2},....,y_{m})}$Si existe una solución factible para el programa lineal de minimización dual, entonces el teorema de dualidad débil puede enunciarse como: ${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}}$, dónde${\displaystyle c_{j}}$y${\displaystyle b_{i}}$son los coeficientes de las respectivas funciones objetivo.

Demostración: c ^T x = x ^T c ≤ x ^T A ^T y ≤ b ^T y

• Optimización convexa
• Desigualdad max-min