Complejidad temporal de la optimización de carteras de Markowitz

Question

¿Cuál es la complejidad temporal de la optimización de la cartera de media-varianza de Markowitz (MVO)?

No he podido encontrar ninguna explicación clara al respecto en Internet ni en documentos académicos.

Estas son mis preguntas:

1. ¿Cuál es la complejidad temporal y espacial de un algoritmo MVO estándar? Explique por qué.

2. ¿Existen casos especiales que puedan resolverse más rápidamente, como la cartera de mínima varianza?

3. ¿Cuál es el tiempo de ejecución típico en segundos utilizando varios paquetes de software para optimizar una cartera con, por ejemplo, 1000 activos en un ordenador típico?

4. ¿Existen algoritmos de cartera más rápidos?

También se agradecerán las referencias a documentos académicos u otras fuentes.

Gracias.

Answer 1

La MVO es una QP (pregunta de programación cuadrática)

Suponiendo un caso no patológico, se puede tener una estimación con el punto interior (sin optimización) de una complejidad alrededor de O(n^{3.5} L)

Véase. https://en.wikipedia.org/wiki/Quadratic_programming Véase. https://en.wikipedia.org/wiki/Interior-point_method Véase. https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm

En la vida real, con un conjunto de restricciones para ser disperso, podemos tener una complejidad entre O(n L) y O(n^{3} L)

En cuanto a la cartera de varianza mínima, sólo tenemos que averiguar la solución de un sistema lineal, que también es O(n^{3} L)

Dependiendo de la matriz, el software, los parámetros, la máquina y la estructura de las restricciones, se puede esperar entre unos cientos de microsegundos a unos pocos segundos para resolver este tipo de problemas.

Dependiendo de su estructura, puede codificar usted mismo un solucionador especializado que superará a los genéricos.