Problemi di ottimizzazione

Analisi matematica > Problemi di ottimizzazione

lezione
lezione
Problemi di ottimizzazione
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Analisi matematica
Avanzamento Avanzamento: lezione completa al 75%

Introduzione

modifica

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

modifica
  • Un problema geometrico di ottimizzazione libera potrebbe consistere per esempio nella ricerca dei punti di massimo della superficie  . 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 ( ), le incognite sono i rapporti tra le lunghezze dei lati ed infine il punto stazionario da analizzare è il minimo della superficie ( ). 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

modifica

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

modifica

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 è  , 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   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

modifica

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   ed il punto P=(x,y).

L'approssimazione di Taylor, al primo grado, della funzione f in   è:

 

Questa scrittura coincide con la scrittura del piano tangente nel punto P0. Ma, dato che il punto   è 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 (   ).

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

 

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

 

L'equazione la possiamo scrivere anche così:

 


Ora verifichiamo se   è massimo. Quindi rivediamo la definizione di massimo locale:

P0 si dice massimo locale se  
con   un generico intorno circolare, di raggio ε, di  
ma per comodità scriviamo la stessa diseguaglianza così:
 

Essendo il polinomio di Taylor un'approssimazione di  , possiamo considerare  , e scrivere che   è massimo locale se è verificata la disequazione sottostante:

 

Quindi, data la (1), equivalentemente se:

 
Nota: il coefficiente   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:

 

(Ma sono forme quadratiche tutti i polinomi che in generale abbiano tutti gli elementi al secondo grado, quindi per esempio anche   )

è 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:

 

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

 

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:

 

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

  • Il punto   è un massimo se gli autovalori di H sono tutti strettamente negativi (forma definita negativa).
  • Il punto   è un minimo se gli autovalori di H sono tutti strettamente positivi (forma definita positiva).
  • Il punto   è 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   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   :

  • Il punto   è un massimo se l'Hessiano è positivo e   è negativo
  • Il punto   è un minimo se l'Hessiano è positivo e   è positivo.
  • Il punto   è 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

modifica

Una volta trovati i punti stazionari, si costruisce la matrice Hessiana in questo modo:   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   :

  • Il punto   è un massimo se l'Hessiano è positivo e   è negativo
  • Il punto   è un minimo se l'Hessiano è positivo e   è positivo.
  • Il punto   è 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

 .

Calcoliamo le derivate parziali prime:

 
 

Quindi il gradiente di   è:

 

I punti critici sono dati dalla soluzione del sistema:

 

Quindi...   oppure  

Calcoliamo le derivate parziali seconde:

 
 
 

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

 

Calcoliamo la matrice hessiana nei punti stazionari:

 

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

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

Ottimizzazione vincolata

modifica

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

modifica

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:

  è già esplicita
  è esplicitabile ad esempio come  
 , una circonferenza, non è esplicitabile (a meno che, ad esempio, non si spezzi la funzione in   ).

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:
 [1]
lungo la linea-vincolo:
 
con x compreso tra -2 e 3.
La linea-vincolo è esplicitabile in quanto y(x)=2+2x. Dunque sostituiamo nella funzione:
 
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:
 
Sempre di conseguenza, troviamo il valore di f(x,y) utilizzando l'equazione della funzione:
 
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:   con  .
Le incognite sono i rapporti tra le lunghezze dei lati.
Il punto stazionario di interesse è il minimo assoluto della superficie:  .
Il problema è di ottimizzazione vincolata con vincolo esplicitabile, infatti per esempio possiamo scrivere c in funzione di a e b:
 
e possiamo sostituirlo nell'equazione della superficie per tovarne il minimo:
 
Ora, per trovare i punti stazionari, calcoliamo i punti che annullano il gradiente:
 
Risolvendo:
 
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:
 
 
 
Quindi l'Hessiana in   sarà:
 
L'Hessiana ha determinante positivo (detH = 12) e termine   positivo, quindi il punto è un minimo, ed è minimo assoluto perché non ve ne sono altri.

Vincolo non esplicitabile

modifica

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

Teoria dei moltiplicatori lagrangiani

modifica

Procedimento dei moltiplicatori lagrangiani

modifica

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

 

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

Dato un valore   defininiamo la funzione L(x,y,λ):

 

Per trovare i punti stazionari risolviamo il sistema:

 
ovvero
 

Una volta trovati i punti stazionari   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.

 

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   sotto il vincolo  .
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   ed il minimo in  .
Formalmente, poniamo:
 
e dunque definiamo L:
 
Ora risolviamo il sistema  , ovvero:
 
Nota: La derivata rispetto a   corrisponde sempre al vincolo di partenza.
Combinando le prime due equazioni si ottiene   (con  , altrimenti la prima eq. implica l'eguaglianza impossibile 1 = 0).
Sostituendo nella terza eq. si ottiene  , cosicché   e i punti stazionari risultano:
 
 .
Valutando la funzione studiata f su questi si ottiene
 
dunque il massimo è  , raggiunto in  , e il minimo è  , raggiunto in  .
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.
  1. La funzione su WolframAlpha.com