convexidad Archivos - Gestión de Operaciones

Método de Planos Cortantes (Optimización Dual)

En un tutorial anterior discutimos sobre la Relajación Lagrangeana, y gracias a dicho ejemplo, vimos que al variar los valores de las variables asociadas a la relajación (más conocidos como los Multiplicadores de Lagrange), el valor de la función objetivo del Problema Dual Lagrangeano se va aproximando al valor que se obtiene al resolver el problema original. En palabras simples, lo que se realizó en ese ejemplo fue optimizar los multiplicadores.

En este artículo, lo que veremos es una forma distinta de optimizar dichas variables, mediante un algoritmo que lleva el nombre de Método de Planos Cortantes o Método de Planos de Corte (o simplemente Planos Cortantes). Este algoritmo también se conoce con el nombre de Cortes basados en Descomposición de Benders, y esto es principalmente debido a que este procedimiento utiliza inecuaciones muy similares a las que se ocupan en el método propuesto por J.F. Benders.

La idea fundamental detrás del algoritmo de planos cortantes es comenzar con una solución inicial factible para el problema relajado, para después “cortar” o sacar dicha solución y cambiarla por otra que mejore el valor de la función objetivo que se está optimizando (es decir el valor del Problema Dual Lagrangeano).

Además, para iniciar este método es necesario tener una consideración especial:

El conjunto de puntos que constituyen las soluciones enteras factibles del problema relajado debe ser acotado.

¿Por qué?: Debido a que el algoritmo de planos cortantes utiliza estos puntos, por lo que si el conjunto fuera no acotado, entonces el algoritmo nunca convergería (es decir, nunca terminaría de iterar). Este conjunto acotado se conoce como la envoltura convexa, pero cuidado: no es cualquiera, es la envoltura convexa de las soluciones enteras del problema relajado.

Veamos entonces cómo funciona este método de forma general. Supongamos que tenemos el siguiente problema, en donde el segundo conjunto de restricciones $Cx\leq d$ es “difícil” y complica la resolución, por lo tanto lo sacamos y lo llevamos a la función objetivo, a lo cual llamaremos el problema relajado:

Además, supongamos que es posible enumerar todos los puntos que son factibles para nuestro problema relajado (es decir, los que están dentro de la envoltura convexa). Si pudiéramos hacer eso, entonces bastaría con evaluar en la función objetivo todos esos puntos, y ver cuál entrega el menor valor: este punto sería entonces nuestra solución óptima.

Lo que se menciona anteriormente, se puede representar matemáticamente de la siguiente forma, donde p es la cantidad de puntos que pertenecen a las soluciones enteras de este problema relajado:

Con lo anterior en consideración, podemos entonces expresar nuestro Problema Dual Lagrangeano de la siguiente forma:

Lo cual, se puede volver a reformular y expresar mediante un problema de optimización. Esta reformulación se conoce como el Problema Maestro, en donde ocupamos una variable auxiliar u y queda expresado de la siguiente forma:

Esta reformulación es importante de entender, ya que gracias a que se dispone de cada uno de los puntos que pertenecen a las soluciones enteras del problema relajado (recuerda que dijimos que se podían enumerar), entonces cada una de las restricciones del tipo:

Constituyen un corte para nuestro problema.

Esto nos lleva a la siguiente pregunta: ¿si tenemos todos los puntos, entonces agregamos todos los cortes inmediatamente (simultáneamente)?

La respuesta es NO, ya que esto sería un trabajo muy tedioso, y tomaría mucho tiempo computacional. Para esto existe el algoritmo de los planos cortantes, para ir agregando iterativamente los cortes, de manera tal que tome menos tiempo que agregarlos todos en conjunto.

Como hemos llamado a la reformulación anterior el Problema Maestro, entonces necesitamos un sub-problema, o problema esclavo. Este sub-problema corresponde al problema relajado que discutimos al principio del desarrollo:

Finalmente, la última pregunta que nos podemos hacer es con cuántos cortes partir. Para la pregunta anterior no hay una respuesta que pudiésemos dar a priori como exacta, pero una buena aproximación es que la cantidad de cortes iniciales (o puntos iniciales a utilizar) sea igual a la cantidad de variables o penalizadores, incrementado en una unidad, es decir:

Número de Cortes Iniciales = Número de Penalizadores + 1

Algoritmo de Planos Cortantes

El algoritmo de planos cortantes se puede enunciar mediante los siguientes pasos. Además, luego encontrarás un resumen mediante un diagrama de flujo:

Sea k=1. Sea x1, x2 ,x3 ,…, xr la cantidad de puntos necesarios para iniciar el algoritmo. Crear los cortes del tipo $\mu \leq c^{T}x_{i}+\lambda ^{T}(Cx_{i}-d)$ con dichos puntos.
Resolver el Problema Maestro.
El problema maestro entregará una actualización para los valores de los Multiplicadores de Lagrange. Con ellos, resolver el sub-problema.
Al resolver el sub-problema, se encontrará un nuevo punto perteneciente a las soluciones factibles del problema relajado. Verificar el criterio de parada. Si se cumple, terminar; sino, crear un nuevo corte.
Agregar el corte al Problema Maestro, hacer k=k+1 y volver a 2.

La teoría de este procedimiento puede ser un poco complicada, así que veamos un ejemplo.

Ejemplo Método de Planos Cortantes

Supongamos el siguiente problema de optimización, en donde las primeras cuatro inecuaciones serán las que permanecen en el problema relajado, y las ultimas 4 son las inecuaciones “complicadas” que serán incorporadas a la función objetivo.

Sin embargo, antes de ello presentaremos una representación gráfica del problema propuesto. El área achurada de color verde corresponde al dominio de soluciones factibles de la relajación continua del problema, es decir, omitiendo las condiciones de integralidad para las variables de decisión.

En este contexto la solución óptima de la relajación continua es el vértice B donde x=30/11 e y=42/11, con valor óptimo V(PL)=186/11=16,909 (aprox).

De forma análoga, la solución óptima del problema entero se encuentra identificado con la letra F con x=3 e y=3, siendo el valor óptimo V(PE)=15.

Notar que la representación gráfica anterior y la obtención de la solución óptima de la relajación continua y del modelo de Programación Entera propuesto tiene un fin sólo ilustrativo, de modo que favorezca la comprensión de los conceptos que presentamos más adelante.

A continuación retomamos el procedimiento del Algoritmo de Planos Cortantes. Para ello escribiremos el problema relajado (no confundir con la relajación continua!) de la siguiente forma:

Al escribir este problema, los puntos pertenecientes a la envoltura convexa de las soluciones enteras del problema relajado son los siguientes:

Una representación gráfica de la envoltura convexa del problema relajado se muestra a continuación:

A pesar de que el método sugiere una cantidad de cortes iniciales, como se puede ver en este ejemplo son sólo 8 puntos (denotados por E, F, G, H, I, J más las coordenadas (2,3) y (3,2)), por lo que no seguiremos esta sugerencia. Para iniciar, hacemos k=1 y utilizaremos el punto (1,4) para crear el siguiente corte:

$\mu \geq 14+8\lambda _{1}-4\lambda _{2}+8\lambda _{3}+23\lambda _{4}$

Por lo que el Problema Maestro en la iteración k=1 es:

Al resolver este problema, la solución óptima es: $\lambda_{1}=0,\lambda_{2}=3,5,\lambda_{3}=0,\lambda_{4}=0,\mu=0$ .

Con estos valores para los Multiplicadores de Lagrange, resolvemos el problema relajado:

El cual, entrega como resultado los valores x=5 e y=1, con un valor objetivo de 58,5.

Luego verificamos el criterio de parada ( $0\neq 58,5$ ) por lo que el nuevo punto que nos permite generar un nuevo corte:

$\mu \geq 13+5\lambda _{1}+13\lambda _{2}+\lambda _{3}+24\lambda _{4}$

Hacemos k=2 y el nuevo Problema Maestro es:

Al resolver este problema, la solución óptima es: $\lambda_{1}=0,\lambda_{2}=0,059,\lambda_{3}=0,\lambda_{4}=0,\mu=13,76$ .

Con estos valores para los Multiplicadores de Lagrange, resolvemos el problema relajado:

El cual, entrega como resultado los valores x=2 e y=4, con un valor objetivo de 15,882.

Verificamos el criterio de parada ( $13,76\neq 15,882$ ) por lo que el nuevo punto que nos permite generar un nuevo corte:

$\mu \geq 16+11\lambda _{1}-2\lambda _{2}+7\lambda _{3}+20\lambda _{4}$

Hacemos k=3 y el nuevo Problema Maestro es:

Al resolver este problema, la solución óptima es: $\lambda_{1}=0,\lambda_{2}=0,2,\lambda_{3}=0,\lambda_{4}=0,\mu=15,6$ .

Con estos valores para los Multiplicadores de Lagrange, resolvemos el problema relajado:

El cual, entrega como resultado los valores x=5 e y=1, con un valor objetivo de 15,6, verificamos el criterio de parada (15,6=15,6), por lo que como se cumple el criterio de parada y el algoritmo se detiene.

Al estar optimizando los valores para una Relajación Lagrangeana, hemos encontrado un valor que cumple con lo siguiente:

$Z_{PE}\leq Z_{H}\leq Z_{PL}$

Particularmente para este problema se cumple que:

$15\leq 15,6\leq 16,909$

Mis sinceros agradecimientos a mi amigo Javier Maturana Ross en la elaboración de este artículo, esperando nos pueda seguir contribuyendo con sus aportes y conocimientos al sitio de Gestión de Operaciones.

Ejemplo del Método de Frank Wolfe en Programación No Lineal

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 $x^{k}$ a la solución óptima del problema, podemos resolver un problema más sencillo que aproxime al problema P), suponiendo $x^{k}$ factible.

O equivalentemente resolviendo el siguiente problema:

Que puede ser resuelto mediante el Método Simplex. Denotamos por $x_{PL}^{k}$ la solución óptima de $PL_{k}$ . El método contempla en seguida una minimización de un problema unidimensional que equivale a escoger un escalar $\alpha _{k}$ de modo que:

En seguida se define la siguiente aproximación al óptimo como:

Que equivale a definir $x^{k+1}$ como la solución óptima de f restringida al conjunto de puntos que determina al segmento que une $x^{k}$ con $x_{PL}^{k}$ .

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 $x_{PL}^{0}=(0,3)$ según se aprecia a continuación:

Luego buscamos la solución para el problema unidimensional en términos del parámetro $\alpha$ :

Finalmente se obtiene $x^{1}=x^{0}+\frac{2}{3}(x_{PL}^{0}-x^{0})=(0,2)$ 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 $x_{PL}^{1}=(2,0)$ . (Hint: La solución óptima se alcanza en $(x_{1},x_{2})=(1,\frac{3}{2})$ .

Programación No Lineal no Convexo

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.