Dualidad débil

La dualidad débil es un concepto en optimización que establece que la brecha de dualidad siempre es mayor o igual a cero. Esto significa que la solución del problema primal (el problema de minimización) siempre es mayor o igual que la solución del problema dual asociado . Este término se opone a la dualidad fuerte , que se cumple sólo bajo ciertas condiciones [1] .

Uso

Muchos algoritmos de aproximación dual directa [2] se basan en el principio de dualidad débil [3] .

Teorema de la dualidad débil

Tarea directa :

Maximizar bajo la condición ;

\mathbf {c} ^{T}\mathbf {x}

A\mathbf {x} \leqslant \mathbf {b} ,\mathbf {x} \geqslant 0

Doble tarea:

Minimizar sujeto a .

\mathbf {b} ^{T}\mathbf {y}

A^{T}\mathbf {y} \geqslant \mathbf {c} ,\mathbf {y} \geqslant 0

El teorema de la dualidad débil establece que . $\mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Es decir, si es una solución factible al problema directo de maximizar la programación lineal y es una solución factible al problema dual de minimizar la programación lineal, entonces el teorema de la dualidad débil se puede formular de la siguiente manera: donde y son los coeficientes de la correspondiente funciones objetivas. ${\ estilo de visualización (x_{1},x_{2},....,x_{n})}$ ${\ estilo de visualización (y_{1},y_{2},....,y_{m})}$ ${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leqslant \sum _{i=1}^{m}b_{i}y_{i))$ ${\ Displaystyle c_ {j}}$ $bi$

Prueba: $\mathbf {c} ^{T}\mathbf {x} =\mathbf {x} ^{T}\mathbf {c} \leqslant \mathbf {x} ^{T}A^{T}\mathbf {y} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Generalizaciones

En un caso más general, si es una solución factible para el problema de maximización primal y es una solución factible para el problema de minimización dual, de la dualidad débil se sigue que , donde y son las funciones objetivo para los problemas primal y dual, respectivamente. $X$ $y$ ${\ estilo de visualización f (x) \ leqslant g (y)}$ $F$ $gramo$

Véase también

programación convexa

Notas

↑ Boţ, Grad, Wanka, 2009 , p. una.
↑ Un algoritmo primal-dual es un algoritmo para resolver los problemas primal y dual simultáneamente.
↑ González, 2007 , p. 2.

Literatura

Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Dualidad en Optimización Vectorial . - Berlín: Springer-Verlag, 2009. - Pág. 1. - ISBN 978-3-642-02885-4 . -doi : 10.1007 / 978-3-642-02886-1 .
Teófilo F. González. Manual de Algoritmos de Aproximación y Metaheurísticas . - Prensa CRC, 2007. - S. 2-12. — ISBN 9781420010749 .