Condiciones de Karush-Kuhn-Tucker
Las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son condiciones necesarias y suficientes para que la solución de un problema de programación sea óptima. Se dice que esta condicion es una generalización del método de los multiplicadores de Lagrange.
las condiciones de Karush-kuhn-Tucker constituyen la base para el desarrollo de muchos algoritmos computacionales y proporcionan un criterio de parada para muchos otros, permitiendo establecer cuando ha sido alcanzado un óptimo local restringido. En los problemas diferenciables de optimización no restringida la condición necesaria para que una solución sea un mínimo local es que se anule el gradiente. Por el contrario, esta propiedad no es cierta para problemas diferenciables restringidos.
Formulación
Consideremos el problema de optimización
Donde
f(x)= Es la función objetivo a minimizar.
gj(x)= Son las restricciones de desigualdad.
hi(x)= Son las restricciones de igualdad.
m y p= Son el número de restricciones de desigualdad e igualdad, respectivamente.
1.Condición estacionaria:
2.Condición de factibilidad
3.Condición de holgura:
4. Condición de signo: Una vez que se cumplen las condiciones anteriores el punto es de
Resolución de kkt Optimización con restriciónes de desigualdad
Algunos problemas económicos requieren condiciones de desigualdades, por ejemplo cuando se desea maximizar la utilidad sujeta a gastar no más que x soles o minimizar costos sujeto a producir no menos que x unidades de producción.
Dado un problema de maximización sujeto a una restricción de desigualdad con la siguiente función objetivo cóncava diferenciable:
Así, la función Lagrangiana correspondiente será:
Las condiciones suficientes y necesarias de primer orden para la maximización,
llamadas condiciones de Kuhn-Tucker son:
Donde las condiciones en (c) son llamadas condiciones complementarias, significando que tanto x como f '(x) no pueden ser -simultáneamente- cero. Puesto que una función lineal es cóncava y convexa, aunque no estrictamente cóncava o estrictamente convexa.
En las condiciones de Kuhn-Tucker la restricción es siempre expresada como más grande o igual que cero. Esto significa que a diferencia de las restricciones de igualdad que son establecidas igual a cero, el orden de la sustracción es importante en programación cóncava.
Para el máximo en F, una solución interior (Figura a)
Para el máximo en G, una solución de frontera (Figura b)
Para el máximo en H o J, ambas soluciones de frontera (Figura c)
Todas las posibilidades para un máximo en el primer cuadrante pueden ser resumidas
como:
Los cuales son reconocibles como parte de las condiciones de Kuhn-Tucker. Notar que tales condiciones automáticamente excluyen un punto como K en (a) el cual no es un máximo, porque f′(K) > 0. Cabe mencionar que la expresión x f′(x) = 0 significa que al menos una de las dos cantidades debe tomar el valor cero.
El problema entonces se reduce a probar las 8 diferentes posibilidades:
Normalmente, las posibilidades encerradas en el recuadro son las más comunes. Por ello, es sugerible que sean las primeras en ser probadas.
Ejemplo:
Maximizar la función de beneficio sujeto a una restricción de producción
Solución.
Paso 1: Formamos la función Lagrangiana
Paso 2: Por las condiciones de Kuhn-Tucker
Paso 3: Se testean o revisan las condiciones de Kuhn-Tucke
Usando la Regla de Cramer donde:
¿Sabías Que?
Albert William Tucker fue un matemático estadounidense nacido en Canadá que realizó importanes contribuciones a la Topología, Teoría de juegos y a la Programación no lineal.
En 1950, Tucker dio el nombre "Dilema del prisionero" al modelo de cooperación y conflicto de Merrill M. Flood y Melvin Dresher, la más conocida paradoja teórica de juegos. También es muy conocido por las Condiciones de Karush-Kuhn-Tucker, un resultado básico de programación no lineal, que fue publicado en las actas de una conferencia, en lugar de en una revista científica, como suele ser habitual.
Datos de interes
La importancia de este teorema radica en que nos dice que podemos asociar una función de utilidad a unas preferencias, esto nos abre la puerta de la potente herramienta del análisis matemático al estudio del comportamiento del consumidor.
Campo de aplicación
Básicamente el procedimiento consiste en resolver el problema no lineal como uno sin restricciones, luego si la solución óptima de dicho problema no cumple la totalidad o parte de las restricciones del problema se activan dichas restricciones (en conjunto y/o secuencialmente) y se resuelve nuevamente.
