Pagine da Matematica Finanziaria Progredito-8 PDF

Preview

Summary

2 QP e style analysis di Sharpe EQUAZIONE DELLA SHARPE STYLE ANALYSIS(Nell’analisi di Sharpe vogliamo trovare il benchmark di stile trovando la combinazione dei beta tale per cui minimizzo la varianza degli errori al quadrato con il vincolo che i beta siano tutti positivi e che la somma dei beta sia...

Description

2.1 QP e style analysis di Sharpe EQUAZIONE DELLA SHARPE STYLE ANALYSIS

(Nell’analisi di Sharpe vogliamo trovare il benchmark di stile trovando la combinazione dei beta tale per cui minimizzo la varianza degli errori al quadrato con il vincolo che i beta siano tutti positivi e che la somma dei beta sia uguale a 1. La funzione che vogliamo minimizzare è la varianza, che è una funzione quadratica e per cui anche questo è un problema di ottimizzazione quadratica.) PERCHÈ ABBIAMO BISOGNO DELLA QUADRATIC PROGRAMMING?

(Guarderemo solo ad un sottoinsieme di quadratic programming perché questo è un problema di ai minimi quadrati o least square.) 3. CHALLENGES IN OPTIMIZATION (DA SAPERE) 1. non-differentiability (non differenziabilità) → non riesco a calcolare le derivate della funzione quindi non trovo il gradiente. 2. non-linearity (non linearità) → non linearità e non convessità, se la funzione obiettivo ha i vincoli non lineari e non convessi allora questi problemi sono più difficili da risolvere. 3. non-convexity (non convessità). 4. constraints (vincoli)→ maggiori i vincoli e maggiore la difficoltà perché si restringe lo spazio di ricerca, a seconda del tipo di vincolo si possono anche creare discontinuità nello spazio di ricerca (macchie ammissibili) pertanto questo è problematico. 5. multiple objectives (obiettivi multipli) → la funzione potrebbe avere diversi ottimi, maggiore è il numero degli obiettivi e maggiore è la difficoltà. 6. high dimensionality (elevata dimensionalità) → un problema di ottimizzazione con un’elevata dimensionalità è difficile da risolvere. Esempio: 2000 titoli equivalgono alla stima di 2000 parametri, maggiore il numero maggiore la difficoltà 7. stochasticity (stocasticità) → la funzione obiettivo non è misurata in modo deterministico ma c’è una componente di errore che potrebbe rendere più completo il sistema. 8. time dependency (dipendenza dal tempo ). 9. complexity of the objective function evaluations (complessità della valutazione delle funzioni obiettivo). 10. lack of features in the search landscape (mancanza di caratteri nello spazio di ricerca).

71

CHALLENGES IN OPTIMIZATION • NP-hardness: la complessità di un problema (inteso come sforzo computazionale o dimensionale per risolverlo) aumenta esponenzialmente con la dimensione delle istanze del problema; • per NP-hard problems nessun algoritmo conosciuto è in grado di risolvere tutte le istanze in un tempo polinomiale ma... • c’è la possibilità di scrivere un algoritmo per un problema NP-hard che approssimi una soluzione di un problema nel tempo polinomiale. (NP = non polynomial, questi problemi dovuti alla complessità crescono in modo esponenziale con la dimensione del problema.) CHALLENGES IN OPTIMIZATION Osservazione: • Ci sono strumenti per le diverse classi di problem di ottimizzazione Quindi bisogna... • Saper classificare il problema; • Sapere quale strumento meglio risolve una classe di problemi. CHALLENGES IN OPTIMIZATION Osservazione: • Alcuni strumenti possono essere utilizzati senza conoscerne il funzionamento, altri richiedono conoscenze specifiche; • Sfrutta qualsiasi tipo di conoscenza riguardo il problema nello strumento (problem solver); • La rappresentazione del problema (funzione obiettivo e parametri) è importante per riuscire a risolverlo. 4. CLASSIFICAZIONE DEI PROBLEMI DI OTTIMIZZAZIONE FEATURES OF OPTIMIZATION PROBLEMS | CARATTERISTICHE DEL PROBLEMA DI OTTIMIZZAZIONE 1. minimization vs. maximization minimizzazione vs. massimizzazione 2. continuous vs. discrete continuo vs. discreto 3. numerical vs. combinatorial numeric vs. combinatorio 4. linear vs. nonlinear lineare vs. non lineare 5. convex vs. nonconvex convesso vs. non convesso 6. unconstrained vs. constrained non vincolato vs. vincolato 7. single objective vs. multiple objectives un obiettivo vs. multi obiettivo 8. deterministic vs. stochastic deterministico vs. stocastico 9. static vs. dynamic statico vs. dinamico 10. explicitly defined vs. implicitly accessible definito esplicitamente vs. accessibile implicitamente 4.1 Minimizzazione vs. Massimizzazione DOBBIAMO DISTINGUERE TRA MIN E MAX? • è sufficiente considerare problemi di minimizzazione solo se un problema di massimizzazione può essere scritto come un problema di minimizzazione per: max f(x) = min -f(x) e min f(x) = max - f(x) (min f(x) = max (- f(x)) alternativa min f(x) = max (1/f(x)). Nei software può essere utile questa uguaglianza.) 4.2 Continuo vs. Discreto CONTINUO: (es. Spazio di ottimizzazione di portafoglio) • spazio di ricercar quasi continuo • examples: finance problems, data clustering DISCRETO: (es. Rischio di credito, ai client viene data una classificazione in base al merito creditizio: A, B , C.) • spazio di ricercar discrete, come: • esempi importanti: problemi interi e booleani; • esempi: problemi legati alla decisioni d’investimento. 72

• •

NB: problemi discreti non sono mai convessi; NB: dipendono dalla dimensione dello spazio di ricerca, spesso più complicati dei problemi continui.

PROBLEMI INTERI (lo spazio di ricerca è un sottoinsieme dei numeri interi es. capital budgeting) • •

Example capital budgeting: Invest an amount z in n investment opportunities optimally Note: linear integer problems cannot be simply solved as linear programming problems

CAPITAL BUDGETING – AN EXAMPLE • Invest €14.000 in 4 investment opportunities optimally o inv1 requires €5000 with present value €8000 o inv2 requires €7000 with present value €11000 o inv3 requires €4000 with present value €6000 o inv4 requires €3000 with present value €4000

(Prima cosa da fare è scalare tutto su mille. L’obiettivo è massimizzare la somma dei valori attesi con il vincolo che posso investire fino a 14 mila.) OTHER EXAMPLES • feature selection in probability of default analysis; (dopo aver stimato il modello di regressione devo decidere quali fattori inserire e se consideriamo tutto il possibile spazio di scelta questo è un problema discreto) • investment decisions with binary choice (invest or don't invest). 4.3 Numerici vs. Combinatori PROBLEMI NUMERICI SONO • continui o discreti; • examples: equation solving, PD bucketing, control optimization PROBLEMI COMBINATORI SONO: • discreti e basati sul calcolo combinatorio; • legati alla ricerca di un’allocazione ottima delle risorse; • tipicamente ben definiti ma complicati da risolvere • examples: logistics (staff scheduling), graph problems 4.4 Convessi vs. Non convessi PROLEMI CONVESSI • problemi dove f è convessa e S è un insieme convesso, c’è solo un ottimo locale = ottimo globale. PROBLEMI CONCAVI • problemi dove f è concava e S è un insieme convesso, gli ottimi locali sono al confine della regione ammissibile.

(Se il problema non è convesso allora è più difficile da risolvere, perché posso avere più ottimi locali. Le funzioni non-convesse invece mi portano a ottimi locali ed è difficile da risolvere.)

73

DEFINIZIONE DI UNA FUNZIONE CONVESSA

4.5 Lineare vs. Non-lineare PROBLEMI LINEARI E NON LINEARI • Un problema è un Linear Programming (LP) quando la funzione obiettivo e i vincoli sono lineari (espressi da funzioni affini) altrimenti il problema è non lineare (NLP).

(Il problema qui è scritto in due modi equivalenti. MATLAB richiede la struttura matriciale.) PROPRIETÀ IMPORTANTI DEI PROBLEMI DI LP • I problemi LP sono convessi o concavi; • Qualsiasi ottimo locale è un ottimo globale; • Gli ottimi locali sono ai confini dello spazio di ricerca ammissibile; • Lo spazio ammissibile è un poliedro in cui la soluzione ottima corrisponde ad uno dei suoi vertici. SOLUZIONI ALGORITMICHE • Problemi LP possono essere risolti in modi molto efficienti, ad esempio con l’algoritmo del simplesso (simplex) o metodo interiore (interior method); • Molti problemi reali possono essere semplificati e trasformati in un problema lineare o quasi-lineare. PROBLEMI DI QUADRATIC PROGRAMMING (QP) • Un problema di QP è un problema in cui la funzione obiettivo è quadratica e i vincoli sono lineari; • Anche i problemi di QP possono essere risolti in modo molto efficiente. 4.6 Constrained vs. Unconstrained UNCONTRINED PROBLEM

CONSTRAINED PROBLEM (ho determinati vincoli)

COME I VINCOLI INFLUISCONO SULLO SPAZIO DI RICERCA 74

•

i vincoli dividono lo spazio di ricercar in regioni ammissibili e regioni non ammissibili (infeasible)

(La presenza di vincoli reduce lo spazio di ricerca. Maggiori sono i vincoli e maggiore probabilità ho di ridurre lo spazio di ricerca in spazi di ricerca discontinui, pertanto, se l’ottimo globale è in uno spazio di ricerca diverso da quello in cui parto può essere molto difficile saltare da uno spazio all’altro. Se ho un problema non vincolato e costruisco un problema vincolato a partire da quello non vincolato, il valore ottimo della funzione del problema vincolato dovrà essere maggiore o al più uguale al valore ottimo del problema non vincolato.) SIGNIFICATO DI PROBLEMI VINCOLATI • La maggior parte dei problemi di ottimizzazione sono problemi vincolati; • I problemi vincolati sono più difficili da risolvere dei problemi non vincolati; • I problemi con vincoli complessi richiedono tecniche particolari di ottimizzazione. 4.7 Single-objective vs. multiple objective

(Problema ad un obiettivo: ho solo una funzione da ottimizzare. Un problema multi-obiettivo invece ha una serie di funzioni da ottimizzare.) SEGUE Single-objective optimization: Multiple-objective optimization:

75

SEGUE

(Nei problemi a due o più obiettivi la soluzione è una frontiera efficiente (frontiera di Pareto).) 4.8 Deterministico vs. Stocastico PROBLEMI STOCASTICI • i problem stocastici sono frequenti nella funanza, come un problema di ribilanciamento del portafoglio ad esempio; • in engineering, e.g., noisy measurements of machine performance. Quali sono le sfide? • Creare modelli realistici e probabilistici; • Giudicare la qualità delle soluzioni • I processi stocastici richiedono di considerare grandi alberi degli scenari ottimali, ad esempio, problemi di complessità computazionale. 4.9 Statici vs. Dinamici PROBLEMI DINAMICI • I problemi dinamici sono problemi di ottimizzazione che sono funzioni del tempo: Esempi: • Problemi di strategia d’investimento in finanza (discreti) • Problemi di controllo dell’ottimizzazione nell’ingegneria (continui) NB: I problemi dinamici al tempo continuo hanno infinite dimensioni. (I problemi dinamici sono funzione del tempo. Ad esempio, voglio ottimizzare il portafoglio, se prendo un’assicurazione, in modo da bilanciare duration tra un anno e tra due anni. Voglio cercare l’ottimizzazione che mi permette di uguagliare la duration in due periodi differenti.) 4.10 Esplicitamente definiti vs. Implicitamente accessibili PROBLEMI ESPLICITAMENTE DEFINITI (riesco a scrivere la funzione) • la funzione obiettivo (e i vincoli se ci sono) puo essere esplicitamente descritto da equazioni Esempi:

(Se voglio ottimizzare questa funzione (non lineare, funzione coseno è periodica e termini alla 4 e alla 2), non posso utilizzare programmazione lineare per risolvere questo problema e nemmeno un algoritmo di programmazione quadratica.) SEGUE PROBLEMI IMPLICITAMENTE ACCESSIBILI (non riesco a scrivere la funzione) La funzione obiettivo (e/o i vincoli, se ci sono) possono essere ottenuti solo da: 76

• "black-box" (oracle) or • a non-trivial trasformazione uni-direzionale dallo spazio di ricerca al dominio della funzione obiettivo. Esempi: • data clustering based on centroid representation; • machine performance optimization (measurement of an objective variable for a set of parameter inputs). CHALLENGES LEGATE A PARTICOLARI PROBLEMI 1. Multimodality (Multimodalità: più ottimi locali) problema: deception from the global optimum / “inganno” dall’ottimo globale

(L’ottimo globale si trova al centro. Se mi muovo lungo il gradiente è difficile arrivare all’ottimo globale.) CHALLENGES 2. Ridges problema: correlazione tra i parametri del problema

(Nelle ridges, se abbiamo correlazione tra i paramenti, abbiamo che i valori su questo ridges tendono a essere equivalenti, quindi si tende a muoversi lungo quella correlazione e può essere difficile trovare gli ottimi.) CHALLENGES 3, Plateaus problema: • molte soluzioni con lo stesso valore e discontinuità. • Caso estremo: caso dell’ago nel pagliaio:

77

(L’ottimo qui sarebbe il punto sopra ma la funzione è tutta costante tranne nel puntino, se uso un algoritmo di ricerca tutto basato sulle derivate molto spesso non riesco ad uscire da questo problema.) CHALLENGES 4. Noise problema: misura della funzione da ottimizzare è inaffidabile → selezione difettosa

(Con il noise è molto difficile trovare la soluzione.) CHALLENGES Estimated objective functions (come stimare la funzione obiettivo)

(problemi di robotica e ottimizzazione adattiva) 5. PANORAMICA DELLE TECNICHE DI OTTIMIZZAZIONE PANORAMICA DELLE TECNICHE • Tecniche convenzionali: le tecniche convenzionali si basano sulla ricerca deterministica di soluzioni in un modo efficiente. → optimization toolbox di MATLAB) • Euristiche di ricercar (search heuristics): graduale (spesso probabilistico) perfezionamento delle soluzioni → global optimization toolbox di MATLAB) (Un algoritmo di ottimizzazione è un algoritmo di ricerca. Un algoritmo di ottimizzazione convenzionale è un algoritmo di ricerca deterministica di soluzioni ottime in un modo efficiente. Un algoritmo di ricerca euristica si basa sul raffinamento delle soluzioni in modo iterativo e in genere probabilistico. Algoritmi di ricerca euristici sono ad esempio gli algoritmi genetici.) 5.1 Tecniche convenzionali Calcolo deterministico delle soluzioni: • Non tutti gli algoritmi garantiscono che la soluzione è un ottimo globale; • Richiedono forti assunzioni riguardo il problema (non è detto che io riesca a verificarle prima), ad esempio, differenziabilità e continuità, linearità, convessità e possibilità di partizione del problema in sotto-problemi. • Spesso richiede un’implementazione specialistica. • Pro e contro: + molto efficienti (e veloci) se applicabili; - solitamente richiede un’esplicita definizione della funzione obiettivo e dei vincoli. 78

non applicabile a problemi molto sfidanti (al problema di Markowitz e della Sharpe Analysis si possono utilizzare questi algoritmi di ricerca convenzionali). - non ottiene soluzioni se l’algoritmo è prematuramente fermato. (UCITS: per la diversificazione non più del 40% del fondo può essere investito in singoli titoli con peso >5%. Posso scriverlo così: O provo a rendere il vincolo lineare o una tecnica deterministica standard (conventional techniques) non ci consente di trattare questo vincolo.) 5.2 Euristiche di ricerca * graduale perfezionamento delle soluzioni, di solito soluzioni probabilistiche: non garantiscono che il risultato sia ottimo e sono molto generali, ad esempio, non richiedono rigide assunzioni. * produce risultati significativi anche se l’algoritmo (la run) viene fermato prima della fine Pro e contro: + non richiedono una definizione esplicita del problema; + possono affrontare problemi complessi così come sono; + facile implementazione che funziona per un’ampia gamma di problemi. - la performance è dipendente dal problema e l’applicazione richiede particolari conoscenze; - per problemi semplici è inferiore alle tecniche convenzionali. TECNICHE CONVENZIONALI VS. EURISTICHE DI RICERCA • Tecniche convenzionali sono di solito più veloci e precise rispetto alle euristiche di ricerca → se possibile utilizzare tecniche convenzionali; • Molti problemi possono essere semplificati (ad esempio, con la linearizzazione) e risolti efficientemente con tecniche convenzionali; • Tuttavia, se le assunzioni per la semplificazione non tengono, questo porta a soluzioni errate o a nessun risultato. • Utilizza euristiche di ricercar per problemi difficili e problemi che non possono essere ben formalizzati, ad esempio se la funzione obiettivo è sconosciuta. CONVENTIONAL TECHNIQUES – IN MATLAB https://it.mathworks.com/products/optimization.html https://www.mathworks.com/help/pdf_doc/optim/index.html • Nonlinear Optimization • Linear Programming • Mixed-Integer Programming • Quadratic Programming • Least Squares • System of Nonlinear Equation

(Queste sono le tecniche incluse in queste toolbox.) GLOBAL OPTIMIZATION NON CONVENTIONAL – IN MATLAB https://it.mathworks.com/products/global-optimization.html https://it.mathworks.com/help/pdf_doc/gads/gads_tb.pdf

79

• • • • • •

Global Search and Multi Start Genetic Algorithm Pattern Search Simulated Annealing Applications Particle Swarm

(Metodi più recenti o più avanzati. Non vedremo la parte di Global Optimization.)

INSERIRE THE MATLAB OPTIMIZATION TOOLBOX E CAPITOLO 2 OPTIMIZATION TOOLBOX.

80...