Home

Federica EU

1/10

Antonio Sforza » 3.Ottimizzazione non lineare multidimensionale non vincolata

Schema della lezione

In questa lezione si presentano i problemi di ottimizzazione caratterizzati dalla presenza di almeno due variabili decisionali, in assenza di relazioni vincolari che definiscano un dominio di ammissibilità delle soluzioni.

Per introdurre l’argomento si presenta un problema di ottimizzazione multidimensionale non vincolata.

Si definiscono quindi le condizioni di ottimalità nei casi di funzioni differenziabili e convesse.

Si introducono i metodi di soluzione a “scalata diretta” della funzione (direct climbing) basati sulla generazione di una successione di punti cui corrispondono valori sempre migliori della funzione obiettivo.

Si presenta infine un esempio numerico dell’algoritmo di discesa ripida.

Un esempio di ottimizzazione multidimensionale non vincolata

Un’azienda produce due beni, A e B, il cui profitto unitario è variabile con la produzione. Se con x_A ed x_B si indicano le quantità prodotte dei beni A e B, il profitto unitario è espresso dalle seguenti funzioni lineari:

p_A = p_A (x_A) = 126 – 9x_A

p_B = p_B (x_B) = 182 – 13x_B

Il profitto globale è espresso dunque dalla seguente funzione quadratica:

z = p_A(x_A) · x_A + p_B(x_B) · x_B = (126 – 9x_A) x_A + (182 – 13x_B) x_B

z = 126 x_A – 9 x_A² + 182 x_B – 13 x_B²

Il massimo di questa funzione si determina nel punto: x_A= 7, x_B= 7, corrispondente alla produzione di A e B che rende massimo il profitto, con z = 1078. Nelle figure sono riportate le rappresentazioni tri e bidimensionali della funzione, attraverso le curve di livello della stessa sul piano v-g. La curva di livello più esterna corrisponde al valore z = 857.

Rappresentazione grafica della funzione obiettivo z (x_A, x_B )

Rappresentazione grafica della f.o. z = f ( x_A , x_B ) =126x_A – 9x_A² + 182x_B – 13x_B²

Punti di ottimo di una funzione multidimensionale e condizioni di ottimalità

Condizioni di ottimo per funzioni differenziabili

Condizione necessaria affinché il punto x* sia un punto di minimo (o di massimo) locale (globale) per la funzione differenziabile f (x) definita in un insieme aperto S è che x* sia un punto di stazionarietà della funzione obiettivo, cioè che sia:

∇f (x* ) = 0

Punti di ottimo di una funzione multidimensionale e condizioni di ottimalità

Metodi di scalata diretta

Punto iniziale x₀

x_k+1=x_k+θ_k dk

d_k (vettore ad n componenti) direzione di spostamento
θ_k(scalare non negativo) lunghezza dello spostamento
{x_k}≡{x₀ , x₁, x₂ …} successione di punti

f (x_k+1) < f (x_k ) (Min) miglioramento

f (x_k+1) > f (x_k) (Max)

Algoritmo di discesa ripida. Funzione z = f (x₁, x₂) – Curve di livello e Direzioni di discesa (salita) ripida

Algoritmo di discesa ripida. Esempio numerico

$Min\; f(x)=f(x_f,x_2) = (_{xf}-3x_2)^2+(x_2-1)^2=x_t^2+10x_2^2-6x_fx_2-2x_2+1$

$x_0=(2,2),f(x_0)=17,$ precisione $\epsilon = 0.001$ per la convergenza dell’algoritmo.

Vettore gradiente e suo valore nel punto iniziale x₀ sono espressi da:

$\nabla f(x)=\left[\begin{array}{ll}2x_f-6x_2 \\ -6x_1+20x_2-2\end{array}\right]\hspace{1,5cm}\nabla f(x_0)=\left[\begin{array}{ll}-8\\26\end{array}\right]$

Condizione di ottimalità non soddisfatta in x₀:

$x_1=x_0-\theta_0\nabla f(x_0)=\left[\begin{array}{ll}2\\2\end{array}\right]-\theta_0\left[\begin{array}{ll}-8\\26\end{array}\right]= \left[\begin{array}{ll}2+8\theta_0\\2-26\theta_0\end{array}\right]\hspace{2cm}x_1=f(\theta_0)$

$f(x_1)=f(x_0-\theta_0\nabla f(x_0))=f(2+8\theta_0,2-26\theta_0)\hspace{1,5cm}f(x)=x_1^2+10x_2^2-6x_1x_2-2x_2+1$

Sostituendo nella formula di espressione f(x) le coordinate x₁ e x₂ del punto x1 sono in funzione di θ₀ si ottiene:

$g(\theta_0)=17-74\theta_0+8072\theta_0^2$

Il punto x1 corrisponde al punto x1 in funzione di θ₀, valore di θ₀ che costituisce un punto di minimo per g(θ₀).

$\theta_0^*=0.0458$

$x_1=\left[\begin{array}{ll}2.3667\\0.8082\end{array}\right]\hspace{1,5cm}f(x_1)=0.0402\hspace{1,5cm}\text{Il gradiente e' }\nabla f(x_1)=\left[\begin{array}{ll}-0.1160\\-0.0357\end{array}\right]$

Algoritmo di discesa ripida. Esempio numerico

$x_1=\left[\begin{array}{ll}2.3667\\0.8082\end{array}\right]\hspace{1,5cm}f(x_1)=0.0402\hspace{1,5cm}\text{Il gradiente e' }\nabla f(x_1)=\left[\begin{array}{ll}-0.1160\\-0.0357\end{array}\right]$

Poiché $|\nabla f(x_1)|>\varepsilon \Rightarrow x_1$ non é un punto di minimo locale.

$x_2=x_1-\theta_1\nabla f(x_1)=\left[\begin{array}{ll}2.3667+0.1160\theta_1\\0.8082+0.0357\theta_1\end{array}\right]$

$f(x_2=f(x_1)-\theta_1\nabla f(x_1))=f(2.3667+0.1160\theta_1,0.8082+0.0357\theta_1)$

$g(\theta_1)=0.0402-0.0147\theta_1+0.00135\theta_1^2$

La funzione $g(\theta_1)$ ha un punto di minimo in $\theta_1=5.4413$ e dunque:

$x_2=\left[\begin{array}{ll}2.9976\\1.0024\end{array}\right]\hspace{1,5cm}f(x_2)=0.000094\hspace{1,5cm}\text{Il gradiente in }x_2\text{ e' }\nabla f(x_2)=\left[\begin{array}{ll}-0.0188\\0.0612\end{array}\right]$