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

CERTEZZA EQUIVALENTE.

Ho considerato un investimento con un rendimento aleatorio e una certa distribuzione utilità, definita dalla funzione

utilità. Considerato l’utilità attesa E[u(x)], come la misuro davvero?

Prendo valore atteso di u(x), (u(x) è un’ordinata, quindi E[u(x)] sarà un’ordinata

-1

specifica, la noto indicata nel grafico), e inverto la funzione utilità, facendo u E[u(x)].

Ritorno quindi sull’asse delle ascisse (dove avevo i ritorni, che si misurano in €).

-1

Quindi u E[u(x)] è la mia CERTEZZA EQUIVALENTE, ovvero rappresenta il ritorno

certo che io associo al mio rendimento incerto. E’ cioè la mia visione economica

dell’investimento: sarà quindi tanto peggiore quanto più sono avverso al rischio.

EX. Se vado in banca e mi propongono un portafogli con rendimento a 2%.

Realisticamente, molti si aspetterebbero che non renderà mai il 2%, ma al massimo l’1%. Ecco, l’1% è la nostra visione

deterministica dell’investimento incerto, cioè è la nostra Certezza equivalente.

Invertendo la funzione utilità, in corrispondenza di E[u(x)] (che è ciò che l’investitore usa per decidere, poiché giudica

l’investimento in base al valore atteso dell’utilità). Trasformo il valore atteso dell’utilità in una valutazione economica.

-1

u E[u(x)] > capitale.

Ovviamente investo se Ovvero se il ritorno certo che associo all’investimento incerto, maggiora il

→

mio capitale, allora investo lo vedo come un investimento che sicuramente mi fa guadagnare.

-1

Quindi dire che l’investitore investe solo se E[u(x)] > = u(), equivale a dire che investe solo se u E[u(x)] > capitale.

Lezione 7. – Algoritmi numerici min (),

Pensiamo ad un problema non vincolato. Parto dal l’obiettivo è costruire una successione di punti {u } con k da

k

0 a infinito tale che il limite per k che tende all’infinito, tende a u*:

+∞ ∗

{ } lim =

=0 → +∞

Quindi, l’obiettivo degli algoritmi per la successione numerica dei problemi di ottimizzazione è quello di costruire una

successione di punti che converga ad un punto di minimo locale. Essi sono di aiuto quando un calcolo può essere troppo

complicato da risolvere in forma chiusa. In particolare, la risoluzione è affidata ad un calcolatore che utilizza dei software,

basati su algoritmi di tipo evolutivo: cioè, come detto in precedenza, costruiscono una serie di punti che auspichiamo

convergano a un minimo locale. E’ molto semplice: Se supponiamo di avere un problema a due variabili decisionali,

parto da una certa condizione iniziale u0 e si costruisce una successione di punti che

si spera convergano al punto di minimo u*.

Dal punto di vista pratico posso immaginare il lavoro di un algoritmo numerico

come uno girovagare secondo alcune logiche all’interno dello spazio delle decisioni,

alla ricerca di un punto di minimo locale. Questo girovagare per me formalmente

vuol dire costruire una successione di punti e cercare un punto di minimo u* vuol

→ ∞

dire che il limite per k deve tendere a u*.

Una prima grande distinzione va fatta tra algoritmi numerici per l’ottimizzazione vincolata e per l’ottimizzazione non

vincolata. Affronteremo inizialmente problemi di ottimizzazione non vincolata, detti algoritmi di discesa in quanto fanno

in modo che la funzione al passo successivo assuma un valore inferiore a quello che assume al passo precedente (fx ) <

k+1

f(x ).

k Line Search

Come costruiamo la successione è il problema di oggi. Posso farlo in due modi: con gli algoritmi di o quelli di

Trust-Region . Per entrambi arrivo al passo successivo come u = u + p ma i due metodi si differenziano per come

k+1 k k,

manipolano u .

k

Nei primi cerco lungo una direzione; a ogni passo, posso scrivere che u = u + p , con p

k+1 k k k

vettore: la domanda è come scegliere p . Lo faccio fissando la direzione lungo cui è p e

k k

→

scegliendo in maniera ottimale il modulo u = u + αd [con d direzione, line su cui cerco il

k+1 k k k

punto successivo, fissata].

( + ),

Dopodiché si risolve per trovare l’α ottimale.

∝ min ())

Il vantaggio di risolvere questo problema ad ogni passo (e non semplicemente risolvere è che α è

semplicemente il modulo (è uno scalare), quindi io trasformo la variabile decisionale da un vettore a n variabili a uno

→

scalare il problema ad alta dimensionalità, diventa monodimensionale. Esistono anche metodi che scelgono α per

tentativi (ne provano un paio, vedono quello migliore e poi passano al prossimo).

LINE SEARCH

I metodi di sono vari a seconda di varie cose, ad esempio come scegliere la direzione.

- La scelta più ovvia è scegliere la direzione del gradiente, con verso opposto (perché il gradiente mi indica la direzione di

massima pendenza, ma io voglio scendere e non salire, quindi verso opposto). Secondo il metodo del gradiente (di

∇L|

d = -

Sleepest Descent – Discesa più ripida) k uk

Quest’algoritmo può essere lento a convergere verso un punto di minimo locale: per aumentarne le prestazioni,

considerando solo la conoscenza del gradiente della funzione obiettivo, si utilizza anche un’informazione relativa

all’essiano, con l’algoritmo di Newton. Assumo qui che in k=0 il gradiente della funzione nel punto uk, con k=0 sia

→ ∇L|

diverso da zero: se fosse uguale a zero, mi troverei già nel punto di minimo. In k=0, ≠ 0

uk

L‘Algoritmo di Newton

- mi dice che, data L, sviluppala in serie di Taylor intorno a u .

k

L(u + p ) = Lu + p ∇L| + ½ p L | p

Tk Tk

Scrivo quindi: k k k uk uu uk k

Faccio poi il minimo di questo sviluppo, rispetto a p : cioè approssimo in ogni punto la funzione ad

k

una quadratica (facile da minimizzare) e trovo il punto di minimo di tale funzione: esso sarà il

punto successivo da cui partire. Per trovare quindi il minimo, impongo la derivata uguale a zero:

uu-1

∇L| ∇L|

+ L | p = 0 e quindi p = L | . E quindi ho trovato il mio passo, più velocemente

uk uu uk k k uk uk

rispetto all’algoritmo precedente.

→ il vantaggio è trasformare il problema difficile di cui non conosciamo la soluzione analitica in una successione di

problemi semplici (semplici perché ne conosciamo la soluzione analitica).

È ancora un algoritmo di line search perché la direzione scelta è ancora una direzione di discesa. Infatti, posso scrivere

p ∇L p

= – L p

Tk Tk

∇L p Tk

= – L p e, moltiplicando per , ottengo:

uu k uu k

Ma L è una matrice definita positiva, quindi maggiore di zero, ma col meno davanti tutto quel termine è minore di

uu

zero.

→ Tk ∇L|

Quindi considerando l’approssimazione al primo ordine, ovvero L(u + p ) = Lu + p , la quantità in rosso è per

k k k uk

l’uguaglianza di prima negativa e quindi sommando ad L qualcosa di negativo, sto scendendo.

NB. Ho come svantaggio il calcolo dell’essiano. Esistono per questo algoritmi di quasi-newton, che invece di calcolare

l’essiano, lo approssimano.

TRUST-REGION

Al contrario, gli algoritmi di , considerano una regione invece che una

direzione: sempre nel caso di due variabili decisionali, l’algoritmo sceglie prima la regione in

cui cerca (intorno di u di raggio fissato r = modulo massimo dello spostamento) e poi cerca il

k

punto successivo in quell’intorno. [non sempre l’intorno è circolare, può essere un ellissi o

altro. Considero il limite della regione, perché altrimenti l’approssimazione in serie non ha più

davvero senso, essendo troppo lontana dal punto di partenza]

L’idea è sempre la stessa: minimizzo un approssimante quadratico:

( ) + p ∇L + ½ p L p ‖ ‖

Tk Tk ma col vincolo ≤ r (che modella la regione in cui cerco) [‖‖=modulo]

uu k

Sto quindi rendendo il problema da non vincolato a vincolato, aggiungendo un vincolo. Potrei quindi pensare che il Trust-

Region sia meno efficiente del Line Search, ma tale algoritmo risulta essere più rappresentativo della realtà. Infatti, nel Line

Search noi andiamo a cercare una funzione che va bene in tutto il dominio, facendo un’approssimazione davvero grande.

Mentre nel Trust Region noi andiamo a trovare quell’approssimante della funzione che la approssima bene solo in una

certa regione del dominio, quindi la situazione è un tantino più realistica.

Lezione 8.

Gli algoritmi per risolvere un problema vincolato non fanno altro che trasformarlo in un problema non vincolato.

Facciamo una breve parentesi sui metodi di risoluzione di problemi vincolati con vincoli di disuguaglianza:

()

Con G(u) ≤ 0

Posso avere due casi: →

1. U* è tale che G(u) < 0 nessun vincolo è attivo, non vale mai il caso in cui G(u) = 0 e sto dentro la regione

∇L| = 0

vincolata. Quindi la condizione di ottimalità diventa semplicemente u*

2. Quando esiste una i tale che G (u) = 0 (con G (u) è l’i-esima equazione del sistema di equazioni G), trattare il

i i

sistema non è semplice.

Per risolvere il problema uso i moltiplicatori di Kuhn Tucker: costruiamo una funzione ausiliaria, composta dalla cifra di

T

merito L(u) e questi moltiplicatori μ che moltiplicano il vincolo:

L T

= L(u) + μ G(u)

Le condizioni di Kuhn Tucker (4) mi dicono che per trovare le condizioni necessarie di ottimalità deve accadere che la

L T

∇L + μ G(u) = 0

derivata di questa funzione ausiliaria su du sia nulla: = 0 e cioè che (1)

L ≤

G(u)

≤ 0,

E che la derivata della funzione ausiliaria su dμ sia minore o uguale di zero: cioè (2) [ovvero il rispetto

dei vincoli].

A queste due condizioni, si aggiungono due ulteriori equazioni:

T →

μ G(u) = 0 [CONDIZIONE COMPLEMENTARE]

(3) fondamentale, perché mi dice che questi moltiplicatori sono tali

≤

che, se G(u) non è nulla, sono loro ad essere nulli. Ciò mi assicura, insieme a G(u) che i vincoli siano rispettati e che

all’ottimo il valore della funzione ausiliaria è proprio esattamente pari ad L (trasformando un problema vincolato in uno

non vincolato)



μ 0 (4)

Vediamo quindi ora come sfruttano queste idee gli algoritmi numerici di risoluzione di problem