Teorema de dualidad fuerte: los valores objetivos óptimos primarios y duales son iguales.
Ejemplo:
[matemáticas] Min \ hspace {0.2cm} x ^ {2} + y ^ {2} \ tag * {} [/ math]
- ¿Cuáles son las inconsistencias conocidas en matemáticas y cuáles son las más controvertidas?
- ¿Cuáles son algunas aplicaciones de la vida real de las transformaciones Z?
- Probar: H (X, Y | Z) = H (X | Z) + H (Y | X, Z)?
- ¿Cuáles son 10 ejemplos de cosas en la naturaleza que corresponden a la serie Fibonacci?
- Tiene 12 años y está nevando constantemente, un quitanieves comienza a funcionar y la primera hora corre el doble de distancia que la segunda hora. ¿A qué hora empezó a nevar?
[matemáticas] \ text {st} \ hspace {0.2cm} -xy + 4 \ leq 0 \ tag * {} [/ matemáticas]
El dual para el problema anterior es
[matemáticas] Máx. \ hspace {0.2cm} \ frac {-1} {2} u ^ {2} + 4u \ tag * {} [/ matemáticas]
[matemáticas] \ text {st} \ hspace {0.2cm} u \ geq 0 \ tag * {} [/ math]
Desde la gráfica de contorno (figura del lado derecho), podemos ver que la solución óptima ocurre en el punto (x, y) = (2,2) cuyo valor objetivo es igual a 8. Además, a partir de la figura 2, podemos ver que dual La solución óptima ocurre en el punto u = 4, cuyo valor objetivo es igual a 8.
Significa que el fuerte teorema de la dualidad se cumple para el problema anterior o la brecha de dualidad es cero (la brecha de dualidad no es más que una diferencia entre el valor objetivo primario óptimo y el valor objetivo dual)
Teorema de dualidad débil: el valor objetivo de cualquier solución factible al problema dual produce un límite inferior en el valor objetivo de cualquier solución factible al problema primario (es decir, la brecha de dualidad es cero)
Condiciones para una fuerte dualidad:
[matemáticas] Min \ hspace {0.2cm} f (x) \ tag {1} [/ math]
[matemáticas] st g (x) \ leq 0 \ etiqueta * {} [/ matemáticas]
Sea [math] f (x) = t [/ math] y [math] g (x) \ leq u [/ math]. La solución óptima para un valor diferente de u se da en la figura siguiente. También proporciona la solución óptima para el problema primario anterior (ecuación 1). El problema 1 exige que el valor [matemático] f (x) [/ matemático] (o t) sea mínimo y al mismo tiempo [matemático] g (x) [/ matemático] debe ser menor que cero. La única x que satisface la demanda anterior es [matemática] x ^ {*} [/ matemática] y su valor objetivo es [matemática] f ^ {*} [/ matemática] (valor objetivo primario), especificado en la figura.
La forma general de dual para el problema 1 es
[matemáticas] Max \ hspace {0.2cm} \ theta (u) \ tag * {} [/ matemáticas]
[matemáticas] st: u \ geq 0 \ etiqueta * {} [/ matemáticas]
Esta cifra también ayuda a encontrar un valor objetivo dual para el mismo problema. Pero, no es fácil como valor objetivo primario. Para encontrar un valor de doble objetivo, necesitamos encontrar un hiperplano de soporte que tenga que satisfacer las siguientes propiedades.
- U (variable doble o multiplicador KKT) da la pendiente de soportar el hiperplano.
- Encuentre una pendiente ‘u’ de tal manera que [math] \ theta (u) [/ math] sea máxima (si primal es un problema de minimización, entonces dual será un problema de maximización)
- S (en la figura) es una función que no aumenta (aumentar el valor de u aumentará la región factible que conduce a mejorar el valor objetivo o permanecer igual)
Condiciones:
La fuerte dualidad generalmente es válida para un problema convexo bajo ciertas condiciones. Esas condiciones se llaman calificación de restricción.
Si el conjunto S no es convexo, entonces el fuerte teorema de dualidad no se cumple (es decir, [matemática] d ^ {*} \ neq f ^ {*} [/ matemática])
La diferencia entre [matemática] d ^ {*} [/ matemática] y [matemática] f ^ {*} [/ matemática] da una brecha de dualidad.
