Teorema de Karush Kuhn Tucker en PNL (Ejercicios Resueltos)

Las condiciones de optimalidad establecidas en el Teorema de Karush Kuhn Tucker (KKT) permiten abordar la resolución de modelos de Programación No Lineal que consideran tanto restricciones de igualdad (ecuaciones) como desigualdad (inecuaciones).

En términos comparativos las condiciones de KKT son más generales que el Método de Lagrange el cual se puede aplicar a problemas no lineales que consideran exclusivamente restricciones de igualdad.

En el siguiente artículo mostraremos cómo utilizar el Teorema de Karush Kuhn Tucker para resolver un problema de Programación No Lineal con 2 variables de decisión.

Sin pérdida de generalidad un modelo de Programación No Lineal se puede representar a través del siguiente formato:

problema-general-kkt

Luego podemos reescribir cualquier problema en dicha estructura manteniendo la equivalencia de la representación matemática. Para ejemplificar lo anterior consideremos el siguiente modelo de optimización no lineal que resulta de interés su resolución.

modelo-pnl

El problema anterior se puede representar gráficamente a través del software Geogebra de modo de encontrar su solución óptima (x1=2 y x2=1) en el par ordenado etiquetado con la letra «C»  en el gráfico a continuación, con valor óptimo V(P)=2.

El conjunto de factibilidad corresponde al área achurada. Adicionalmente se puede observar que en la solución óptima se encuentran activas las restricciones 1 y 3 (el resto de las restricciones por cierto se cumple pero no en igualdad).

resolucion-grafica-programa

Por supuesto la resolución mediante el Método Gráfico es sólo referencial y se ha utilizado en este caso para corroborar los resultados a obtener en la aplicación del teorema. En este contexto el problema en su forma estándar es simplemente:

forma-estandar-kkt

Notar que sólo fue necesario cambiar la forma de las restricciones de no negatividad (esto se puede hacer multiplicando por -1 cada una de ellas). Cabe destacar que en este caso en particular el problema no considera restricciones de igualdad.

Luego las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT) están dadas por:

condiciones-kkt-primer-orde

Por ejemplo, si en las condiciones generales anteriores consideramos el problema no restringido (asumiendo que todas las restricciones son inactivas) la solución óptima por simple inspección es x1=3 y x2=2, que corresponde a la coordenada «E» de la gráfica anterior y que se puede observar no es una solución factible para el problema.

De este modo la circunferencia de menor radio que intercepta el conjunto de factibilidad es precisamente aquella que pasa por la coordenada «C» donde las restricciones 1 y 3 se cumplen en igualdad, razón por la cual las cuales activaremos de forma simultanea:

desarrollo-condiciones-kkt

Al calcular los gradientes respectivos se obtiene:

kkt-primer-orden

Lo cual da origen al siguiente sistema de ecuaciones:

sistema-ecuaciones-primer-o

Reemplazando x1=2 y x2=1 podemos despejar los valores de los multiplicadores los cuales cumplen con las condiciones de no negatividad:

solucion-sistema-primer-ord

Adicionalmente se puede verificar que x1=2 y x2=1 satisface las restricciones omitidas (2, 4 y 5) por lo cual se puede afirmar que dicha solución cumple las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT).

A continuación verificamos el cumplimiento de las condiciones de segundo orden de KKT, en particular lo que tiene relación con la convexidad del problema. Para ello calculamos la Matriz Hessiana o de segundas derivadas de la función objetivo y las restricciones activas.

condiciones-de-segundo-orde

El primer determinante de la Matriz Hessiana es D1=8/3>=0 y el segundo determinante es D2=(8/3)*(8/3)=(64/9)>=0. Se concluye que el problema es convexo y por tanto x1=2 y x2=1 es mínimo local y global para el problema. La resolución computacional de este problema con AMPL corrobora los resultados alcanzados:

solucion-ampl-problema-no-l

Ejercicio Resuelto Teorema de Karush Kuhn Tucker (KKT)

Un asesor financiero está evaluando la compra de acciones de firmas de cierto sector industrial. Desea minimizar la variación de la cartera resultante compuesta por acciones de dos firmas, pero también quiere tener un tasa de retorno de al menos un 9%. Después de obtener datos históricos sobre la variación y rendimientos de ambos instrumentos, desarrolla el siguiente modelo de optimización no-lineal:

ejemplo kkt

Donde x e y representan la proporción de dinero invertida en cada acción. Formule explícitamente todas las condiciones de optimalidad del Teorema de Karush-Kuhn-Tucker para este problema y úselas para determinar la cartera óptima. Justifique adecuadamente su respuesta. Analice todos los posibles casos.

Respuesta:

Según el Teorema de Weierstrass, el problema admite solución óptima pues tiene una función objetivo continua y un dominio de soluciones factibles cerrado y acotado (que se puede apreciar incluso geométricamente). En este sentido el dominio de soluciones factibles son los puntos en la recta que unen los pares ordenados etiquetados con las letras A y B, donde:

A=(x,y)=(\frac{1}{3},\frac{2}{3}) y B=(x,y)=(1,0)

representación gráfica teorema de kkt

Más aún es fácil ver que la Matriz Hessiana de la función objetivo es positiva definida y por ende es una función (estrictamente) convexa.

\bigtriangledown f(x,y)=(0.32x+0.20y,0.20x+0.18y)

H=D^{2}(x,y)=\begin{pmatrix}0.32&0.20\\0.20&0.18\end{pmatrix}

Como las restricciones son lineales, y la función objetivo es estrictamente convexa, resulta que es problema propuesto es un problema convexo.

Lo anterior (que el problema sea convexo) implica que las condiciones de optimalidad de Karush-Kuhn-Tucker son necesarias y suficientes para hallar la solución óptima del mismo.

Las condiciones del Teorema de Karush-Kuhn-Tucker para este problema son:

i)
0.32x + 0.20y + λ1 – 0.11μ1 – μ2 = 0
0.18y + 0.20x + λ1 – 0.08μ1 – μ3 = 0
ii)
(-0.11x – 0.08y + 0.09) μ1 = 0
-x1 μ2 = 0 -x3 μ3 = 0
iii)
x + y = 1
0.11x + 0.08y ≥ 0.09
x≥0, y≥0
iv)
μ1≥0, μ2≥0, μ3≥0

Al considerar el esquema de activación de restricciones, siempre debe estar activa la ecuación x+y =1 y lo que cabe entonces es no activar ninguna inecuación o a lo sumo activar una de ellas.

Los diferentes casos que se podrían llegar a analizar son:

i) Ninguna inecuación activa.

Tomamos μ1=0, μ2=0, μ3=0 y resolvemos:

0.32x + 0.20y + λ1 = 0
0.18y + 0.20x + λ1 = 0
x + y = 1

Cuya solución resulta ser: x=-0.2 e y=1.2 que es infactible.

ii) Activando sólo la inecuación 0.11x + 0.08y ≥ 0.09.

Tomamos μ2=0, μ3=0 y resolvemos:

0.32x + 0.20y + λ1 – 0.11μ1 = 0
0.18y + 0.20x + λ1 – 0.08μ1 = 0
x + y = 1
0.11x + 0.08y = 0.09

Cuya solución resulta ser: x=1/3 e y=2/3 con multiplicadores λ1=0,04444453 y μ1=1,777777502, con lo cual tenemos un punto que cumple con todas las condiciones del teorema.

iii) Activando sólo la inecuación x≥0.

Tomamos μ1=0, μ3=0 y resolvemos:

0.32x + 0.20y + λ1 – μ2 = 0
0.18y + 0.20x + λ1 = 0
x + y = 1
x = 0

Cuya solución resulta ser: x=0 e y=1 con multiplicadores λ1=-0.18 y μ2 = 0.02 pero no verifica 0.11x + 0.08y = 0.08 ≥ 0.09.

iv) Activando sólo la inecuación y≥0.

Tomamos μ1=0, μ2=0 y resolvemos:

0.32x + 0.20y + λ1 = 0
0.18y + 0.20x + λ1 – μ3 = 0
x + y = 1
y = 0

Cuya solución resulta ser: x=1 e y=0 con multiplicadores λ1=-0.32 y μ3=-0.12 y este último no cumple con la no-negatividad.

En consecuencia, la solución óptima es aquella obtenida en el caso ii) pues el problema es convexo: x=1/3 e y=2/3. Dicha solución corresponde al par ordenado etiquetado con la letra A en la gráfica anterior. El valor óptimo es 0.102222 y se obtiene simplemente al evaluar la solución óptima en la función objetivo.

Cómo resolver un modelo de Programación No Lineal con AMPL

La complejidad adicional que representan los modelos de Programación No Lineal en comparación a los modelos de Programación Lineal, justifica el desarrollo de algoritmos especializados que permitan abordar de forma más eficiente la resolución de este tipo de modelos.

En este contexto, uno de los lenguajes de programación matemática más conocidos y confiable para formular diversos modelos de optimización es AMPL (www.ampl.com). Su popularidad ha sido sustentada adicionalmente por el desarrollo de distintos algoritmos de resolución (o solvers) que son compatibles con AMPL y que permiten resolver modelos de Programación Lineal, Programación No Lineal, Programación Entera, entre otras.

página web ampl

Estos solvers han sido resultado del trabajo de prestigiosas universidades y centros de investigación, en algunos casos en conjunto con empresas de software. El servidor NEOS consolida esta información en Internet.

Solver NEOS

A continuación mostraremos cómo resolver un modelo de Programación No Lineal sencillo utilizando la versión estudiantil de AMPL y utilizando el solver de resolución MINOS versión 5.5. Para ello debemos descargar el archivo «amplcml.zip» a nuestro computador, descomprimir éste y luego ejecutar el archivo de nombre «ampl».

Consideremos el siguiente modelo de Programación No Lineal:

Modelo Minimización PNL

La sintaxis utilizada por AMPL es bastante intuitiva como se aprecia a continuación en la resolución del ejemplo:

  • var x1>=0;     # definición de la variable x1 estableciendo condición de no negatividad.
  • var x2>=0;     # definición de la variable x2 estableciendo condición de no negatividad.
  • minimize funcionobjetivo: (x1-2)^2+(x2-4)^2;     # definición de la función objetivo. El nombre de la misma es arbitrario.
  • subject to restriccion1: 2*x1+4*x2<=12;     # se define la inecuación correspondiente a la restricción 1.
  • subject to restriccion2: 4*x1+3*x2<=16;     # se define la inecuación correspondiente a la restricción 2.
  • solve;     # una vez implementado el modelo se ejecuta su resolución haciendo uso de MINOS 5.5 (opción por defecto)

PNL en AMPL

La solución óptima es X1=1,2 y X2=2,4 con valor óptimo V(P)=3,2. (Puedes consultar aquí la Resolución Gráfica de este modelo). Adicionalmente se pueden corroborar los resultados a través de la aplicación de las condiciones de optimalidad de Karush-Kuhn-Tucker (KKT).