Consideriamo una funzione non lineare f(x)Dove X è una variabile continua. Vorremmo trovare il valore minimo di questa funzione f(x) modificando la nostra variabile decisionale X. Il problema di ottimizzazione può essere formulato matematicamente nel modo seguente:
Nella maggior parte dei casi, l’utente incontra alcuni vincoli che devono essere considerati. Potrebbe trattarsi, ad esempio, della temperatura minima richiesta in una stanza, di un vincolo sulla pressione esercitata su un materiale o del tempo minimo che desideri/devi attendere prima di bere il tuo prossimo caffè.
Questi vincoli si presentano sotto forma di uguaglianze o disuguaglianze. Per semplicità, assumeremo di avere solo vincoli di disuguaglianza, descritti da g(x)≤0. Possiamo quindi aggiungere questo vincolo al problema di ottimizzazione come segue:
Se le funzioni (f(x) E g(x), o solo uno di essi) sono non lineari, dovremmo utilizzare solutori non lineari. Cerchiamo di evitarlo, ed è qui che entra in gioco una fase di linearizzazione. Quindi fermiamo la discussione sull’ottimizzazione e guardiamo prima una tecnica che ci consente di approssimare una funzione non lineare.
Per visualizzare e comprendere meglio questa parte, considera una funzione logaritmica f(x)=log(x) nella gamma di 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 questo pezzo di codice, possiamo produrre la seguente trama:
Iniziamo ora con la definizione di funzione lineare, che ha la seguente forma generale (con pendenza UN e un incrocio B):
Le funzioni sono qui per descrivere qualcosa. Potrebbe trattarsi ad esempio di un comportamento o di un sistema fisico. Questo sistema può probabilmente essere campionato, quindi possiamo scegliere il nostro X e poter osservare ciò che il nostro f(x) è (indipendentemente dal fatto che il sistema sia lineare o non lineare). Esempio. Se cuociamo gli spaghetti in una pentola d’acqua, potremmo aspettare 1 minuto (x1) e osservare come sono cotti i nostri Spaghetti (f(x1)). Possiamo aspettare altri 5 minuti (x2) e controlla nuovamente la cottura degli spaghetti (f(x2)). Immagino che tu sappia cosa intendo. 😄 🍝
Se abbiamo un ambiente da cui ricaviamo alcuni punti campione, possiamo usarli per calcolare la pendenza corrispondente UN e l’intersezione B della linea che collega questi due punti. Diciamo che abbiamo 2 punti, f(x1) E f(x2). Ciò significa che, poiché il modello lineare dovrebbe valere in entrambi i punti, sappiamo che anche queste due equazioni valgono in entrambi i punti:
Abbiamo due incognite (UN E B) e due equazioni, quindi possiamo risolvere UN E B:
Usando queste espressioni, possiamo provare ad approssimare la funzione considerata f(x)=log(x) nella gamma di x=(1,6).
Facciamolo in Python. Innanzitutto, prendiamo i limiti inferiore e superiore come i nostri due punti per definire il segmento (ricorda, Python inizia l’indicizzazione da zero, quindi non essere confuso se dice “segmento 0”, che è solo il nostro primo segmento considerato):
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.
Quindi, scriviamo una funzione che restituisce la pendenza e l’intersezione dati due punti di appoggio (a volte chiamati anche “nodi”), vale a dire x=(x1,x2) E 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)
Calcoliamo quindi le pendenze e gli incroci e memorizziamo i valori in liste:
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 pendenza è calcolata come a=0,36dove l’intersezione ha lo stesso valore di b=0,36. Questo ci porta, in approssimazione, alla seguente equazione lineare:
Possiamo tracciarlo insieme alla funzione logaritmica originale:
# 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()
BENE. Non è molto accurato. Ma è lineare e passa attraverso i due nodi che abbiamo usato. Quindi, in sostanza, fa quello che vogliamo. Ora possiamo campionare la funzione un po’ più spesso (utilizzando più di questi nodi), il che ci porta alla tecnica di linearizzazione a tratti.
Dividiamo il tutto X-intervallo in N segmenti (i=1,2,…,n) ed eseguire la linearizzazione della funzione sopra mostrata f(x) in ogni segmento. Nelle equazioni seguenti, la notazione N descrive l’insieme di questi segmenti, significato N={1,2,…,n}. Per ogni funzione lineare, abbiamo bisogno della sua pendenza e intersezione individuali:
Poiché possiamo definire un numero di valori desiderati per X e quindi campionare i valori corrispondenti per f(x) dalla nostra funzione (sconosciuta) possiamo calcolare nuovamente le pendenze e gli incroci. Cerchiamo quindi di definirne qualcuno in più X-valori per i diversi segmenti (i nodi). Diciamo che usiamo n=3.
È possibile utilizzare gli stessi frammenti di codice di cui sopra, basta regolare la variabile num_segments su 3. Gli intervalli x dei segmenti e le loro equazioni sono forniti come segue:
(+) 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).
Sembra un po’ meglio. Potremmo aumentare ulteriormente il numero dei segmenti, ma non sempre vivere ai limiti è ciò che desideriamo, quindi atteniamoci n=3 per ora. 😎
Con ciò abbiamo individuato una possibile approssimazione della funzione non lineare f(x). Torniamo indietro e sostituiamo questa non linearità nel nostro problema di ottimizzazione originale.
Anche in questo caso l’obiettivo è trovare il minimo della funzione f(x)considerando che deve essere superiore ad una determinata specifica K. Possiamo formularlo come mostrato sopra, dove il nostro vincolo di disuguaglianza g(x)≤0 è fondamentalmente Kf(x)≤0:
Poiché abbiamo linearizzato la nostra funzione in segmenti, è necessario considerare tutti i segmenti per il problema di ottimizzazione. Ciò è possibile creando un’altra variabile z per ciascun segmento. Questa variabile dovrebbe essere binaria (0 o 1). È 0 se il segmento è inattivo e 1 se il segmento è attivo (il che significa che la nostra soluzione minima che stiamo cercando si trova in questo segmento).
Possiamo ora sommare tutte le funzioni lineari dei segmenti e moltiplicarle per il corrispondente z variabile.
Consideriamo inoltre che la nostra soluzione ottimale può essere solo in un segmento alla volta. In altre parole può essere attivo un solo segmento, ovvero la somma di tutti z le variabili devono essere 1:
O in una forma leggermente diversa:
Beh, sembra che non abbiamo fatto un ottimo lavoro. La formulazione del problema è ora non lineare (a causa della moltiplicazione di X con z nella funzione obiettivo e nel vincolo) e ha anche variabili intere (z).
Tuttavia, esiste un semplice trucco che ci permette di riscrivere tale “termine pseudo bilineare” (che è una non linearità). Per prima cosa definiamo una variabile ausiliaria x-tildeche è la moltiplicazione della variabile continua (X) con la variabile binaria (z):
Successivamente, dobbiamo definire il dominio in cui x-tilde può essere valido per i casi in cui z=0 (segmento inattivo) e z=1 (segmento attivo). Se il segmento è inattivo, la nostra variabile ausiliaria deve essere zero. Otteniamo ciò mediante le seguenti disuguaglianze:
Dove xmin E xmax sono i “nodi” inferiori e superiori che abbiamo calcolato sopra. Puoi verificarlo facilmente se z è zero, x-tilde è costretto a essere anch’esso pari a zero.
Inoltre, se z=1la variabile ausiliaria x-tilde dovrebbe essere delimitato dalla variabile continua “vera”. X:
Vale la pena menzionarlo qui frecce è il limite superiore della variabile continua X (non quelli dei nodi intermedi). Con questo, possiamo riscrivere il nostro problema di ottimizzazione dall’alto:
Potresti voler ripercorrerlo con una tazza di caffè ☕
Fonte: towardsdatascience.com
