Problemi di ottimizzazione

Introduzione

I problemi di ottimizzazione consistono nella ricerca di punti stazionari. Questo genere di analisi è spesso utilizzata nelle discipline scientifiche e ingegneristiche per ottenere i parametri utili per raggiungere il massimo rendimento, o il minimo rapporto tra parametri come dimensioni, peso, prestazioni. In questo caso generale di ricerca di massimi, minimi o punti di sella in un intero insieme numerico, parliamo di ottimizzazione libera.

Inoltre il sistema da analizzare può essere soggetto a vincoli geometrici, fisici o semplicemente matematici, per cui parleremo anche di ottimizzazione vincolata.

Esempi di problemi

• Un problema geometrico di ottimizzazione libera potrebbe consistere per esempio nella ricerca dei punti di massimo della superficie $z=-x^2-y^2$. Il problema trova unica soluzione nel vertice del paraboloide capovolto che la data superficie rappresenta.
• Un primo problema di ottimizzazione vincolata potrebbe essere semplicemente di tipo geometrico: minimizzare la superficie di un generico parallelepipedo di dimensioni a, b, c con volume dato. In questo caso il vincolo è il volume ($a\cdot b\cdot c=Vol$), le incognite sono i rapporti tra le lunghezze dei lati ed infine il punto stazionario da analizzare è il minimo della superficie ($Sup=2\cdot (ab+bc+ac)$). Questo problema lo risolveremo in seguito, ma anticipiamo che la soluzione geometrica è il cubo, ovvero il caso in cui i lati sono uguali tra loro.

Ottimizzazione libera

Come anticipato, si procede con l'ottimizzazione libera per trovare tutti punti critici (massimi, minimi e selle) nel dominio della funzione.

Ricerca dei punti stazionari

I punti stazionari sono massimi e minimi (locali e assoluti), e i punti di sella. I punti di massimo, oltre che avere - come tutti i punti stazionari - un piano tangente orizzontale, hanno la particolarità di avere nel loro intorno solo punti ad una quota inferiore. Viceversa per i punti di minimo. Le selle invece sono punti - sempre con piano tangente orizzontale - che nel loro intorno hanno punti a quota più bassa ed altri punti a quota più alta.

Il primo passo da eseguire (se la funzione è $C^1$, cioè ovunque liscia) consiste nella ricerca della proprietà fondamentale di tutti i punti stazionari: l'orizzontalità del piano tangente. Questa proprietà si può verificare grazie alle caratteristiche del gradiente della funzione, che in tali punti è nullo. Infatti il gradiente indica in ogni punto la direzione e di quanto cresce la superficie in quel punto: se in quel punto esso è nullo allora la pendenza è nulla, il piano dunque è orizzontale.

Se tuttavia la funzione non fosse $C^1$ e magari nemmeno differenziabile - cioè liscia - in tutto il dominio, allora è possibile che siano presenti dei punti critici in punti non differenziabili come spigoli e punte. Questi punti critici non vengono rilevati con la ricerca dei punti stazionari e vanno evidenziati separatamente.

Ricerca del tipo di punto stazionario: massimo, minimo o sella

Il secondo passo invece consiste nel discriminare i punti stazionari trovati tra: massimi, minimi e selle. Per fare ciò si può utilizzare il metodo della matrice Hessiana.

Procedimento di costruzione ed interpretazione della matrice Hessiana in due variabili

Una volta trovati i punti stazionari, si costruisce la matrice Hessiana in questo modo: $H=\left[\begin{array}{cc}{f}_{xx}& f_{xy}\\ f_{xy}& f_{yy}\end{array}\right]$ e, per ogni punto stazionario, si sostituiscono i valori di x e y.

Quindi, per capire se il punto in questione è massimo, minimo o sella, utilizziamo semplicemente il determinante della matrice Hessiana, detto Hessiano, ed il segno di $f_{xx}$ :

• Il punto $P_0$ è un massimo se l'Hessiano è positivo e $f_{xx}$ è negativo
• Il punto $P_0$ è un minimo se l'Hessiano è positivo e $f_{xx}$ è positivo.
• Il punto $P_0$ è una sella se l'Hessiano è negativo.
• Se invece l'Hessiano è nullo, allora non abbiamo informazioni sufficienti.

Template:Cassetto

Ottimizzazione vincolata

L'ottimizzazione vincolata consiste nella ricerca dei punti stazionari e dell'analisi della loro tipologia, ma in un dominio soggetto ad un vincolo: una relazione necessaria tra le variabili. Di conseguenza si ricercano i punti in un dominio di dimensione inferiore a quello di partenza. Ad esempio una linea è un dominio di dimensione inferiore per uno spazio tridimensionale.

Un possibile problema potrebbe essere la ricerca di punti stazionari e loro tipologia, di una funzione scalare in x-y-z lungo una certa linea, ad esempio una circonferenza sul piano x-y.

Vincolo esplicitabile

Se il vincolo è esplicitabile, la procedura è più semplice.

Il vincolo si dice esplicitabile se (nel caso a due variabili) la variabile x è esprimibile esplicitamente in funzione di y, dunque nella forma x=g(y); o viceversa se y=g(x).

Ad esempio:

$\gamma :y(x)=x$ è già esplicita

$\gamma :2y+3x=0$ è esplicitabile ad esempio come $y=g(x)=-\frac{3}{2}x$

$\gamma :x^2+y^2=1$, una circonferenza, non è esplicitabile (a meno che, ad esempio, non si spezzi la funzione in $x(y)=\pm \sqrt{1-y^2}$ ).

Nel caso dunque procediamo con la sostituzione del vincolo nell'equazione della funzione, ottenendo così una funzione f(x, g(x) ) (o viceversa f( g(y), y) ) che è funzione di una sola variabile (x o, viceversa, y).

A questo punto la ricerca di massimi, minimi e selle (tutte entità bi-dimensionali) si trasforma nella ricerca di massimi, minimi e flessi mono-dimensionali, semplicemente analizzando la funzione di una variabile.

Vincolo non esplicitabile

Se il vincolo non è esplicitabile (e non si intende spezzare la funzione), si può utilizzare il metodo dei moltiplicatori lagrangiani.

Procedimento dei moltiplicatori lagrangiani

Il vincolo, si è detto, in questo caso non è esplicitabile, ma possiamo scriverlo quindi nella forma:

$h=h(x,y)$

portando tutti gli elementi da un solo lato dell'equazione.

Dato un valore $\lambda \in ℝ$ defininiamo la funzione L(x,y,λ):

$L(x,y,\lambda ):=f(x)-\lambda \cdot h(x)$

Per trovare i punti stazionari risolviamo il sistema:

$\mathrm{\nabla }L=\underset{\_}{0}$

ovvero

$\{\begin{array}{c}{L}_x=0\\ L_y=0\\ L_{\lambda }=0\end{array}$

Una volta trovati i punti stazionari $P_1,P_2,$ etc. per distinguere le tipologie calcoliamo le derivate seconde per utilizzare il già studiato metodo della matrice Hessiana, limitandoci alle righe e colonne delle variabili x e y.

$H(L){|}_{P_1=(x_1,y_1,{\lambda }_1)}=\left[\begin{array}{cc}{L}_{xx}(x_1,y_1,{\lambda }_1)& L_{xy}(x_1,y_1,{\lambda }_1)\\ \\ L_{xy}(x_1,y_1,{\lambda }_1)& L_{yy}(x_1,y_1,{\lambda }_1)\end{array}\right]$

Infine interpretiamo la matrice Hessiana come già visto sopra.