“Brecha de dualidad” es un término más utilizado en la optimización, que es muy similar al aprendizaje automático.
Un problema de optimización es un problema matemático en el que se busca minimizar una función objetivo sujeta a un conjunto de restricciones. Puede pensar en las restricciones como un sistema de ecuaciones, con o sin desigualdades, con cero a muchas soluciones, y resolver el problema de optimización implica encontrar valores para todas las variables en el problema de manera que el valor objetivo (el valor de la función objetivo ) es lo más bajo posible y, al mismo tiempo, satisface las restricciones. Muchos algoritmos de aprendizaje automático (la regresión lineal es un ejemplo) provienen de la optimización; En la regresión lineal, buscamos minimizar una función de costo que es la suma de las distancias entre nuestro modelo predictivo y cada dato.
Convencionalmente, los problemas de optimización implican la minimización (si busca maximizar, negar el objetivo), y el problema de minimización se llama primario . El principio de dualidad establece que para cualquier primario, hay un doble problema que se puede resolver para obtener soluciones, si existen, para el primario. El dual, a diferencia del primario, es un problema de maximización.
- ¿Cuál es el número esperado de veces que una computadora puede calcular 1 + 1 correctamente sin cometer un error?
- ¿Cuáles son los problemas automotrices / de automóviles y de transporte que podemos resolver usando la visión por computadora?
- ¿Por qué el desarrollo ágil de software no se practica en los programas de pregrado de CS en los Estados Unidos?
- ¿Cuáles son las dificultades de descifrar un juego protegido por Denuvo?
- ¿Es Giga Flops una forma confiable de comparar la velocidad de los procesadores de la computadora (no le interesa la potencia u otros parámetros)?
Puedes pensar en la función objetivo como una línea vertical. Subir la línea aumenta el valor objetivo y bajar disminuye el valor objetivo. Los valores objetivos para soluciones a lo primario, un problema de minimización, descienden desde la parte superior, y las soluciones de valor objetivo a lo dual, un problema de maximización, ascienden desde la parte inferior. Con esta visualización, es fácil ver que el dual proporciona un límite inferior para el primario, y el primario un límite superior para el dual. En otras palabras, la solución primaria es necesariamente mayor o igual que la solución dual.
Por lo tanto, hay tres combinaciones posibles de clasificaciones de solución dual y primaria. Primero, tanto el primario como el dual son factibles, lo que significa que podemos encontrar al menos una solución a ambos problemas que satisfagan las restricciones. Tenga en cuenta que una solución no es necesariamente la solución óptima. Segundo, uno de los primarios y duales puede ser ilimitado y el otro inviable; esto parece razonable, porque si, por ejemplo, un objetivo dual es infinito (es decir, no hay un límite inferior a la solución objetiva), entonces el primal nunca convergerá a una solución La tercera combinación es que tanto el primario como el dual son inviables. En los dos últimos escenarios, el problema de optimización se considera inviable; es decir, no hay soluciones que satisfagan el conjunto de restricciones.
Entonces, ¿cuál es la brecha de dualidad?
Fuente: dualidad lagrangea
La brecha de dualidad es solo la diferencia entre las soluciones primarias y duales. En otras palabras, es el valor objetivo óptimo (mínimo) de lo primario menos el valor objetivo óptimo (máximo) de lo dual. Si la diferencia es cero, entonces sabemos con certeza que hemos encontrado la solución óptima al problema.
Si la brecha de optimización no es cero, entonces sabemos con certeza que el problema es factible con soluciones, pero no hemos podido encontrar la solución óptima o demostrar que una solución es óptima.
En resumen, la brecha de dualidad es útil porque puede probar si nuestra solución es óptima o no.
Wikipedia tiene otra definición para la brecha de dualidad que se encuentra en la optimización computacional. Se reproduce aquí:
En la optimización computacional, a menudo se informa otra “brecha de dualidad”, que es la diferencia de valor entre cualquier solución dual y el valor de una iteración factible pero subóptima para el problema primario. Esta “brecha de dualidad” alternativa cuantifica la discrepancia entre el valor de una iteración actual factible pero subóptima para el problema primario y el valor del problema dual; el valor del problema dual es, en condiciones de regularidad, igual al valor de la relajación convexa del problema primario: la relajación convexa es el problema que surge reemplazando un conjunto factible no convexo con su casco convexo cerrado y reemplazando un no convexo función convexa con su cierre convexo, que es la función que tiene el epígrafe que es el casco convexo cerrado de la función objetivo primaria original. [1]
Sin entrar en demasiados detalles, los algoritmos de relajación convexa son formas de convertir un problema no convexo en uno convexo similar. Esto es necesario porque los problemas no convexos tienen óptimos locales, y los algoritmos para encontrar los óptimos globales (es decir, la solución óptima) pueden atascarse en óptimos locales y, por lo tanto, informar una solución subóptima.
Notas al pie
[1] Brecha de dualidad – Wikipedia
