Raul E. Lopez Briega

Matemáticas, análisis de datos y python

Problemas de Optimización con Python

Optimización

Introducción

La optimización es fundamental para cualquier problema relacionado con la toma de decisiones, ya sea en ingeniería o en ciencias económicas. La tarea de tomar decisiones implica elegir entre varias alternativas. Esta opción va a estar gobernada por nuestro deseo de tomar la "mejor" decisión posible. Que tan buena va a ser cada una de las alternativas va a estar descripta por una función objetivo o índice de rendimiento. La teoría y los métodos de optimización nos van a ayudar a seleccionar la mejor alternativa de acuerdo a esta función objetivo dada. El área de optimización ha recibido gran atención en los últimos años, principalmente por el rápido desarrollo de las ciencias de computación, incluido el desarrollo y la disponibilidad de herramientas de software sumamente amigables, procesadores paralelos de alta velocidad, y redes neuronales artificiales. El poder de los métodos de optimización reside en la posibilidad de determinar la solución óptima sin realmente tener que probar todos los casos posibles. Para logar esto, se utiliza un nivel modesto de Matemáticas y se realizan cálculos numéricos iterativos utilizando procedimientos lógicos claramente definidos o algoritmos implementados en computadoras.

¿Qué es un problema de optimización?

Un problema de optimización comienza con un conjunto de variables independientes o parámetros, y a menudo incluye condiciones o restricciones que definen los valores aceptables de estas variables. Tales restricciones se denominan las limitaciones del problema. El otro componente esencial de un problema de optimización es una medida única de "bondad", denominada función objetivo, la cual va a depender también de las variables independientes. La solución al problema de optimización va a estar dada por un conjunto de valores permitidos para las variables independientes, de acuerdo con las limitaciones del problema, en los que la función objetivo asume un valor óptimo. En términos matemáticos, la optimización implica normalmente maximizar o minimizar la función objetivo.

Requisitos para la aplicación de los métodos de optimización

Para aplicar los resultados matemáticos y técnicas numéricas de la teoría de optimización a problemas concretos, es necesario delinear claramente los límites del sistema a optimizar, definir los parámetros cuantitativos que se utilizaran como criterio en base al cual serán clasificadas las alternativas para determinar la "mejor" opción, seleccionar las variables que se utilizarán para caracterizar o identificar alternativas; y definir el modelo que exprese la forma en que las variables estarán relacionadas. Una buena formulación del problema es la clave para el éxito de un problema de optimización y es en alto grado un arte. Se aprende a través de la práctica y el estudio de aplicaciones exitosas y se basa en el conocimiento de las fortalezas, debilidades y particularidades de las técnicas proporcionadas por los distintos métodos de optimización.

Clasificación de los problemas de optimización

Un paso importante en cualquier problema de optimización es clasificar nuestro modelo, ya que los algoritmos para resolver problemas de optimización generalmente están diseñados para atacar un tipo de problema en particular. Algunas de las principales clasificaciones que vamos a poder encontrar son las siguientes:

  • Optimización continua versus optimización discreta: Algunos modelos sólo tienen sentido si las variables toman valores de un conjunto discreto, a menudo un subconjunto de enteros, mientras que otros modelos contienen variables que pueden asumir cualquier valor real o continuo. Los modelos con variables discretas son problemas de optimización discretos; mientras que los modelos con variables continuas son problemas de optimización continua. Los problemas de optimización continua tienden a ser más fáciles de resolver que los problemas de optimización discreta; sin embargo, las mejoras en los algoritmos junto con los avances en la tecnología informática han aumentado dramáticamente el tamaño y la complejidad de los problemas de optimización discreta que se pueden resolver eficientemente.
  • Ninguna, una o varias funciones objetivo: La mayoría de los problemas de optimización tienen una única función objetivo, sin embargo, hay casos interesantes en los cuales los problemas de optimización no tienen una función objetivo o tienen múltiples de ellas. Los problemas de factibilidad, son problemas en los que el objetivo es encontrar valores para las variables que satisfacen las limitaciones de un modelo sin un objetivo particular de optimización. Los problemas de complementariedad surgen a menudo en ingeniería y economía; el objetivo es encontrar una solución que satisfaga las condiciones de complementariedad. Los problemas de optimización multiobjetivo surgen en muchos campos, como la ingeniería, la economía y la logística, cuando es necesario tomar decisiones óptimas en presencia de compromisos entre dos o más objetivos conflictivos. En la práctica, los problemas con objetivos múltiples a menudo se reformulan como problemas con objetivos únicos, ya sea formando una combinación ponderada de los diferentes objetivos o sustituyendo algunos de los objetivos por restricciones.
  • Optimización determinista versus optimización estocástica: En la optimización determinista, se supone que los datos para el problema dado se conocen con exactitud. Sin embargo, para muchos problemas reales, los datos no pueden ser conocidos con precisión por una variedad de razones. La primera razón se debe a un simple error de medición. La segunda razón más fundamental es que algunos datos representan información sobre el futuro (por ejemplo, la demanda o el precio del producto para un período de tiempo futuro) y simplemente no se puede saber con certeza. En la optimización bajo incertidumbre, o optimización estocástica, la incertidumbre se incorpora en el modelo. El objetivo es encontrar una solución que sea factible para todos los datos y óptima en algún sentido. Los modelos de programación estocástica aprovechan el hecho de que las distribuciones de probabilidad que gobiernan los datos son conocidas o pueden ser estimadas; el objetivo es encontrar alguna solución que sea factible para todas (o casi todas) las posibles instancias de los datos y optimice el rendimiento esperado del modelo.

Programación lineal

Matemáticamente, un problema de optimización con restricciones asume la siguiente forma:

$$ \begin{array}{ll} \min \hspace{1cm} f_0(x)\\ \mbox{sujeto a } \ f_i (x) \leq b_i, \hspace{1cm} i=1, \dots, m. \end{array} $$

En donde el vector $x = (x_1, \dots, x_n)$ es la variable de optimización del problema, la función $f_0: \mathbb{R}^n \rightarrow \mathbb{R}$ es la función objetivo, las funciones $f_i: \mathbb{R}^n \rightarrow \mathbb{R}, i=1, \dots, m$; son las funciones de restricciones de desigualdad; y las constantes $b_1, \dots, m$ son los límites de las restricciones. Dentro de este marco, un caso importante es el de la programación lineal, en el cual la función objetivo y las restricciones son lineales. El objetivo de la programación lineal es determinar los valores de las variables de decisión que maximizan o minimizan una función objetivo lineal, y en donde las variables de decisión están sujetas a restricciones lineales. En general, el objetivo es encontrar un punto que minimice la función objetivo al mismo tiempo que satisface las restricciones.

Para resolver un problema de programación lineal, debemos seguir los siguientes pasos:

  1. Elegir las incógnitas o variables de decisión.

  2. Escribir la función objetivo en función de los datos del problema.

  3. Escribir las restricciones en forma de sistema de inecuaciones.

  4. Averiguar el conjunto de soluciones factibles representando gráficamente las restricciones.

  5. Calcular las coordenadas de los vértices del recinto de soluciones factibles (si son pocos).

  6. Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de ellos presenta el valor máximo o mínimo según nos pida el problema (hay que tener en cuenta aquí la posible no existencia de solución).

Uno de los algoritmos más eficientes para resolver problemas de programación lineal, es el método simplex.

Optimización convexa

Otro caso importante de optimización que debemos destacar es el de la optimización convexa, en el cual la función objetivo y las restricciones son convexas. En realidad, la programación lineal que vimos anteriormente, no es más que un caso especial de optimización convexa.

¿qué es una función convexa?

Podemos decir que un un conjunto es convexo si se puede ir de cualquier punto a cualquier otro en línea recta, sin salir del mismo. El concepto de convexidad es el opuesto de concavidad. LLevado a las funciones, podemos decir que una función es convexa en un intervalo (a,c), si para todo punto b del intervalo la recta tangente en ese punto queda por debajo de la función.

Convexo vs no Convexo

Los conjuntos y funciones convexas tienen algunas propiedades que los hacen especiales para problemas de optimización, como ser:

  • Una función convexa no tiene mínimos locales que no sean globales.

  • Un conjunto convexo tiene un interior relativo no vacío.

  • Un conjunto convexo está conectado y tiene direcciones factibles en cualquier punto.

  • Una función no convexa puede ser convexificada manteniendo al mismo tiempo lo óptima de sus mínimos globales.

  • Una función convexa es continua dentro del interior de su dominio, y tiene buenas propiedades de diferenciación.

  • entre otras

Librerías de Python para problemas de optimización

Como es de esperar, en el ecosistema científico de Python podemos encontrar varias librerías que nos van a ayudar a enfrentar los problemas de optimización, entre las que podemos destacar:

  • Pyomo: Esta librería también nos va a proporcionar un lenguaje para modelar problemas de optimización en Python. Tiene una notación similar a la que utilizaríamos en la definición matemática de los problemas.

Debemos destacar que tanto PuLP como Pyomo requieren la instalación adicional de diferentes solvers para poder resolver los problemas de optimización. Algunos de los solvers que soportan son: GLPK, COIN CLP/CBC, CPLEX y GURUBI, entre otros.

Ejemplos con Python

Bien, ahora llegó el momento de ver como podemos resolver algunos problemas de optimización con la ayuda de las librerías antes mencionadas.

Mínimos cuadrados no lineales

En general, podemos resolver problemas de Mínimos cuadrados utilizando un poco de álgebra lineal, pero los Mínimos cuadrados también pueden ser vistos como un problema de optimización; ya que como su nombre lo indica, debemos minimizar la suma de los cuadrados de las diferencias entre los puntos generados por la función elegida y los correspondientes valores en los datos. scipy.optimize nos ofrece algunos métodos para resolver este tipo de problemas utilizando técnicas de optimización, como por ejemplo el algoritmo Gauss-Newton. Estos métodos pueden sernos de mucha utilizar sobre todo si la función tiene componentes no lineales. Veamos un ejemplo

In [1]:
Ver Código
In [2]:
# Ejemplo mínimos cuadrados no lineales utilizando scipy.optimize
beta = (0.25, 0.75, 0.5)

# funcion modelo
def f(x, b0, b1, b2):
    return b0 + b1 * np.exp(-b2 * x**2)

# datos aleatorios para simular las observaciones
xdata = np.linspace(0, 5, 50)
y = f(xdata, *beta)
ydata = y + 0.05 * np.random.randn(len(xdata))

# función residual
def g(beta):
    return ydata - f(xdata, *beta)

# comenzamos la optimización
beta_start = (1, 1, 1)
beta_opt, beta_cov = optimize.leastsq(g, beta_start)
beta_opt
Out[2]:
array([ 0.24022514,  0.76030423,  0.48425909])
In [3]:
# graficamos
fig, ax = plt.subplots(figsize=(10,8))
ax.scatter(xdata, ydata)
ax.plot(xdata, y, 'r', lw=2)
ax.plot(xdata, f(xdata, *beta_opt), 'b', lw=2)
ax.set_xlim(0, 5)
ax.set_xlabel(r"$x$", fontsize=18)
ax.set_ylabel(r"$f(x, \beta)$", fontsize=18)
ax.set_title('Mínimos cuadrados no lineales')
plt.show()

Optimización con restricciones

Las restricciones añaden otro nivel de complejidad a los problemas de optimización. En su forma más simple, simplemente consiste en poner algunos límites sobre los valores que las variables pueden alcanzar. Por ejemplo, podrías intentar resolver el siguiente problema:

$$\min \ f(x)= (x_1 -1)^2 - (x_2 -1)^2 \hspace{1cm} \mbox{sujeto a } \ 2 \leq x_1 \leq 3 \mbox{ y } 0 \leq x_2 \leq 2 $$

Este tipo de problema se puede resolver utilizando el método L-BFGS-B que nos ofrece scipy.optimize.

In [4]:
# Ejemplo de optimización con restricciones scipy

# defino una funcion de ayuda para subregion en el gráfico
def func_X_Y_to_XY(f, X, Y):
    """
    Wrapper for f(X, Y) -> f([X, Y])
    """
    s = np.shape(X)
    return f(np.vstack([X.ravel(), Y.ravel()])).reshape(*s)

# función a minimizar
def f(X):
    x, y = X
    return (x - 1)**2 + (y - 1)**2

# minimizo la función si restricciones
x_opt = optimize.minimize(f, (1, 1), method='BFGS').x

# el mínimo para las restricciones
bnd_x1, bnd_x2 = (2, 3), (0, 2)
x_cons_opt = optimize.minimize(f, np.array([1, 1]), method='L-BFGS-B',
bounds=[bnd_x1, bnd_x2]).x

# graficando la solución
fig, ax = plt.subplots(figsize=(10, 8))
x_ = y_ = np.linspace(-1, 3, 100)
X, Y = np.meshgrid(x_, y_)
c = ax.contour(X, Y, func_X_Y_to_XY(f, X, Y), 50)
ax.plot(x_opt[0], x_opt[1], 'b*', markersize=15)
ax.plot(x_cons_opt[0], x_cons_opt[1], 'r*', markersize=15)
bound_rect = plt.Rectangle((bnd_x1[0], bnd_x2[0]),
bnd_x1[1] - bnd_x1[0], bnd_x2[1] - bnd_x2[0],
facecolor="grey")
ax.add_patch(bound_rect)
ax.set_xlabel(r"$x_1$", fontsize=18)
ax.set_ylabel(r"$x_2$", fontsize=18)
plt.colorbar(c, ax=ax)
ax.set_title('Optimización con restricciones')
plt.show()

Las restricciones que se definen por igualdades o desigualdades que incluyen más de una variable son más complicadas de tratar. Sin embargo, existen técnicas generales que también podemos utilizar para este tipo de problemas. Volviendo al ejemplo anterior, cambiemos la restricción por una más compleja, como ser: $g(x) = x_1 - 1.75 - ( x_0 - 0.75 )^4 \geq 0$. Para resolver este problema scipy.optimize nos ofrece un método llamado programación secuencial por mínimos cuadrados, o SLSQP por su abreviatura en inglés.

In [5]:
# Ejemplo scipy SLSQP
# funcion de restriccion
def g(X):
    return X[1] - 1.75 - (X[0] - 0.75)**4

# definimos el diccionario con la restricción
restriccion = dict(type='ineq', fun=g)

# resolvemos
x_opt = optimize.minimize(f, (0, 0), method='BFGS').x
x_cons_opt = optimize.minimize(f, (0, 0), method='SLSQP',
                               constraints=restriccion).x

# graficamos
ig, ax = plt.subplots(figsize=(10, 8))
x_ = y_ = np.linspace(-1, 3, 100)
X, Y = np.meshgrid(x_, y_)
c = ax.contour(X, Y, func_X_Y_to_XY(f, X, Y), 50)
ax.plot(x_opt[0], x_opt[1], 'b*', markersize=15)
ax.plot(x_, 1.75 + (x_-0.75)**4, 'k-', markersize=15)
ax.fill_between(x_, 1.75 + (x_-0.75)**4, 3, color='grey')
ax.plot(x_cons_opt[0], x_cons_opt[1], 'r*', markersize=15)
ax.set_ylim(-1, 3)
ax.set_xlabel(r"$x_0$", fontsize=18)
ax.set_ylabel(r"$x_1$", fontsize=18)
plt.colorbar(c, ax=ax)
plt.show()