Problemi di ottimizzazione

Analisi matematica > Problemi di ottimizzazione

• Indice delle lezioni di:
  • Analisi matematica
• Torna al corso:
  • Matematica

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.

Forme quadratiche e teoria del metodo della matrice Hessiana

Una volta individuato almeno un punto stazionario, per verificare se esso sia massimo, minimo o sella utilizzo l'approssimazione del polinomio di Taylor (in due variabili) al secondo grado. Vediamo perché.

Consideriamo una funzione f, un punto $P_{0}=(x_{0},y_{0})$ ed il punto P=(x,y).

L'approssimazione di Taylor, al primo grado, della funzione f in $P_{0}$ è:

$T_{f,P_{0}}^{1}(P)=f(P_{0})\quad +\quad f_{x}|_{P_{0}}(x-x_{0})+f_{y}|_{P_{0}}(y-y_{0})$

Questa scrittura coincide con la scrittura del piano tangente nel punto P₀. Ma, dato che il punto $P_{0}$ è stazionario, il piano tangente è orizzontale (cioè del tipo z=k con k valore reale) ed il primo grado di approssimazione coincide semplicemente con il valore della funzione nel punto ( $f(P_{0})$ ).

Dunque per avere informazioni aggiuntive dall'approssimazione di Taylor è necessario calcolarne il secondo grado:

$T_{f,P_{0}}^{2}(P)=f(P_{0})\quad +\quad f_{x}|_{P_{0}}(x-x_{0})+f_{y}|_{P_{0}}(y-y_{0})\quad +\quad {\frac {1}{2}}\left(f_{xx}|_{P_{0}}(x-x_{0})^{2}+2f_{xy}|_{P_{0}}(x-x_{0})(y-y_{0})+f_{yy}|_{P_{0}}(y-y_{0})^{2}\right)$

Che, come detto, per l'orizzontalità del piano tangente, corrisponde semplicemente a:

$T_{f,P_{0}}^{2}(P)=f(P_{0})\quad +\quad {\frac {1}{2}}\left(f_{xx}|_{P_{0}}(x-x_{0})^{2}+2f_{xy}|_{P_{0}}(x-x_{0})(y-y_{0})+f_{yy}|_{P_{0}}(y-y_{0})^{2}\right)$

L'equazione la possiamo scrivere anche così:

$T_{f,P_{0}}^{2}(P)\quad -\quad f(P_{0})\quad =\quad {\frac {1}{2}}\left(f_{xx}|_{P_{0}}(x-x_{0})^{2}+2f_{xy}|_{P_{0}}(x-x_{0})(y-y_{0})+f_{yy}|_{P_{0}}(y-y_{0})^{2}\right)\qquad (1)$

Ora verifichiamo se $P_{0}$ è massimo. Quindi rivediamo la definizione di massimo locale:

P₀ si dice massimo locale se $f(P_{0})\geq \;f(P)\quad \forall P\in I_{\epsilon }(P_{0})$

con $I_{\epsilon }(P_{0})$ un generico intorno circolare, di raggio ε, di $P_{0}$

ma per comodità scriviamo la stessa diseguaglianza così:

$f(P)-f(P_{0})\leq \;0$

Essendo il polinomio di Taylor un'approssimazione di $P_{0}$, possiamo considerare $f(P)=T_{f,P_{0}}^{2}(P)$, e scrivere che $f(P_{0})$ è massimo locale se è verificata la disequazione sottostante:

$T_{f,P_{0}}^{2}(P)\ -\ f(P_{0})\leq \;0$

Quindi, data la (1), equivalentemente se:

${\frac {1}{2}}\left(f_{xx}|_{P_{0}}(x-x_{0})^{2}+2f_{xy}|_{P_{0}}(x-x_{0})(y-y_{0})+f_{yy}|_{P_{0}}(y-y_{0})^{2}\right)\leq \;0\qquad (2)$

Nota: il coefficiente ${\frac {1}{2}}$ si può elidere e non considerare più d'ora in avanti, dato che l'altro termine della disequazione è zero.

Per risolvere quest'ultima disequazione, che è una forma quadratica, del tipo:

$ax_{1}^{2}+bx_{1}x_{2}+cx_{2}^{2}$

(Ma sono forme quadratiche tutti i polinomi che in generale abbiano tutti gli elementi al secondo grado, quindi per esempio anche $ax_{1}x_{3}+bx_{3}^{2}+cx_{2}x_{1}+dx_{2}^{2}$ )

è utile utilizzare la cosiddetta matrice Hessiana: una forma che usa l'algebra lineare per rappresentare ed evidenziare il segno delle forme quadratiche.

Difatti vale la seguente eguaglianza:

$ax^{2}+bxy+cy^{2}\quad =\quad {\begin{bmatrix}x&y\end{bmatrix}}\cdot {\begin{bmatrix}a&{\frac {b}{2}}\\{\frac {b}{2}}&c\end{bmatrix}}\cdot {\begin{bmatrix}x\\y\end{bmatrix}}$

e la matrice dei coefficienti della relativa forma quadratica è detta matrice Hessiana:

$H={\begin{bmatrix}a&{\frac {b}{2}}\\{\frac {b}{2}}&c\end{bmatrix}}$

Nella caso della nostra disequazione, la (2), sulla diagonale andranno le derivate parziali seconde pure (non miste), mentre fuori dalla diagonale andranno le derivate miste, all'intersezione delle relative derivate parziali pure. Quindi:

$H={\begin{bmatrix}f_{xx}&{\frac {2f_{xy}}{2}}\\{\frac {2f_{xy}}{2}}&f_{yy}\end{bmatrix}}={\begin{bmatrix}f_{xx}&f_{xy}\\f_{xy}&f_{yy}\end{bmatrix}}$

Ora è finalmente possibile distinguere massimi, minimi e selle poiché, per le proprietà della matrice Hessiana:

• Il punto $P_{0}$ è un massimo se gli autovalori di H sono tutti strettamente negativi (forma definita negativa).
• Il punto $P_{0}$ è un minimo se gli autovalori di H sono tutti strettamente positivi (forma definita positiva).
• Il punto $P_{0}$ è una sella se gli autovalori di H sono tutti non nulli e di segni contrastanti (forma indefinita).
• Se invece almeno un autovalore di H è nullo, allora non abbiamo informazioni sufficienti per stabilire se $P_{0}$ sia massimo, minimo o sella. Non è sufficiente un'approssimazione con un polinomio di Taylor del secondo ordine. (forma semi-definita)

Un metodo più semplice si può utilizzare per le funzioni di sole due variabili, utilizzando 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.

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={\begin{bmatrix}f_{xx}&f_{xy}\\f_{xy}&f_{yy}\end{bmatrix}}$ 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.

Esempi di ottimizzazione libera

Si consideri la funzione di 2 variabili

$f(x,y)=x^{3}+y^{3}+3xy$.

Calcoliamo le derivate parziali prime:

${\frac {\partial z}{\partial x}}=f_{x}=3x^{2}+3y$

${\frac {\partial z}{\partial y}}=f_{y}=3y^{2}+3x$

Quindi il gradiente di $f(x,y)$ è:

$\nabla f(x,y)=(f_{x};f_{y})={\begin{cases}f_{x}=3x^{2}+3y\\f_{y}=3y^{2}+3x\end{cases}}$

I punti critici sono dati dalla soluzione del sistema:

${\begin{cases}f_{x}=3x^{2}+3y=0\\f_{y}=3y^{2}+3x=0\end{cases}}\leftrightarrow {\begin{cases}x^{2}+y=0\\y^{2}+x=0\end{cases}}\leftrightarrow {\begin{cases}y=-x^{2}\\x^{4}+x=0\end{cases}}\leftrightarrow {\begin{cases}x(x^{3}+1)=0\\y=-x^{2}\end{cases}}$

Quindi... $P_{1}\ {\begin{cases}x=0\\y=0\end{cases}}\$ oppure $P_{2}\ {\begin{cases}x=-1\\y=-1\end{cases}}\$

Calcoliamo le derivate parziali seconde:

$f_{xx}=6x$

$f_{xy}=3$

$f_{yy}=6y$

Quindi la matrice hessiana di f(x,y) sarà:

$H={\begin{bmatrix}6x&3\\3&6y\end{bmatrix}}$

Calcoliamo la matrice hessiana nei punti stazionari:

$H(P_{1})=H(0,0)={\begin{bmatrix}0&3\\3&0\end{bmatrix}}$

Questa matrice ha determinante negativo (-9), quindi è un punto di sella.

$H(P_{2})=H(-1,-1)={\begin{bmatrix}-6&3\\3&-6\end{bmatrix}}$

Questa seconda matrice ha invece determinante positivo (27) e primo termine (-6) negativo quindi è un punto di massimo relativo.

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.

Esempi di ottimizzazione vincolata con vincolo esplicitabile

• Ad esempio cerchiamo massimi, minimi e selle della funzione:

$f(x,y)=-x^{2}-y^{2}$

lungo la linea-vincolo:

$y=2+2x$

con x compreso tra -2 e 3.

La linea-vincolo è esplicitabile in quanto y(x)=2+2x. Dunque sostituiamo nella funzione:

$f(x,y(x))=-x^{2}-(2+2x)^{2}=-x^{2}-4-4x^{2}=-5x^{2}-4$

il risultato trovato è una parabola rivolta verso il basso con vertice in (0,-4). Il massimo assoluto è dunque in x=0, unico punto stazionario, di conseguenza il valore di y corrispondente lo troviamo utilizzando l'equazione del vincolo:

$y(0)=2+2x=2$

Sempre di conseguenza, troviamo il valore di f(x,y) utilizzando l'equazione della funzione:

$f(0,2)=-0^{2}-2^{2}=-4$

Nonostante x=0 risulti l'unico punto stazionario, sappiamo per il teorema di Weierstrass (in due dimensioni) che, se la funzione è continua ed il dominio è chiuso e limitato, allora esistono sicuramente un massimo ed un minimo assoluti.

Quindi oltre al punto stazionario trovato (il massimo assoluto), cerchiamo altri punti critici agli estremi del dominio: per come è formata la parabola rivolta verso il basso, agli estremi del dominio x=-2 e x=-3 troveremo dei minimi, uno dei quali sarà assoluto. Per distinguere quale dei due sia assoluto è sufficiente individuare quale tra i due abbia valore di f(x,y) inferiore.

• (Problema geometrico proposto nell'introduzione) Minimizzare la superficie di un generico parallelepipedo di dimesioni a, b, c con volume dato.

Il vincolo è il volume: $a\cdot b\cdot c=Vol\$ con $\ Vol\in \mathbb {R}$.

Le incognite sono i rapporti tra le lunghezze dei lati.

Il punto stazionario di interesse è il minimo assoluto della superficie: $Sup(a,b,c)=2\cdot (ab+bc+ac)$.

Il problema è di ottimizzazione vincolata con vincolo esplicitabile, infatti per esempio possiamo scrivere c in funzione di a e b:

$c=g(a,b)={\frac {Vol}{ab}}$

e possiamo sostituirlo nell'equazione della superficie per tovarne il minimo:

$Sup(a,b)=2\cdot (ab+b\cdot {\frac {Vol}{ab}}+a\cdot {\frac {Vol}{ab}})=2ab+{\frac {2Vol}{a}}+{\frac {2Vol}{b}}$

Ora, per trovare i punti stazionari, calcoliamo i punti che annullano il gradiente:

${\begin{cases}{\frac {\partial Sup}{\partial a}}=2b-{\frac {2Vol}{a^{2}}}=0\\{\frac {\partial Sup}{\partial b}}=2a-{\frac {2Vol}{b^{2}}}=0\end{cases}}$

Risolvendo:

${\begin{cases}b={\frac {Vol}{a^{2}}}\\2a-{\frac {2Vol}{b^{2}}}=0\end{cases}}{\begin{cases}b={\frac {Vol}{a^{2}}}\\a={\frac {Vol}{Vol^{2}}}\cdot a^{4}\end{cases}}{\begin{cases}a={\sqrt[{3}]{Vol}}\\b={\sqrt[{3}]{Vol}}\end{cases}}$

Trovati i valori di a e b, sostituiamo nell'equazione del vincolo per trovare il valore di c, evidenziando così che il punto stazionario trovato rappresenta il caso dell'uguaglianza tra i lati: stiamo parlando di un cubo.

Infine, per verificare formalmente che il punto trovato sia un minimo, costruiamo la matrice Hessiana, calcolando prima le derivate seconde:

$Sup_{aa}={\frac {4Vol}{a^{3}}}$

$Sup_{bb}={\frac {4Vol}{b^{3}}}$

$Sup_{ab}=2\$

Quindi l'Hessiana in $P_{0}=({\sqrt[{3}]{Vol}},{\sqrt[{3}]{Vol}},{\sqrt[{3}]{Vol}})$ sarà:

$H|_{P_{0}}={\begin{bmatrix}{\frac {4Vol}{{\sqrt[{3}]{Vol}}^{3}}}&2\\2&{\frac {4Vol}{{\sqrt[{3}]{Vol}}^{3}}}\end{bmatrix}}={\begin{bmatrix}4&2\\2&4\end{bmatrix}}$

L'Hessiana ha determinante positivo (detH = 12) e termine $Sup_{aa}$ positivo, quindi il punto è un minimo, ed è minimo assoluto perché non ve ne sono altri.

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 \mathbb {R}$ defininiamo la funzione L(x,y,λ):

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

Per trovare i punti stazionari risolviamo il sistema:

$\nabla L={\underline {0}}$

ovvero

${\begin{cases}L_{x}=0\\L_{y}=0\\L_{\lambda }=0\end{cases}}$

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})}={\begin{bmatrix}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{bmatrix}}$

Infine interpretiamo la matrice Hessiana come già visto sopra.

Esempio di soluzione con forma lagrangiana

Figura 3. Illustrazione del problema di ottimizzazione vincolata.

• Supponiamo di voler massimizzare $f(x,y)=x+y$ sotto il vincolo $x^{2}+y^{2}=1$.

Osservazione:Il vincolo è un cerchio di raggio unitario centrato nell'origine, e le curve di livello della f (che è un piano) sono rette diagonali (con pendenza -1), così si può già vedere graficamente che il massimo sarà raggiunto in $({\sqrt {2}}/2,{\sqrt {2}}/2)$ ed il minimo in $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$.

Formalmente, poniamo:

$g(x,y)=x^{2}+y^{2}-1$

e dunque definiamo L:

$L(x,y,\lambda )=f(x,y)-\lambda g(x,y)=x+y-\lambda (x^{2}+y^{2}-1)$

Ora risolviamo il sistema $\nabla L={\underline {0}}$, ovvero:

${\begin{cases}L_{x}=1+2\lambda x=0\\L_{y}=1+2\lambda y=0\\L_{\lambda }=x^{2}+y^{2}-1=0\end{cases}}$

Nota: La derivata rispetto a $\lambda$ corrisponde sempre al vincolo di partenza.

Combinando le prime due equazioni si ottiene $x=y$ (con $x\neq 0$, altrimenti la prima eq. implica l'eguaglianza impossibile 1 = 0).

Sostituendo nella terza eq. si ottiene $2x^{2}=1$, cosicché $x=\pm {\sqrt {2}}/2$ e i punti stazionari risultano:

$P_{1}=({\sqrt {2}}/2,{\sqrt {2}}/2)$

$P_{2}=(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$.

Valutando la funzione studiata f su questi si ottiene

$f(P_{1})={\sqrt {2}}\ {\mbox{ e }}\ f(P_{2})=-{\sqrt {2}},$

dunque il massimo è ${\sqrt {2}}$, raggiunto in $P_{1}$, e il minimo è $-{\sqrt {2}}$, raggiunto in $P_{2}$.

Nota: Essendo f una funzione continua definita sul vincolo che è un insieme chiuso e limitato, essa presenta sicuramente un minimo e un massimo assoluti (per T. di Weierstrass). Nessuno dei due punti stazionari trovati può quindi essere un punto di sella. Non è stato perciò qui necessario utilizzare la matrice Hessiana per verificare il tipo di punto stazionario. In casi più complessi, con insiemi non chiusi e limitati, funzioni non continue o presenza di più punti stazionari è utile o necessario utilizzare la matrice Hessiana.