Metaheurísticas para el problema de la selección de portfolio (PSP)

24
Metaheurísticas para el problema de la selección de portfolio (PSP)

Transcript of Metaheurísticas para el problema de la selección de portfolio (PSP)

Page 1: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaheurísticas para el problema de la selección de

portfolio (PSP)

Page 2: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaheuristics for the Portfolio Selection Problem

Andrea RoliDEISUniversit`a di Bologna

Giacomo di TolloDipartimento di ScienzeUniversit`a “G.D’Annunzio” Chieti–Pescara

Page 3: Metaheurísticas para el problema de la selección de portfolio (PSP)

Indice 1. Presentación del problema   2. Motivación   3. Modelo de Markowitz  4. Extensiones al modelo  5. Restricciones  6. Metaheurísticas en la literatura  7. Resultados  8. Conclusiones

Page 4: Metaheurísticas para el problema de la selección de portfolio (PSP)

El problema de selección de portfolio

• La cartera de inversiones o portfolio, es el conjunto de activos financieros compuesto por una combinación de instrumentos de renta fija y renta variable.

• Cada inversión conlleva un riego asociado y una ganancia potencial.

• El modelo aquí presentado es una simplificación que considera sólo la adquisición de acciones.

• Se intenta minimizar el riesgo maximizando la ganancia.• Los riesgos y las ganancias son estimados mediante

procesos estocásticos sujetos a errores de medición. • Es difícil incorporar al modelo restricciones que se presentan

en la realidad, como el tamaño mínimo de las operaciones, el tamaño máximo de la cartera o los costos y comisiones por operaciones, entre otros.

Page 5: Metaheurísticas para el problema de la selección de portfolio (PSP)

El problema de selección de portfolio(II)

PSP:•  Presentado por Harry Markowitz formula un problema de

optimización donde se debe minimizar el riesgo.• Sin embargo, falla en capturar muchos aspectos del mundo

real. PSP restringido: • Es el resultado de agregar restricciones encontradas en el

mundo real al modelo original.• Se ha demostrado que es un problema de dificultad NP-

Completo

Page 6: Metaheurísticas para el problema de la selección de portfolio (PSP)

Algunos problemas de eficiencia    

•  En algunos casos, los problemas son de gran tamaño, con restricciones particulares o se dispone de poco tiempo de computo. Esto hace de los métodos exactos no sean una herramienta conveniente para atacar instancias de gran envergadura.

 •  En estos casos los investigadores han desarrollado

algoritmos aproximados, en particular se han focalizado en metaheurísticas y técnicas híbridas, dando como resultado "solvers" para algunas formulaciones del problema.

Page 7: Metaheurísticas para el problema de la selección de portfolio (PSP)

Modelo PSPEn la formulación de Markowitz el riesgo se mide con la varianza del portfolio.

sujeto a:

 

 

Page 8: Metaheurísticas para el problema de la selección de portfolio (PSP)

Modelo PSP (II)

• La covarianza nos indica el grado de correlación entre los variables aleatorias entre X e Y

• El resultante de la cartera es representado por una variable aleatoria y el valor esperado es dado por (1) que es el valor mínimo de retorno requerido para el problema

Page 9: Metaheurísticas para el problema de la selección de portfolio (PSP)

Modelo PSP (III)

Page 10: Metaheurísticas para el problema de la selección de portfolio (PSP)

Modelo PSP extendido

Función objetivo (Lagrangean relaxation)

donde lambda es el coeficiente de trade-off.El inversor puede elegir el portfolio dependiendo de requerimientos riesgo/retorno específicos.Esta representación es poco representativa del problema real, incluso Markowitz recomendó usar la semivarianza que representa mejor el riesgo percibido por los inversores. 

Page 11: Metaheurísticas para el problema de la selección de portfolio (PSP)

Modelo PSP extendido (II)Target downside risk:

Donde el treshold tao conocido como Value-at-risk (VaR) puede ser percibido como una medida del riesgo catastrófico, ya que los inversores suelen preocuparse por eventos de baja probabilidad y alto impacto.

Short fall probability and expected short fall probability:

Es la probabilidad que el retorno caiga por debajo del VaR

Es el retorno esperado dado que que su valor está por debajo del VaR.Si bien VaR falla en resaltar la importancia de la diversificación, el acuerdo de Basel permite a los bancos utilizarla para calcular el riesgo crediticio, por lo que es muy utilizada.

Page 12: Metaheurísticas para el problema de la selección de portfolio (PSP)

Restricciones• Budget and return Las posibilidades están limitadas por el capital y el retorno. • Cardinality  Reduce los costos de managment• Floor and ceiling Evita costos de transacciones y limita el riesgo. • Short sales Intenta reducir los efectos de una potencial baja de valor. • Rounds Modela la adquicición de activos enteros. • Class Permite diversificar por clases. • Preassignment Admite elecciones por parte del inversor. • Transaction costs Contempla varios costos fijos de las transacciones.

Page 13: Metaheurísticas para el problema de la selección de portfolio (PSP)
Page 14: Metaheurísticas para el problema de la selección de portfolio (PSP)

Criterios en la literaturaEl espacio de búsquedaEn la literatura hay implementaciones que no permiten visitar soluciones inválidas, otros que dada una solución inválida la reparan y también se pueden encontrar métodos que aplican penalizaciones. Se hace un trade off entre la exploración y la intensificación.

La función de costosEn la mayoría de las implementaciones la función objetivo se usa como función de costos. Sin embargo, hay casos en los que se han utilizado otras funciones para guiar el proceso de búsqueda. Soluciones vecinasSe puede clasificar la construcción de soluciones vecinas en dos categorías: 1. Las que toman un pivot en el protfolio y la comparan con una cantidad x de otras acciones. 2. Las que modifican una cantidad arbitraria de acciones en el portfolio.

Page 15: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaherísticas (Simulated annealing)• Simulated annealing se caracteriza por la posibilidad de moverse a

soluciones vecinas de un costo mayor.• La probabilidad de moverse hacia soluciones peores que la actual

depende de la diferencia del costo entre ambas. • Este criterio probabilístico de aceptación permite que la búsqueda no

caiga en óptimos locales.  • Los autores Crama y Schyns experimentaron en modelos de una

sola restricción utilizaron 3 estrategias:o Corridas independientes usando la misma solución inicial.o Corridas subsecuentes usando como solución inicial la iteración

anterior.o Ejecutar el algoritmo una candidad de veces tal que una lista P de

soluciones interesantes es creada, se ejecuta el algoritmo tantas veces como elementos haya en P usando como solución inicial el i-esimo elemento de la lista.

Page 16: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaherísticas (Simulated annealing)

ACEF , UEF y CEF:• Ninguna de las 3 muestra un mejor desempeño, lo cual

implica que la solución inicial no determina mejoras en la búsqueda

Multiobjetivo:• En este caso los movimientos aceptados solo aquellos que

al menos un criterio es mejorado, mientras que las soluciones que deterioran son evaluadas de acuerdo al criterio probabilístico escogido. Este enfoque fue aplicado a restricciones del tipo: Floor & ceiling y cardinalidad.

• Para este modelo las soluciones encontradas son aquellas que viven en la parte baja de la región efectiva y minimizan tanto el riego como la ganancia.

Page 17: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaheurísticas (Tabu search)Rolland utiliza el modelo sin restricciones e intenta construir un protfolio con un retorno dado, en vez de buscar el mejor.Minimun variance:• Después de 5 pasos dentro del espacio de soluciones no factibles

ejecuta un algoritmo de reparación.• Si la inversión excede el presupuesto toma el activo con mayor

suma de covarianza y decrementa su participación.• Si la inversión está por debajo del presupuesto toma el activo con

menor suma de covarianza e incrementa su participación.Minimun variance given return:• Mientras el retorno esperado no se encuentre a 0,005% del dado:

 

  • Si la inversión supera el presupuesto decrementa xi.• Si la inversión está por debajo del presupuesto aumenta xi.

Page 18: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaheurísticas (Tabu search)

• Glover et al. ataca un porblema similar a PSP pero que trabaja sobre períodos multiples (asset-allocation with fixed-mix).

• Busca partir el portfolio en clases formadas por acciones, bonos y bonos del tesoro; para mantener un mismo riesgo en todos los períodos.

• En cada período toma en cuenta el cash flow generado por el management, pues los dividendos generados por los activos son reinvertidos. 

• Tiene en cuenta, también, el costo de las transacciones.• Permite agregar estrategias utilizadas en la práctica, como

por ejemplo, vender los activos con retornos mayores a los esperados y comprar más de aquellos con retornos menores al esperado. 

Page 19: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaherísticas (Evolutionary algorithms)

1. Tettamanzi et al. usa una población con una especie por cada lambda. Se generan individuos proporcionalmente a la probabilidad de que pertenezcan a la especie de interés.

2. Las poblaciones vecinas son aquellas con lambdas similares.3. La reproducción se realiza con un criterio elitista, donde sólo las

mejores soluciones participan. El cross-over es una combinación lineal de los padres: c*padre + (1-c)*madre.

4. Fue la base de algunos algoritmos meméticos que utilizan SA y TA. Los resultados indican que TA trabaja mejor con una medida down side risk, mientras que SA mejora al usar expected shortfall.

5. Los resultados indican que se obtienen mejores resultados intensificando la búsqueda sobre espacios suaves lo que permite escapar de un optimo local sin grandes perdidas en performance.

Page 20: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaherísticas (Evolutionary algorithms)

1. Existen implementaciones distribuidas que agregan migraciones entre poblaciones vecinas para evitar la convergencia prematura. Cada subpoblación está relacionada con un lambda.

2. La restricción de cardinalidad permite buscar paralelamente distintas fronteras para cada valor k. La información intercambiada durante la reproducción y las migraciones mejora los procesos de búsqueda.

3. Se han incorporado restricciones de floor-ceiling y transaction cost con muy buenos resultados.

4. La naturaleza de estos algoritmos logra mejorar la performance en formulación con objetivos múltiples. Mientras que se considera muy poco flexible en formulaciones de objetivos singulares.

Page 21: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaherísticas (Ant colony)• Una aplicación exitosa de Ant Colony para el problema de

PSP con restricción de cardinalidad fue realizado por D.G. Maringer.

• Este aproach consiste en definir una población de n hormigas que exploran el grafo conexo de n nodos. 

• En este modelo se mapea cada nodo a cada elemento disponible para invertir y el camino realizado por cada hormiga se utiliza como el conjunto de elementos del portfolio para invertir.

• El tamaño del camino es k, donde k es el tamaño del portfolio.

Page 22: Metaheurísticas para el problema de la selección de portfolio (PSP)

Metaherísticas (Ant colony)

• En el caso de multi restricción, las hormigas se dividen en poblaciones tales que cada población resuelve una restricción.

• Cuando las hormigas terminan la exploración, una búsqueda golosa refina la solución. 

• Ant Colony encuentra mejores soluciones que SA, los resultados obtenido por ACO pertenecen a la parte alta de la frontera, donde el riesgo y la ganancia son altos.

Page 23: Metaheurísticas para el problema de la selección de portfolio (PSP)

ComparacionesLas diferentes implementaciones puede llevar a comparaciones injustas.

Tenemos que tener en cuenta criterios muy variados respecto a un modelo dado:                            Eficiencia, Robustez, Performance Usualmente se comparan los resultados obtenidos por implementaciones sobre modelos con restricciones contra  otros sin restricciones. Es importante utilizar el mismo set de datos. Los resultados parecen indicar que los algoritmos evolutivos suelen obtener las mejores soluciones. Simulated annealing y colonia de hormigas no son tan efectivos, pero logran mayor performance. Finalmente, Tabu search es en general el peor.

Page 24: Metaheurísticas para el problema de la selección de portfolio (PSP)

Conclusiones• Este problema es intrínsicamente interdisciplinario y

requiere grandes aportes tanto del mundo de la computación como del de las finanzas.

• Los trabajos en la literatura muestran por un lado el potencial de estas estrategias de resolución, y por otro otro lado los numerosos problemas que surgen de las distintas modelizaciones y diseños de algoritmos.

• Actualmente se está trabajando en algoritmos híbridos que resuelvan problemas sujetos a múltiples restricciones. La intención es lograr buenos resultados con un modelo lo más realista posible.

• Todos estos modelos incluyen en alguna medida información estocástica, por lo que su importancia no puede quedar desapercibida.