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.

Consideremos el siguiente problema general:

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]​

Supongamos que la función objetivo, por ejemplo, a minimizar, es ${displaystyle f:mathbb {R} ^{n} ightarrow mathbb {R} }$ y las funciones de restricción son ${displaystyle g_{i}:,!mathbb {R} ^{n} ightarrow mathbb {R} }$ y ${displaystyle h_{j}:,!mathbb {R} ^{n} ightarrow mathbb {R} }$. Además, 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 u _{j} (j=1,...,l)}$ tales que:

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 eq 0}$). Estas incluyen:

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.

Sea ${displaystyle f:mathbb {R} ^{n} ightarrow mathbb {R} }$ la función objetivo y las funciones de restricción ${displaystyle g_{i}:mathbb {R} ^{n} ightarrow mathbb {R} }$ sean funciones convexas y ${displaystyle h_{j}:mathbb {R} ^{n} ightarrow mathbb {R} }$ sean las funciones de afinidad, y séa un punto ${displaystyle x^{*}}$. Si existen constantes ${displaystyle mu _{i}geq 0 (i=1,ldots ,m)}$ y ${displaystyle u _{j} (j=1,ldots ,l)}$ tales que

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