Pagine da Matematica Finanziaria Progredito-9 PDF

Preview

Summary

OPTIMIZATION ALGORITHMS – ALGORITMI DI OTTIMIZZAZIONE1. OTTIMIZZAZIONE CONTINUA SENZA VINCOLIPANORAMICA Metodo del gradiente (discesa) (SI) Metodo della regione di fiducia (Trust-region method)(SI) Subgradient method (NO) Quasi Newton method (NO) Simplex search (NO) (Il metodo 1 si chiama a gradient...

Description

OPTIMIZATION ALGORITHMS – ALGORITMI DI OTTIMIZZAZIONE 1. OTTIMIZZAZIONE CONTINUA SENZA VINCOLI PANORAMICA 1. Metodo del gradiente (discesa) (SI) 2. Metodo della regione di fiducia (Trust-region method)(SI) 3. Subgradient method (NO) 4. Quasi Newton method (NO) 5. Simplex search (NO) (Il metodo 1 si chiama a gradiente o a discesa ci dice di cercare ad ogni passo della ricerca la direzione più ripida verso l’ottimo (ripido definito dalla derivata).) SECOND DERIVATIVE EXTREMUM TEST • Idea: se la funzione è continua e due volte differenziabile l’ottimo può essere calcolato direttamente. • Trivial for 1-d case:

•

Problema: richiede due volte parzialmente differenziabile (la derivata seconda esiste)) per problemi n-dimensionali; il testo della matrice Hessiana può non essere risolutivo.

1.1 METODO DEL GRADIENTE Idea: se la funzione obiettivo è definita esplicitamente, differenziabile e senza vincoli allora il problema può essere risolto seguendo iterativamente un gradiente (derivata più ripida) dal punto di partenza verso l’ottimo. Outline: • Genera una sequenza di punti 𝑥 (0), 𝑥 (1) , … , 𝑥 (𝑛) che convergono all’ottimo loc ale 𝑥 ∗ . • Per ogni 𝑥 (𝑘) trova una direzione di discesa 𝑠 (𝑘) ∈ 𝑅𝑛 e un passo 𝑎 (𝑘) > 0 tale che: 𝒇(𝒙(𝒌) + 𝒂(𝒌) 𝒔(𝒌) ) < 𝒇(𝒙(𝒌)). Procedura: • Genera una soluzione casuale 𝒙(𝟎) . • Itera finché non trovi l’ottimo: o Determina una direzione di discesa 𝑠 (𝑘) ; o Determina un passo 𝑎 (𝑘) > 0; o Aggiorna 𝒙(𝒌+𝟏) = 𝒙(𝒌) + 𝒂(𝒌) 𝒔(𝒌) (dal nuovo punto poi itero nuovamente.) DISCESA PIÙ RIPIDA (METODO DEL GRADIENTE)

81

(formula poco importante. Mi interessa sapere che se mi muovo lungo il gradiente ho la funzione minore di f(x(k)). L’obiettivo è trovare la sequenza degli h tale per cui la funzione raggiunge il suo minimo. Può essere risolta soprattutto per funzioni convesse.) DISCESA PIÙ RIPIDA (METODO DEL GRADIENTE)

(Immagino di tagliare un piano e prender e il gradiente in quel piano, il piano è orizzontale e mi muovo lungo il gradiente. Le curve rappresentano i valori in cui la funzione ha i medesimi valori (piani della funzione). Taglio la funzione, mi muovo nel piano con uno step alfa, calcolo la direzione e mi muovo ancora di alfa e poi continuo. Devo seguire la direzione della derivata prima più ripida.) DISCESA PIÙ RIPIDA (METODO DEL GRADIENTE) Limiti: • Trovo solo ottimi locali; (calcolo il gradiente nell’intorno di x0.) • Posso avere scarsa convergenza se sono molto vicino all’ottimo (nel caso peggiore posso zigzagare attorno); • Il gradiente di una funzione può non essere sempre calcolato. DISCESA PIÙ RIPIDA (METODO DEL GRADIENTE)

(Lo zigzag potrebbe avere problemi quando mi trovo in una narrow valley. ) 1.2 METODO DELLA REGIONE DI FIDUCIA Idea: • Approssimare la funzione obiettivo f con una funzione più semplice q per un intorno N (chiamata regione di fiducia) attorno al punto x; • Da x calcolare il passo di prova s per minimizzare attorno a N (= trust-region subproblem), altrimenti riduci N e ripeti il calcolo dello step di prova (Nella minimizzazione non prendiamo più f ma consideriamo q.)

82

Implementazione

(Approssimo la funzione da ottimizzare con una funzione che si muove in modo più regolare (es. funzione convessa) e cerco di ottimizzare la nuova funzione. Potrei prendere un’approssimazione quadratica in s utilizzando l’approssimazione di Taylor. Nella componente lineare della approssimazione quadratic a approssimo utilizzando il gradiente della funzione. Poi risolvo il problema di ottimizzazione per la funzione quadratica, in modo da rimanere all’interno di una regione specifica (Δ).) SEGUE

(Posso muovermi cercando di ottimizzare la funzione e più mi avvicino all’ottimo e più restringo la regione di fiducia. Ottimizzo in una parte delta della funzione. Metodo a gradiente: prendo la direzione più ripida; Metodo della regione di fiducia: approssimo la funzione con un’approssimazione di Taylor fino al secondo grado e poi ottimizzo la funzione quadratica in un intervallo (Δ) della funzione quadratica.) SEGUE Problem: approach does not work if the Hessian matrix H is negative. Alternative: assume that a first-order approximation is valid in a neighbourhood of the current iterate solution x, i.e.,

(più riduco l’ordine dell’approssimazione e maggiore è la perdita di approssimazione.) 2. OTTIMIZZAZIONE CONTINUA CON VINCOLI PANORAMICA 1. Metodo della penalità (SI) 83

2. Kelly's cutting plane algorithm 3. Reduced gradient method 4. Active set strategy 5. Linear programming (Simplex and interior point method) -> problema lineare con vincoli lineari (SI) 6. Quadratic programming -> problema quadratico con vincoli lineari (SI) 7. Sequential quadratic programming 8. Non-linear programming with semi-infinite constraints 9. Minimax programming (Questi sono tutti i metodi che potrei avere per l’ottimizzazione vincolata.) 2.1 METODO DELLA PENALITÀ Idea: • Riscrivi la funzione obiettivo, in modo che includa i vincoli; • Inizialmente saranno generate solo soluzioni inammissibili, ma ci si sposta verso la regione delle soluzioni ammissibili verso la fine del processo di ottimizzazione (da soluzioni inammissibili, quindi esterne allo spazio di ricerca ammissibile, ci spostiamo verso soluzioni ammissibili). • NB: le soluzioni ottimali di solito si trovano sul confine tra la regione ammissibile e quella non ammissibile (all’incrocio tra la regione ammissibile e la regione non ammissibile). (Se devo massimizzare questa funzione, con questo vincolo. Riscrivo la funzione obiettivo così da includere i vincoli. ➔ VINCOLI DI UGUAGLIANZA Per un problema con vincoli di uguaglianza …

… possiamo ottenere una versione del metodo della penalità senza vincoli:

(s.t = such that. Per un problema di minimo riscrivo il vincolo in modo che il vincolo sia uguale a 0. Sommatoria dei vincoli al quadrato per dare ancora più peso ai vincoli. Posso scrivere questo come un problema senza vincoli: il minimo di una funzione gamma, dove la funzione è f(x) + sigma * sommatoria dei vincoli di uguaglianza al quadrato. Al quadrato per aumentare la forza del vincolo.) VINCOLI DI DISUGUAGLIANZA Per vincoli di disuguaglianza...

... possiamo ottenere una versione del metodo della penalità senza vincoli:

(Se avessi un vincolo di disuguaglianza potrei risolvere il problema come minimizzazione della funzione gamma: f(x) + sigma*sommatoria dei vincoli al quadrato oppure se voglio che diventi il più piccolo possibile prendo il massimo tra il vincolo e zero e aggiungo questo come sommatoria in a f(x) + sigma*sommatoria. Così se aggiungessi qualcosa di negativo questo andrebbe solo ad ottimizzare la funzione ma non spingerebbe il vincolo ad essere soddisfatto. 84

g+ sta ad indicare (forse) max tra g(x) e 0 perciò dovremmo pensare che ogni valore della funzione si prende il max tra g(x) e 0, e lo butto dentro la funzione gamma. Le due funzioni (una con gamma e una senza), sono diverse perché la prima ha il quadrato per cui rafforza di più il vincolo.) Osservazioni: • Il metodo qui presentato è il metodo della penalità esterna, perché il confine tra la regione ammissibile e la regione non ammissibile è approcciato dall’esterno. • Per vincoli più forti ha senso usare il metodo della penalità interna, il quale inizia la ricerca dall’interno della regione ammissibile e si sposta verso l’esterno. METODO DELLA PENALITÀ INTERNA

(Se scrivo la sommatoria con il meno e il reciproco allora faccio l’interior penalty.) SEGUE

(Nell’exterior penalty cerco di raggiungere l’ottimo partendo da punti non ammissibili. Nell’interior penalty invece provo a raggiungere l’ottimo che si trova sul confine partendo dalla regione ammissibile.) 3. LINEAR PROGRAMMING (LP) Il problema mathematical programming è il problema vincolato dato come:

85

PROBLEMA LP • È un problema matematico dove sia la funzione obiettivo che i vincoli sono lineari. Due principali tecniche (iterative): 1. Metodo del simplesso; 2. Metodo del punto interno (interior point method, disponibile su MATLAB) (funzione obiettivo e vincoli sono lineari. Da sapere solo quali sono non come funzionano le tecniche.) 3.1 SIMPLEX METHOD (NO EXAM) Observation: LP problems are linear and hence convex all extreme points of convex constraint problems are at the boundary between feasibility and infeasibility the global optimum is an extreme point. Idea: given a current extreme point, look for an adjacent extreme point such that the objective function is improved and stop when no further improvements can be made extreme points can be obtained by using the so-called standard LP form, which just contains equalities, i.e.,

Idea (cont):

3.2 INTERIOR POINT METHOD (NO EXAM) Observation – Duality theory: • a LP problem can be expressed as a mirror-image (dual) that corresponds fully to the original (primal) formulation: minimization of the primal variables corresponds to maximization of the dual variables. • if either dual problem has an optimal solution than both have one. • in case of convexity (linear problems) that solution is identical. • in general, duality provides only a lower bound. Idea •

to take a shortcut through the middle of the feasible set instead of searching along the extreme points. • exploit correspondence between primal and dual formulations of an LP problem by using complementary slackness and an interior penalty function. Advantages • much faster than the simplex method (polynomial time whereas the simplex algorithm is nonpolynomial in the worst case)

86

LINEAR PROGRAMMING (LP) (DA SAPERE) MATLAB function La optimization toolbox include la funzione "linprog", che risolve problemi LP del tipo:

LINEAR PROGRAMMING (LP) (DA SAPERE)

(EXAM: Se ho un problema di massimo devo riscrivere il problema in termini di minimo. Così trovo C, poi trovo A e b, Aeq e Beq e inserisco i lower e upper bound se ci sono. NB: c’è un errore, il vettore C è un vettore colonna non riga! Quindi nella scritta sopra sarebbe [-1; -1].) QUADRATIC PROGRAMMING (QP) Obiettivo QP è un problema in cui la funzione obiettivo è quadratica e i vincoli sono lineari. Un problema quadratico può essere scritto come:

Può essere risolto usando l’approssimazione locale di secondo ordine usando il metodo della regione di fiducia o by active sets:

(Per trovare la matrice hessiana si raccoglie ½ a fattor comune e poi i coefficienti dei termini al quadrato vanno nella diagonale mentre il coefficiente misto viene diviso per due e inserito nella diagonale secondaria.) 4, APPLICATIONS OF LP AND QP IN FINANCE 4.1 LP/QP E FRONTIERA EFFICIENTE DEL MODELLO MEDIA-VARIANZA Obiettivo: Calcolare la frontiera efficiente del modello media-varianza per un portafoglio.

87

(Per risolvere questo problema devo minimizzare la varianza e massimizzo il rendimento atteso così da trovare i punti estremi.) CALCOLARE LA FRONTIERA (Step 1): Calcolare i punti estremi di del rendimento atteso.

(problema QP perchè la funzione è quadratica e i vincoli sono lineari.) CALCOLARE LA FRONTIERA (Step 2) – NaiveMV.m in MATLAB

(Anche questo è un problema quadratico (QP). r barrato è la stima del rendimento atteso → in genere, si prende la media perché il valore medio del rendimento è molto difficile da trovare.) 4.2 QP E SHARPE’S STYLE ANALYSIS Equazione dalla style analysis di Sharpe

Perchè abbiamo bisogno della quadratic programming (QP)?

88

(L’obiettivo è minimizzare l’errore al quadrato per aumentarne il peso. Questa funzione obbiettivo è sempre quadratica e in MATLAB viene trattata come un algoritmo di minimi quadrati. (vedi optimization toolbox p. 6): type linear least-squares. Nell’analisi di Sharpe C sono i rendimenti dei fattori, x sono i beta e d è la serie storica del fondo. L’algoritmo mldivide si utilizza per l’analisi weak mentre l’algoritmo migliore con analisi strong per sharpe è lsqlin.)

→

Se la scrivo così ho:

NB: funzione seno e coseno non sono lineari né quadratiche ma sono funzioni smooth non linear → per questo uso fminbnd o fminsearch.

89...