Consideremos una función no lineal f(x)dónde X es una variable continua. Nos gustaría encontrar el valor mínimo de esta función. f(x) cambiando nuestra variable de decisión X. El problema de optimización se puede formular matemáticamente de la siguiente manera:
En la mayoría de los casos, el usuario se encuentra con algunas limitaciones que deben tenerse en cuenta. Podría ser, por ejemplo, una temperatura mínima requerida en una habitación, una restricción sobre cuánta presión se ejerce sobre un material o la cantidad mínima de tiempo que desea o necesita esperar hasta tomar su próximo café.
Estas limitaciones se presentan en forma de igualdades o desigualdades. En aras de la simplicidad, asumiremos que sólo tenemos restricciones de desigualdad, descritas por g(x)≤0. Por lo tanto, podemos agregar esta restricción al problema de optimización de la siguiente manera:
Si las funciones (f(x) y g(x), o sólo uno de ellos) son no lineales, necesitaríamos utilizar solucionadores no lineales. Intentamos evitar esto, que es donde entra en juego un paso de linealización. Entonces, hagamos una pausa en nuestra discusión sobre optimización y veamos primero una técnica que nos permite aproximar una función no lineal.
Para visualizar y comprender mejor esta parte, considere una función logarítmica f(x)=log(x) en el rango de x=[1,6]:
# Get some packages
import numpy as np
import matplotlib.pyplot as plt# Create nonlinear function
def f(x):
return np.log(x)
# Define lower and upper values and an x-range
xlb = 1
xub = 6
numx = 100
x = np.linspace(xlb, xub, numx)
y = f(x)
# Plot the function
plt.figure()
plt.plot(x, y, color='blue', linestyle='--', label='Nonlinear f(x)')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.legend(frameon=False, loc='lower right')
plt.show()
Con este fragmento de código, podemos producir el siguiente diagrama:
Ahora comenzamos con la definición de una función lineal, que tiene la siguiente forma general (con pendiente a y una intersección b):
Las funciones están aquí para describir algo. Eso podría ser, por ejemplo, un comportamiento o sistema físico. Este sistema probablemente pueda ser muestreado, por lo que podemos elegir nuestro X y podemos observar lo que nuestro f(x) es (independiente del hecho de si el sistema es lineal o no lineal). Ejemplo. Si cocemos Spaghetti en una olla con agua, podríamos esperar 1 minuto (x1) y observa que bien se cocinan nuestros Spaghetti (f(x1)). Podemos esperar otros 5 minutos (x2) y comprobar de nuevo qué tan bien están hechos los espaguetis (f(x2)). Supongo que sabes a qué me refiero. 😄 🍝
Si tenemos un entorno del que obtenemos algunos puntos de muestra, podemos usarlos para calcular la pendiente correspondiente. a y la intersección b de la recta que une esos dos puntos. Digamos que tenemos 2 puntos, f(x1) y f(x2). Esto significa que, dado que el modelo lineal debe cumplirse en ambos puntos, sabemos que estas dos ecuaciones también se cumplen en ambos puntos:
Tenemos dos incógnitas (a y b) y dos ecuaciones, por lo que podemos resolver para a y b:
Usando estas expresiones, podemos intentar aproximar nuestra función considerada. f(x)=log(x) en el rango de x=[1,6].
Hagámoslo en Python. Primero, tomamos los límites inferior y superior como nuestros dos puntos para definir el segmento (recuerde, Python comienza a indexar en cero, así que no se confunda si dice “segmento 0”, que es solo nuestro primer segmento considerado):
num_segments = 1
x_segments = np.linspace(xlb, xub, num_segments+1)
for i in range(num_segments):
print(f'[+] Segment {i} goes from x={x_segments[i]:.2f} to x={x_segments[i+1]:.2f}.')
[+] Segment 0 goes from x=1.00 to x=6.00.
Luego, escribimos una función que devuelve la pendiente y la intersección dados dos puntos de apoyo (a veces también llamados “nodos”), a saber x=[x1,x2] y y=[f(x1),f(x2)]:
def calc_slope_and_intersection(x, y):
slope = (y[1:] - y[:-1])/(x[1:] - x[:-1])
intersection = y[:-1] - slope*x[:-1]
return float(slope), float(intersection)
Luego calculamos las pendientes y las intersecciones y almacenamos los valores en listas:
slope, intersection = [], []
for i in range(num_segments):
x_segment = x_segments[i:i+2] # Get the x values for the segment
y_segment = f(x_segment) # Sample from nonlinear environment
slope_, intersection_ = calc_slope_and_intersection(x_segment, y_segment)
slope.append(slope_)
intersection.append(intersection_)
print(f'[+] Linear function of segment {i}: x*{slope[i]:.2f}+({intersection[i]:.2f}).')
[+] Linear function of segment 0: x*0.36+(-0.36).
La pendiente se calcula como a=0,36donde la intersección tiene el mismo valor de b=0,36. Esto nos lleva a la siguiente ecuación lineal como aproximación:
Podemos trazar esto junto con la función logarítmica original:
# Function that creates a linear function from slope and intersection
def get_linear(slope, intersection, xlb, xub):
x_ = np.array([xlb, xub])
return slope*x_ + intersection# Plot the linear functions
plt.figure()
plt.plot(x, y, color='blue', linestyle='--', label='Nonlinear f(x)') # Nonlinear function
for i in range(num_segments):
x_segment = x_segments[i:i+2]
y_segment = get_linear(slope[i], intersection[i], x_segment[0], x_segment[1])
plt.plot(x_segment, y_segment, color='orange', linestyle='-', label='Linear segment' if i==0 else '__nolabel__') # Linear segments
plt.plot(x_segment, y_segment, color='black', linestyle='', marker='x', label='Nodes' if i==0 else '__nolabel__') # Nodes
plt.xlabel('x')
plt.ylabel('f(x)')
plt.legend(frameon=False, loc='lower right')
plt.show()
Bien. Eso no es muy exacto. Pero es lineal y pasa por los dos nodos que utilizamos. En esencia, hace lo que queremos. Ahora podemos muestrear la función un poco más a menudo (usar más de estos nodos), lo que nos lleva a la técnica de linealización por partes.
Dividamos todo X-rango en norte segmentos (yo=1,2,…,norte), y realice la linealización de la función que se muestra arriba f(x) en cada segmento. En las ecuaciones siguientes, la notación norte describe el conjunto de estos segmentos, es decir norte={1,2,…,n}. Para cada función lineal, necesitamos su pendiente e intersección individuales:
Dado que podemos definir un número de valores deseados para X y luego muestrear los valores correspondientes para f(x) a partir de nuestra función (desconocida), podemos calcular nuevamente las pendientes y las intersecciones. Por tanto, definamos algo más X-valores para los diferentes segmentos (los nodos). Digamos que usamos norte=3.
Se pueden usar los mismos fragmentos de código anteriores, simplemente ajuste la variable num_segments a 3. Los rangos x de los segmentos y sus ecuaciones se dan de la siguiente manera:
[+] Segment 0 goes from x=1.00 to x=2.67.
[+] Segment 1 goes from x=2.67 to x=4.33.
[+] Segment 2 goes from x=4.33 to x=6.00.[+] Linear function of segment 0: x*0.59+(-0.59).
[+] Linear function of segment 1: x*0.29+(0.20).
[+] Linear function of segment 2: x*0.20+(0.62).
Se ve un poco mejor. Podríamos aumentar aún más el número de segmentos, pero vivir al límite no siempre es lo que queremos, así que sigamos con norte=3 Siendo por el momento. 😎
Con esto, identificamos una posible aproximación de la función no lineal. f(x). Regresemos y reemplacemos esta no linealidad en nuestro problema de optimización original.
Nuevamente, el objetivo es encontrar el mínimo de la función. f(x)considerando que tiene que estar por encima de una especificación determinada k. Podemos formular esto como se muestra arriba, donde nuestra restricción de desigualdad g(x)≤0 es basicamente Kf(x)≤0:
Dado que hemos linealizado nuestra función en segmentos, se deben considerar todos los segmentos del problema de optimización. Esto es posible creando otra variable. z para cada segmento. Esta variable debe ser binaria (0 o 1). Es 0 si el segmento está inactivo y 1 si el segmento está activo (lo que significa que nuestra solución mínima que buscamos se encuentra en este segmento).
Ahora podemos sumar todas las funciones lineales de los segmentos y multiplicarlas por el correspondiente z variable.
También consideramos que nuestra solución óptima sólo puede estar en un segmento a la vez. En otras palabras, sólo un segmento puede estar activo, es decir, la suma de todos z las variables tienen que ser 1:
O en una forma ligeramente diferente:
Bueno, parece que no hicimos un muy buen trabajo. Esta formulación del problema ahora es no lineal (debido a la multiplicación de X con z en la función objetivo y la restricción) e incluso tiene variables enteras (z).
Sin embargo, existe un truco sencillo que nos permite reescribir dicho “término pseudobilineal” (que es una no linealidad). Primero, definimos una variable auxiliar. x-tildeque es la multiplicación de la variable continua (X) con la variable binaria (z):
A continuación, debemos definir el dominio en el que x-tilde puede ser válido para los casos en que z=0 (segmento inactivo) y z=1 (segmento activo). Si el segmento está inactivo, nuestra variable auxiliar debe ser cero. Esto lo logramos mediante las siguientes desigualdades:
Dónde xmin y xmax son los “nodos” inferior y superior que calculamos anteriormente. Puedes verificar fácilmente que si z es cero, x-tilde también se ve obligado a ser cero.
Además, si z=1la variable auxiliar x-tilde debe estar delimitado por la variable continua “verdadera” X:
Vale la pena mencionar aquí que xub es el límite superior de la variable continua X (no los de los nodos intermedios). Con esto, podemos reescribir nuestro problema de optimización desde arriba:
Quizás quieras repetirlo con una taza de café ☕