Condiciones KKT para programación cuadrática (I)

Para que sea concreto, primero considérese el ejemplo anterior. Comenzando con la forma dada en la sección anterior, sus condiciones KKT son las siguientes

Programación cuadrática (II)

para toda x, es decir, que Q es una matriz positiva semidifinida.) Se describirá uno de estos algoritmos, que es muy aceptado porque sólo emplea el método símple con una pequeña modificación. La clave de este enfoque es construir las condiciones KKT de la sección anterior y después reexpresar estas condiciones demanera conveniente que se parezca a programación lineal. Por esto, antes de describir el algoritmo, se desarrollará esta forma conveniente.

Programación cuadrática (I)

Como se indicó en la sección 14.3, el problema de programación cuadrática difiere del problema de programación lineal nada más en que la función objetivo incluye también términos xj² y xixj (i≠j). Así, si se usa la notación matricial comola que se introdujo en la sección 5.2, el problema es encontrar x para

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (IV)

Toda vez que se encontró una solución, no se considerarán casos adicionales.

En problemas más complicados que éste puede ser difícil, si no es materialmente imposible, derivar una solución óptima directa de las condiciones KKT. De todas maneras estas condiciones proporcionan información valiosa en cuanto a la identidad de una solución óptima y también permiten verificar que una solución propuesta sea óptima.

Existen mucha aplicaciones indirectas valiosas de las condiciones KKT. Una de ellas surge en la teoría de la dualidad desarrollada par programación no lineal, que se puede poner en parelelo con la teoría de la dualidad para programación líneal presentada en el capítulo 6. En particular, para cualquier problema de maximización restringida (llámese problema primal), se pueden usar las condiciones KKT para definir un problema dual asociado, que es un problema de minización restringido. Las variables del problema dual consisten en multiplicadores de Lagrange, ui = (i = 1,2,......, m) y las variables primales xj (j = 1,2....., n). En el caso especial de que el problema primal es un problema de programación lineal, las variables xj desaparecerán del problema dual y quedará el familiar problema dual de programación líneal (en el que las variables ui, aquí corresponden a las variables yi del capítulo 6). Cuando un problema primal es un problema de programación convexa, es posible establecer relaciones entre el problema primal y el problema dual, que son muy parecidas a las de programación lineal. Por ejemplo,la propiedad dualidad fuerte de la sección 6.1, que establece que los valore óptimos de las funciones objetivo son iguales, también se cumple aquí. Más aún, los valores de las variables ui en una solución óptima para el problema dual,de nuevo se pueden interpretar como los precios sombra (véanse las secciones 4.7 y 6.2); es decir, proporcionan la tasa a la que puede aumentar el valor óptimo de la función objetivo para el problema primal, si se aumenta (ligeramente) el lado derecho de la restricción correspondiente. Como la teoría de dualidad para programación no lineal es un tema relativamente avanzado se pide al lector interesado que consulte otros libros para obtener la información.

En la sección siguiente se verá otra aplicación indirecta de la condiciones KKT.

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (III)

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (II)

A continuación se describen los pasos para resolver las condiciones KKT para este ejemplo específico.

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (I)

Par ilustrar esta formulación y la aplicación de las condiciones KKT, considérese el siguiente problema de programación no lineal de dos variables.