El método o algoritmo de Frank Wolfe fue propuesto en 1956 por Marguerite Frank y Philip Wolfe y se aplica a problemas de optimización matemática con una función objetivo no lineal convexa y cuyo dominio de soluciones factibles esta compuesto exclusivamente por restricciones lineales, es decir, es un conjunto convexo (en consecuencia el problema es convexo).
Consideremos el siguiente problema que asumiremos cumple con el formato anteriormente descrito:
Dada una aproximación a la solución óptima del problema, podemos resolver un problema más sencillo que aproxime al problema P), suponiendo factible.
O equivalentemente resolviendo el siguiente problema:
Que puede ser resuelto mediante el Método Simplex. Denotamos por la solución óptima de . El método contempla en seguida una minimización de un problema unidimensional que equivale a escoger un escalar de modo que:
En seguida se define la siguiente aproximación al óptimo como:
Que equivale a definir como la solución óptima de f restringida al conjunto de puntos que determina al segmento que une con .
Ejemplo: Aplicar el método de Frank Wolfe al siguiente problema no lineal restringido (convexo). Notar que la matriz hessiana o de segundas derivadas de la función objetivo es positiva definida.
Realizamos la primera iteración del método que da origen al siguiente problema de Programación Lineal:
La resolución es trivial y puede ser alcanzada de forma gráfica con Geogebra. La solución óptima es según se aprecia a continuación:
Luego buscamos la solución para el problema unidimensional en términos del parámetro :
Finalmente se obtiene concluyendo una iteración del método de Frank Wolfe. Se propone al lector seguir las iteraciones a contar de este punto. Por ejemplo se puede verificar que . (Hint: La solución óptima se alcanza en .
El Método del Centroide es una técnica para ubicar instalaciones que considera las instalaciones existentes, las distancias entre ellas y la cantidad de productos a transportar entre las mismas. Se suele suponer que los costos de envío o transporte de entrada y salida son iguales y no incluye costos de envío especiales.
La aplicación del Método del Centroide requiere ubicar las instalaciones existentes en un sistema de coordenadas. La elección de dicho sistema de coordenadas es completamente arbitraria, no obstante, actualmente son populares las medidas de longitud y latitud debido a la rápida adopción de los sistemas GPS. Sin perjuicio de lo anterior y con el objetivo de representar ejemplos sencillos se pueden utilizar coordinadas arbitrarias (X,Y).
El Centroide se encuentra calculando las coordenadas X e Y que dan como resultado el costo de transporte mínimo. Para ello se utilizan las fórmulas:
Donde:
Ejemplo Método del Centroide
Se desea determinar la ubicación óptima de una planta productiva (en adelante Planta E) mediante el Método del Centroide con respecto a otras 3 plantas demandantes a las cuales abastece de un cierto producto, que en lo sucesivo denotaremos por A, B y C y cuyas coordenadas (X,Y) son (150,75), (100,300) y (275,380), respectivamente. En este contexto, las plantas A, B y C requieren 6.000, 8.200 y 7.000 unidades anuales, respectivamente, las cuales serán transportadas desde la Planta E. Se supone una relación lineal entre los volúmenes enviados y los costos de envío (sin cargos adicionales).
Dada la información anterior calculamos las coordenadas en X e Y de la Planta E.
¿Minimizará la localización propuesta para la Planta E por el Método del Centroide la sumatoria de la distancia euclidiana respecto a las plantas demandantes A, B y C?. Para responder esta pregunta formulamos el siguiente modelo de Programación No Lineal no restringida:
Luego de implementar el problema anterior en Solver de Excel obtenemos la coordenada (X,Y)=(175,00, 251,67) que determina una sumatoria de distancias totales de 66.266,67[u] que es levemente inferior a la obtenida a través del Método del Centroide donde la sumatoria de las distancias alcanza las 66.662,80[u].
Esta diferencia menor se explica por la relativa similitud de los resultados obtenidos a través de los 2 métodos según se aprecia en la siguiente representación gráfica:
El método de multiplicadores de Lagrange (el cual es generalizado por las condiciones de optimalidad de Karush-Kuhn-Tucker) permite abordar la resolución de modelos de programación no lineal que consideran restricciones de igualdad. En este sentido y como resulta natural, el dominio de soluciones factibles considerará exclusivamente aquellas soluciones que permiten verificar el cumplimiento de la igualdad de dichas restricciones. Por el contrario, un problema de optimización que considera inecuaciones como restricciones, sólo requiere que éstas se cumplan y no necesariamente se deberá forzar el cumplimiento de ellas en igualdad (activas).
En general las condiciones de Lagrange se aplican a un problema que tiene la siguiente estructura:
Que da origen a la función Lagrangiana asociada a dicho problema:
Consideremos el siguiente problema de Programación No Lineal restringido que nos permitirá ilustrar la aplicación del método de Lagrange.
Notar que el problema adopta la estructura estándar previamente descrita y considera una única restricción de igualdad. No se incluye en particular condiciones de no negatividad, que en caso de estar presentes justificarían la aplicación del Teorema de Karush-Kuhn-Tucker.
En este contexto, un mínimo local para el problema propuesto debe satisfacer las condiciones necesarias de primer orden de Lagrange:
Que da origen al siguiente sistema de ecuaciones:
Donde la resolución es trivial y corresponde a x1=2, x2=2 y λ1=-4. Notar que el multiplicador de Lagrange asociado a una restricción de igualdad es libre de signo, en consecuencia la solución propuesta satisface las condiciones necesarias de primer orden.
Adicionalmente se cumplen las condiciones de segundo orden pues:
Es positiva definida (función objetivo estrictamente convexa y restricción lineal que define un conjunto convexo). Luego, el problema es convexo y en consecuencia x1=2 y x2=2 es mínimo global y solución óptima del problema. Este resultado por cierto es consistente con la representación gráfica del problema, donde la solución óptima corresponde al punto A, donde la restricción (color naranjo) es tangente a la curva de nivel que representa a la circunferencia de menor radio que intercepta el dominio de soluciones factibles.
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:
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.
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).
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:
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:
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:
Al calcular los gradientes respectivos se obtiene:
Lo cual da origen al siguiente sistema de ecuaciones:
Reemplazando x1=2 y x2=1 podemos despejar los valores de los multiplicadores los cuales cumplen con las condiciones de no negatividad:
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.
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:
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:
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:
y
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.
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:
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.
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.
A diferencia de la Programación Lineal donde sus distintas aplicaciones corresponden a problemas de optimización convexos (situación que facilita la resolución computacional), en Programación No Lineal no existen garantías a priori que permita garantizar que un modelo en particular será un problema convexo.
Es decir, una aplicación de Programación No Lineal puede ser un problema convexo o un problema no convexo.
En este artículo abordaremos a través de un ejemplo sencillo las dificultades prácticas y algorítmicas asociadas a la resolución de un modelo de Programación No Lineal no convexo.
Consideremos el siguiente modelo matemático no lineal con restricciones:
Una primera aproximación a su resolución consiste en graficar la función anterior utilizando Geogebra:
Se puede observar que la función es no convexa, constatándose adicionalmente la presencia de mínimos locales (por ejemplo los Puntos B y C) y mínimo global (Punto A).
En este sentido la expectativa que debiéramos tener al implementar este problema computacionalmente es obtener la solución óptima para un valor de x en el intervalo entre [4,5] (por simple inspección) lo que corresponde al Punto A de la gráfica anterior.
Una alternativa de resolución computacional para este problema es utilizar AMPL como lenguaje de programación matemática y MINOS 5.5 como solver de resolución. El código de la implementación y los resultados alcanzados se muestra a continuación:
La solución óptima encontrada por el algoritmo corresponde a x=1 (Punto C) lo que permite alcanzar un valor en la función objetivo igual a cero: f(1)=0. Claramente según nuestro gráfico esta solución corresponde sólo a un mínimo local aun cuando el programa sugiere que es el mínimo global del problema.
Otra alternativa de resolución consiste en la utilización de Solver. En primera instancia el algoritmo converge a la solución x=1 con f(1)=0.
Sin embargo, si manualmente editamos el valor de la celda color amarillo B3 (variable de decisión) a «2» y reoptimizamos con Solver se obtiene lo siguiente:
Se alcanza ahora una nueva solución con x=2,45608774 con f(2,45608774)=-1,41869663 lo que corresponde al Punto B de nuestro gráfico y que si bien corresponde a un mínimo local provee un valor menor en la función objetivo al ser comparado con el Punto C. En este contexto resulta razonable considerar el valor «4» para la celda cambiante como punto de partida para una nueva reoptimización:
Ahora obtenemos lo que correspondería al mínimo global del problema (Punto A) con solución óptima x=4,64443285 y valor óptimo f(4,64443285)=-3,63143221.
Finalmente hemos resuelto el problema con What’sBest! donde en el siguiente tutorial de nuestro canal de Youtube mostramos los detalles de la implementación:
Luego de reoptimizar sobre la solución local alcanzada en primera instancia se obtiene el mínimo global del problema (Punto A):
Conclusiones: Las principales dificultades enfrentadas al intentar resolver un modelo de Programación No Lineal no convexo es no tener la certeza si la solución obtenida a través de una herramienta computacional corresponde a un mínimo local o mínimo global.
Con las herramientas presentadas en este artículo fue necesario reoptimizar sobre soluciones obtenidas en primera instancia para encontrar la solución óptima del problema. Cabe destacar que en este ejemplo al disponer de una representación gráfica del problema sabíamos de antemano cuál era la solución del problema lo cual nos permitía contrastar los resultados computacionales. En este sentido claramente un modelo de mayor complejidad (por ejemplo, un mayor número de variables de decisión y/o restricciones) una aproximación intuitiva no tiene sentido práctico.
En este contexto una de las principales áreas actuales de desarrollo de la Investigación de Operaciones es proveer de métodos numéricos de resolución que permita abordar de forma eficiente la complejidad de esta categoría de problemas de optimización.
a la solución óptima del problema, podemos resolver un problema más sencillo que aproxime al problema P), suponiendo 
la solución óptima de 
. El método contempla en seguida una minimización de un problema unidimensional que equivale a escoger un escalar 
de modo que:
como la solución óptima de f restringida al conjunto de puntos que determina al segmento que une 
según se aprecia a continuación:
:
concluyendo una iteración del método de Frank Wolfe. Se propone al lector seguir las iteraciones a contar de este punto. Por ejemplo se puede verificar que 
. (Hint: La solución óptima se alcanza en 
.
y 
