Condiciones de Karush-Kuhn-Tucker

Las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son requerimientos necesarios y suficientes para que la solución de un problema de programación matemática sea óptima. Es una generalización del método de los multiplicadores de Lagrange.

Problema general de optimización

Consideremos el siguiente problema general:

${\displaystyle {\text{min }}\;f(x)}$

${\displaystyle {\text{sujeto a }}\ }$

${\displaystyle \ g_{i}(x)\leq 0\ }$, ${\displaystyle \ i=1,\ldots ,m}$

${\displaystyle \ h_{j}(x)=0\ }$, ${\displaystyle \ j=1,\ldots ,l}$

donde ${\displaystyle f(x)}$ es la función objetivo a minimizar, ${\displaystyle g_{i}(x)}$ son las restricciones de desigualdad y ${\displaystyle h_{j}(x)}$ son las restricciones de igualdad, con ${\displaystyle m}$ y ${\displaystyle l}$ el número de restricciones de desigualdad e igualdad, respectivamente.

Las condiciones necesarias para problemas con restricciones de desigualdad fueron publicadas por primera vez en la tesis de máster de W. Karush,^[1] aunque fueron renombradas tras un artículo en una conferencia de Harold W. Kuhn y Albert W. Tucker.^[2]

Condiciones necesarias de primer orden

Supongamos que la función objetivo, por ejemplo, a minimizar, es ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ y las funciones de restricción son ${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ y ${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$. Entonces, supongamos que son continuamente diferenciables en el punto ${\displaystyle x^{*}}$. Si ${\displaystyle x^{*}}$ es un mínimo local, entonces existen constantes ${\displaystyle \lambda \geq 0}$, ${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$ y ${\displaystyle \nu _{j}\ (j=1,...,l)}$ no todas nulas tales que:

${\displaystyle \lambda +\sum _{i=1}^{m}\mu _{i}+\sum _{j=1}^{l}|\nu _{j}|>0,}$

${\displaystyle \lambda \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}(x^{*})=0,}$

${\displaystyle \mu _{i}g_{i}(x^{*})=0\;{\mbox{para todo}}\;i=1,\ldots ,m.}$

Condiciones de regularidad (o cualificación de las restricciones)

En la condición necesaria anterior, el multiplicador dual ${\displaystyle \lambda }$ puede ser igual a cero. Este caso se denomina degenerado o anormal. La condición necesaria no tiene en cuenta las propiedades de la función sino la geometría de las restricciones.

Existen una serie de condiciones de regularidad que aseguran que la solución no es degenerada (es decir ${\displaystyle \lambda \neq 0}$). Estas incluyen:

• Cualificación de la restricción de independencia lineal (CRIL): los gradientes de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad son linealmente independientes en ${\displaystyle x^{*}}$.
• Cualificación de la restricción de Mangasarian-Fromowitz (CRMF): los gradientes de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad son linealmente independientes positivos en ${\displaystyle x^{*}}$.
• Cualificación de la restricción de rango constante (CRRC): para cada subconjunto de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad, el rango en el entorno de ${\displaystyle x^{*}}$ es constante.
• Cualificación de la restricción de dependencia lineal constante positiva (DLCP): para cada subconjunto de restricciones activas de desigualdad y de gradientes de las restricciones de igualdad, si es linealmente dependiente positivo en ${\displaystyle x^{*}}$ entonces es linealmente dependiente positivo en el entorno de ${\displaystyle x^{*}}$. (${\displaystyle \{v_{1},\ldots ,v_{n}\}}$ es linealmente dependiente positivo si existe ${\displaystyle a_{1}\geq 0,\ldots ,a_{n}\geq 0}$ distintos de cero tal que ${\displaystyle a_{1}v_{1}+\cdots +a_{n}v_{n}=0}$)
• Condición de Slater: para un problema únicamente con restricciones de desigualdad, existe un punto ${\displaystyle x}$ tal que ${\displaystyle g_{i}(x)<0}$ para todo ${\displaystyle i=1,\ldots ,m}$

Puede verse que CRIL=>CRMF=>DLCP, CRIL=>CRRC=>DLCP, aunque CRMF no es equivalente a CRRC. En la práctica, se prefiere cualificación de restricciones más débiles ya que proporcionan condiciones de optimalidad más fuertes.

Condiciones suficientes

Sean ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$, ${\displaystyle g_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ convexa, ${\displaystyle h_{j}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ y un punto ${\displaystyle x^{*}\in \mathbb {R} ^{n}}$. Si existen constantes ${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$ y ${\displaystyle \nu _{j}\ (j=1,\ldots ,l)}$ tales que

${\displaystyle \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}(x^{*})=0}$

${\displaystyle \mu _{i}g_{i}(x^{*})=0\;{\mbox{para todo}}\;i=1,\ldots ,m,}$

entonces el punto ${\displaystyle x^{*}}$ es un mínimo global.

Referencias

1. W. Karush (1939). Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois.
2. H. W. Kuhn,Tucker, A. W., Proceedings of 2nd Berkeley Symposium, Nonlinear programming, University of California Press, 1951, Berkeley

Bibliografía

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, pp. 473-485 (2005).

Véase también

• Teorema de Karush Kuhn Tucker aplicado a un Problema de Programación No Lineal
• El artículo de A. Kuhn y W. Tucker (en inglés)

• Datos: Q2075125