Appunti ISM - Identificazione e stima dei modelli (ex IMCO - Identificazione e Metodi di Controllo Ottimo) + Domande sessione invernale divise per docente

Lezione 1 – Ottimizzazione non vincolata

Per prendere decisioni in azienda, ho generalmente sempre un problema di allocazione delle risorse (siano esse economiche, finanziarie, umane, energetiche, ecc.). Posso farlo in due modi: o le alloco in modo che rispettino dei vincoli (ad esempio la minimizzazione dei costi, intesa come obiettivo dell’allocazione), oppure ottimizzo una cifra di merito. Generalmente in azienda si traduce quindi un problema decisionale in un problema di ottimizzazione, poiché in un’impresa le decisioni generalmente impattano su costi e guadagni.

Gli ingredienti di un problema di ottimizzazione sono le variabili decisionali. Considero ad esempio il vettore delle variabili decisionali u = vettore con n componenti (le componenti possono essere la quantità di prodotto i da comprare e stoccare, la quantità di danaro da investire in un asset, ecc.). Non è uno scalare perché posso avere più variabili decisionali, che raccolgo in questo vettore. Se il vettore u è di dimensione n, vuol dire che il nostro spazio delle decisioni è Rⁿ. Ovviamente questa è un’ipotesi, potrei avere anche vettori ‘binari’, ma generalizzando se ho un vettore di componenti u, dove ogni componente può appartenere a R, il vettore u abita nello spazio Rⁿ. Es. Se n = 2, sono in R² (un piano – Ogni punto di tale piano è una possibile decisione).

Altra componente fondamentale di un problema di ottimizzazione è una funzione obiettivo. Posso quindi formulare il più semplice dei problemi di ottimizzazione come min(L(u)), dove L(u) è proprio la nostra funzione obiettivo. Affinché però questo problema sia ben posto, il dominio della funzione L(u) deve essere Rⁿ, cioè: L(u): Rⁿ → R. L tale che ad un punto dello spazio Rⁿ associa un punto in R (dove R è il codominio della funzione).

Questa è una formulazione davvero molto generale (nonostante considero il minimo), infatti: min() = max(-()), cioè argmin() = argmax(-()). Il che vuol dire sostanzialmente che posso utilizzare la formulazione col minimo come una formulazione di carattere generale (non solo per problemi di ottimizzazione), e soprattutto molti software permettono di formulare solo problemi a minimizzare (o a massimizzare) e quindi posso utilizzare la stessa routine di soluzione del problema, consci delle due formule precedenti.

Procedura per la risoluzione del problema

Condizione necessaria affinché u* sia minimo di L(u) è che il gradiente sia nullo (non la derivata poiché u è un vettore). Condizione sufficiente invece è che, nel caso scalare è che la derivata seconda sia maggiore di zero, in quello vettoriale è che l’Hessiana sia una matrice definita positiva.

{Ricordo che il gradiente è il vettore che ha per componenti le derivate parziali della funzione L rispetto a tutte le variabili, cioè ∇L = [∂L/∂u₁, ∂L/∂u₂, ...]. H invece è la matrice hessiana, ovvero la matrice delle derivate seconde di L rispetto a tutte le variabili componenti di u. Posso vederla come la derivata rispetto ad u del gradiente}.

Conoscendo ora già il ‘risultato’ del mio problema, passiamo alla dimostrazione del risultato stesso, fatta con il metodo variazionale.

Assumo di conoscere u*, ovvero l’argomento che minimizza, rispetto ad u, L(u) [cioè argmin L(u)]. Se facciamo una piccola variazione u* + δu con infinitesimo, L(u* + δu) deve essere > rispetto a L(u*) lo è perché se u* è un punto di minimo, vuol dire che immediatamente dopo u* (cioè in u* + δu) la funzione inizia a crescere.

Metodo variazionale

• Assumi di conoscere la soluzione del problema, ovvero u*;
• Effettua una variazione, cioè δu;
• Verifica le proprietà di cui gode il punto u* (a questo punto hai ottenuto le condizioni di ottimalità per un punto);
• Rimuovi l’ipotesi di conoscere u* (avendo oramai trovato le proprietà da ricercare in un punto, affinché questi sia un punto di minimo).

Andiamo quindi ad utilizzare quest’approccio: Assumiamo di conoscere u* e consideriamo una variazione infinitesima u* + δu. Adesso sappiamo che affinché u* sia un punto di minimo locale, per δu sufficientemente piccoli, L(u* + δu) > L(u*).

Ora, dall’analisi matematica sappiamo che grazie allo sviluppo in serie di Taylor posso approssimare ad un polinomio il valore di una funzione nell’intorno di un punto prefissato (ovviamente sotto ipotesi di regolarità della stessa, cioè che ne esistano sufficienti derivate) e quindi dire che:

L(u* + δu) = L(u*) + ∇L|_u=u* δu + ½ δu^T H|_u=u* δu + … [con gradiente e H matrice Hessiana]

In teoria potrei andare avanti all’infinito, ma a noi sostanzialmente serve solo il segno di L(u* + δu) - L(u*). Tale segno è determinato dallo sviluppo arrestato al primo termine, in prima approssimazione, poiché il contributo dei membri successivi è trascurabile nella determinazione del segno.

Posso quindi dire che u* sia tale che: L(u* + δu) - L(u*) > 0

È possibile trovare una condizione che mi assicura che ∇L|_u=u* δu > 0, per ogni δu. No! Immaginiamo infatti di conoscere un certo δu e consideriamo poi δu = -∇L|_u=u*. Se ∇L|_u=u* > 0, allora ∇L|_u=u* δu < 0, il che non va bene poiché voglio che esso sia positivo per ogni δu.

Quindi, l’unica condizione che assicura che ∇L(u* + δu) - L(u*) ≥ 0 è che ∇L|_u=u* = 0. Quindi in questo modo mi assicuro che la disuguaglianza vale col segno di maggiore o uguale (evito i casi in cui essa è minore di zero), ma non con quello di maggiore stretto. Ecco perché questa è condizione necessaria di ottimalità (affinché u* sia punto di minimo), ma non sufficiente. Del resto, il fatto che il gradiente sia nullo ci assicura soltanto di essere di fronte a un punto di stazionarietà (che può essere massimo, minimo, punto di sella, ecc.).

A questo punto considero il termine successivo della serie di Taylor, cioè ½ δu^T H|_u=u* δu, infatti se il primo termine l’ho posto a zero, è da questo che dipende il segno che sto cercando. Quindi impongo che ½ δu^T H|_u=u* δu > 0.

{Nel caso scalare, esso diventa ½ (∂²L/∂u²) δu² > 0. δu² è un quadrato, quindi sempre positivo. Quindi basta imporre che ∂²L/∂u² > 0, per avere verificata l’equazione. Quindi, nel caso scalare avrò ∇L = 0 e ∂²L/∂u² > 0 come condizioni (necessaria e sufficiente) affinché u* sia punto di minimo.}

Nel caso vettoriale devo porre quindi ½ δu^T H|_u=u* δu > 0, il che vale se H è definita positiva (ovvero se una sua qualunque forma quadratica è sempre maggiore di zero sto in pratica dicendo sempre che H dev’essere positivo). Ma quand’è che una matrice è definita positiva? Nel nostro caso (di H e quindi di matrice simmetrica), essa è definita positiva se ha tutti gli autovalori positivi.

Riassumo che quindi u* = argmin L(u) se:

• ∇L|_u=u* = 0
• H|_u=u* > 0 (la indico così, ma intendo ‘è definita positiva’, ovvero ha tutti autovalori maggiori di zero).

Esempio

min (u₁² + u₂²), con u = [u₁, u₂]

Ponendo il gradiente nullo, ho che ∇L = [2u₁, 2u₂] Che si annulla se u₁ = u₂ = 0

Quindi un candidato ad essere minimo di tale funzione è il punto (0,0).

Consideriamo la condizione sufficiente H = [2 0; 0 2] (dove sulla diagonale principale ho le derivate seconde ‘totali’ e sull’altra ho le derivate seconde parziali, qui nulle). Essa è una matrice simmetrica con due autovalori entrambi pari a due [eig(H) = {2, 2}, ovvero due autovalori positivi verifico quindi anche la condizione di ottimalità sufficiente.

Considerazione finale: tale metodo ci consente di conoscere i punti di minimo locale (abbiamo fatto un’analisi per infinitesimi, quindi è un ragionamento intrinsecamente locale). Quindi tale metodo ci fa trovare un insieme di punti (sia u*₁, che u*₂) di stazionarietà della funzione. Confrontando poi, se tale confronto è possibile, i corrispondenti valori di L, possiamo trovare il punto di minimo globale della funzione (cioè u*₂).

Lezione 2 – Ottimizzazione vincolata (vincoli di uguaglianza)

Consideriamo in questa lezione un problema vincolato: min L(u) a cui però sottopongo un vincolo di uguaglianza f(u) = 0. Poiché u ∈ Rⁿ, allora per essere sicuri che il problema abbia senso, f(u) deve andare da Rⁿ a R^m ovvero ci sono m vincoli e n variabili decisionali. In pratica f(u) = [f₁(u), f₂(u), ..., f_m(u)], quindi ho m equazioni, ognuna in n incognite (quindi ogni f va da Rⁿ a R). Devo poi avere m < n (meno equazioni che vincoli). In realtà queste f non sono lineari, quindi anche se avessi due equazioni in due incognite (es due circonferenze) potrei avere due soluzioni (ho una scelta), ma localmente non mi posso mai spostare (nessuno spostamento è ammissibile, considerando i vincoli) ogni punto che rispetta i vincoli è un punto di minimo locale.

Ciò in pratica vuol dire che il sistema è mal posto, perché non posso applicare il metodo variazionale. Se invece considero m < n, è possibile considerare uno spostamento infinitesimo δu. Posso applicare qui il metodo variazionale.

Assumo quindi di conoscere u*. Non posso però aggiungervi (come faccio solitamente) un δu infinitesimo qualsiasi, poiché devo considerare il vincolo; l’unico spostamento che posso fare è tangente al vincolo.

Formalmente, io voglio che u* sia minimo di L(u), rispettando il vincolo f. Cioè:

L(u* + δu) – L(u*) > 0 : f(u* + δu) = 0

Direzioni tangenti alla superficie vincolare

E come faccio a farlo, a trovare le direzioni tangenti alla superficie vincolare (quelli che vedevo essere gli unici spostamenti fattibili)? Sostanzialmente divido il vettore u in due vettori, di diversa appartenenza, uno il cui numero di variabili sia uguale al numero di vincoli, l’altro con le restanti variabili:

u = [x; w] con x ∈ R^m e w ∈ R^n-m

Facendo ciò, l’idea è lasciare libere le variabili w (che sono quindi le variabili indipendenti) e far variare le variabili x in funzione delle w, in modo che lo spostamento ottenuto rispetti il vincolo (chiamo le x variabili dipendenti).

Esempio: Se il vincolo fosse la retta u₁ + u₂ = 0, se parto dall’origine, δu = (1,1) non è uno spostamento ammissibile. Tuttavia, se pongo u₁ = x e u₂ = w, e faccio sì che δx = 1, ne ricavo (dall’equazione del vincolo) che δw = -1. In pratica lascio libera di variare la variabile indipendente e rendere le variabili x dipendenti dalle w, trovando la dipendenza che mi assicura che il vincolo sia rispettato per ogni δw.

Questa cosa mi permette di rendere il problema da vincolato a non vincolato. Praticamente se la funzione di vincolo f definisce esplicitamente una funzione che lega x a w, in tutto il dominio, allora io posso trasformare in questo modo il sistema, passando da:

min L(u) con vincolo f(u) = 0 → min L(ϕ(w)), senza vincoli.

[Poiché se ho x = ϕ(w), avrò che f(x,w) = f(u) = 0] il problema è falsamente vincolato.

Il problema nasce quando non posso definire una funzione che lega x a w esplicitamente. Se ad esempio avessi la funzione f(x,w) = xw – 1. Col vincolo f(x,w) = 0, avrei che xw – 1 = 0, cioè x = 1/w. Ma per w = 0 essa ha un punto di discontinuità (non è definita in tutto il dominio) non posso scrivere x esplicitamente in funzione di w. In questo caso devo cercare di farlo in modo implicito (ovvero solo nell’intorno del punto di ottimo):

Sviluppo f in serie di Taylor (nell’intorno dell’ottimo, δu = [δx, δw]) e mi fermo al primo ordine:

f(x* + δx, w* + δw) = f(x*, w*) + [F_x | F_w] * [δx; δw]

[Le due F sono due matrici iacobiane, ovvero le matrici delle derivate parziali: F_x = [∂f₁/∂x₁ ... ∂f₁/∂x_m; ... ; ∂f_m/∂x₁ ... ∂f_m/∂x_m].]

Ora porto f(x*, w*) al primo membro e moltiplico le iacobiane per il vettore spostamento:

f(x* + δx, w* + δw) - f(x*, w*) = δf = F_x δx + F_w δw

Affinché lo spostamento (δx, δw) rispetti i vincoli, deve essere nulla.

Quindi, assumendo che F_x sia invertibile, ricavo δx come:

δx = - F_x^-1 F_w δw

È il legame implicitamente definito da f tra x e w nell’intorno del punto di ottimo.

Condizione di ottimalità

A questo punto posso tornare a ragionare su L. Ricordo che la condizione da verificare era:

dL = L(x* + δx, w* + δw) - L(x*, w*) ≥ 0 che rispetti i vincoli (che sono sicura di rispettare se scelgo il δx appena trovato δx = - F_x^-1 F_w δw).

Quindi sviluppo sempre in serie di Taylor fermandomi al primo membro e ottengo:

dL = L_x δx + L_w δw ≥ 0 per ogni spostamento ammissibile (ovvero quelli variando arbitrariamente w e scegliendo arbitrariamente δx = - F_x^-1 F_w δw).

Sostituendo δx, ottengo che la condizione di ottimalità risulta essere:

dL = - L_x F_x^-1 F_w δw + L_w δw ≥ 0

Mettendo δw in evidenza, diventa:

(-L_x F_x^-1 F_w + L_w) δw ≥ 0

Ma visto che δw può essere arbitrario (sia maggiore che minore di zero), l’unico modo per verificare questa disuguaglianza è porre la parentesi uguale a zero.

L_w – L_x F_x^-1 F_w = 0

Condizione necessaria di ottimalità.

Metodo dei moltiplicatori di Lagrange

Esiste un altro metodo per giungere allo stesso risultato ed è quello che utilizza i moltiplicatori di Lagrange.

L_T = L(x,w) + λ f(x,w)

In pratica parto da una funzione lagrangiana che indico con L_T, dove λ è il vettore dei moltiplicatori di Lagrange. Se sono rispettati i vincoli (ovvero f(x,w) = 0), la lagrangiana è pari alla funzione L. Ad esempio nell’ottimo, poiché λf(x*,w*) = 0, allora avrò: L_T(x,w) = L(x,w). In realtà questo è vero non solo per l’ottimo, ovviamente, ma per qualunque punto che rispetti i vincoli.

Proviamo ora a ragionare sulla lagrangiana come ragionavamo sulla cifra di merito (ovvero la L) di un problema non vincolato. Assumiamo di fare una variazione dal punto di ottimo e scriviamo il primo pezzo della serie di Taylor:

L_T = L + λ^T F

(gradiente) = (iacobiana)

NB. La L è una sola, quindi ho un gradiente. Le f sono m, quindi ho una matrice iacobiana.

L_x = 0, λ^T = - L_x F_x^-1

Quindi mi assicuro prima che L_x = 0 e quindi scegliamo λ in modo opportuno.

Poi mi assicuro che anche L_w = L_w + λ^T F_w, ma conosco oramai che λ^T = - L_x F_x^-1.

E quindi imporre che L_w = 0 equivale a dire che:

L_w – L_x F_x^-1 F_w = 0

[sostituendo il valore di λ]

L_w – L_x F_x^-1 F_w = 0

Ciò è valido solo se la parentesi è uguale a zero, cioè se:

In pratica, se cerco i punti che rispettano la condizione necessaria per il mio problema di minimo vincolato, ciò equivale a trovare i punti di stazionarietà della funzione lagrangiana definita come L_T = L(x,w) + λ^T f(x,w). Ciò banalmente si dimostra con un tris di equazioni risolutive che prevedono di porre a zero le derivate della lagrangiana per tutte le variabili di cui essa è funzione:

• L_x = 0
• f(x,w) = 0
• λ^T = - L_x F_x^-1
• L_w – L_x F_x^-1 F_w = 0

Nb. Matematicamente moltiplicare a dx e a sx una matrice non è la stessa cosa. Quando scrivo λ in funzione di L, ragiono come:

λ^T F_x = - L_x

λ^T F_x F_x^-1 = - L_x F_x^-1

λ^T I = - L_x F_x^-1

λ^T = - L_x F_x^-1