Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 xA ed xB si indicano le quantità prodotte dei beni A e B, il profitto unitario è espresso dalle seguenti funzioni lineari:

pA = pA (xA) = 126 – 9xA 

pB = pB (xB) = 182 – 13xB 

Il profitto globale è espresso dunque dalla seguente funzione quadratica:

z = pA(xA) · xA + pB(xB) · xB = (126 – 9xA) xA + (182 – 13xB) xB

z = 126 xA – 9 xA2 + 182 xB – 13 xB2

Il massimo di questa funzione si determina nel punto: xA= 7, xB= 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 (xA, xB )


Rappresentazione grafica della f.o. z = f ( xA , xB ) =126xA – 9xA2 + 182xB – 13xB2


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 x0

xk+1=xkk dk

dk (vettore ad n componenti) direzione di spostamento
θk(scalare non negativo) lunghezza dello spostamento
{xk}≡{x0 , x1, x2 …} successione di punti

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

f (xk+1) > f (xk) (Max)

Algoritmo di discesa ripida. Funzione z = f (x1, x2) – 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 x0 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 x0:

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 x1 e x2 del punto x1 sono in funzione di θ0 si ottiene:

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

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

\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]

|\nabla f(x_2)|>\varepsilon il punto x2 non è un punto di minimo locale.

x_3=x_2-\theta_2\nabla f(x_2)\hspace{1,5cm}x_3=\left[\begin{array}{ll}2.9985\\0.9995\end{array}\right]\hspace{1,5cm}f(x_3)=2.2\cdot 10^{-7}

\nabla f(x_3)=\left[\begin{array}{ll}-0.0003\\-0.0001\end{array}\right]

Il punto x3 è un punto di minimo locale. Infatti |\nabla f(x_3)|<\varepsilon ed inoltre |x_3-x_2|<\varepsilon.

 

Algoritmo di discesa ripida: z = x12+10x22 – 6x1x2  – 2x2+1


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion