Encontrar k de n activos que "minimicen" la matriz de correlación

Question

Estoy tratando de encontrar una manera eficiente de seleccionar $k$ de $n$ activos de riesgo que están menos correlacionados entre sí. Sé que puedo realizar una búsqueda por fuerza bruta de todos los $k$ -combinaciones del tamaño de la $n$ activos pero esto no escala como $n$ crece así que me pregunto si hay una optimización para este problema.

Por ejemplo, tiene los siguientes activos candidatos SHW, GOOG, AMZN, WMT, XOM, JNJ, UPS, AMT, AAPL y NEE. ¿Qué código python, matlab o R (usted elige) ejecutaría para recoger los rendimientos diarios de cada activo y encontrar el subconjunto de 5 activos que minimice root cuadrada de la suma de los cuadrados de las entradas de la matriz de correlación de los rendimientos de esos 5 activos.

I piense en se trata de un problema de programación entera binaria (o tal vez de optimización convexa, ya que estamos buscando un mínimo), por favor, corrija la siguiente formulación si es incorrecta.

Dado

1. una matriz de rendimientos $R$ donde $\left(r_{ij}\right) \in \mathbb{R}^{m \times n}$ es el retorno para el $i$ -día y el $j$ -aquel activo y
2. la matriz de correlación $C = \text{corr}\left( R \right)$ donde $\left(c_{ij}\right) \in \mathbb{R}^{n \times n}$ es el coeficiente de correlación entre el $i$ -y $j$ -activos

Queremos encontrar $\vec{x} \in \left\{0,1\right\}^n $ s.t.

1. $\sum \limits_i^n x_i = k$ y
2. $\vec{x}$ minimiza $\sqrt{\sum \limits_{i,j}^n {c'}_{ij}^{2}}$ , donde $\left({c'}_{ij}\right) \in \mathbb{R}^{n \times n}$ es la entrada de la matriz de correlación modificada $C'$ para los activos seleccionados por $\vec{x}$ dado por $C'= \left(\vec{x} \otimes \vec{x}\right) \odot C$ .

Es decir, $C'$ es $C$ con las filas y columnas de los activos rechazados "puestas a cero", dadas por el producto exterior de $\vec{x}$ con ella misma (para obtener una matriz $X$ con $x_{i,j} \in \left\{0,1\right\} = 0$ cuando $\vec{x}_i = 0$ y $x_{i,j} = 1$ cuando $\vec{x}_i = 1$ ) Hadamard multiplicado por $C$ . Finalmente elegí root cuadrada de la suma de los cuadrados de las entradas de $C'$ pero creo que cualquier métrica de distancia serviría (como la media de los valores absolutos de las entradas).

Gracias.

Answer 1

(Entiendo que 5 de 10 activos es sólo un ejemplo, porque en este caso se podrían comprobar fácilmente todas las combinaciones).

Este sería un ejemplo de cómo hacerlo en R con un algoritmo llamado Aceptación de Umbral.

library("neighbours")  ## https://github.com/enricoschumann/neighbours
library("NMOF")        ## https://github.com/enricoschumann/NMOF

Creo una matriz de correlación C de los rendimientos aleatorios. (Tenga en cuenta que utilizo pocas observaciones, por lo que las correlaciones difieren sustancialmente).

C <- cor(randomReturns(na = 10, ns = 20, rho = 0.5, sd = 0.01))
##        [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
##  [1,] 1.000 0.390 0.715 0.645 0.621 0.587 0.701 0.437 0.394 0.219
##  [2,] 0.390 1.000 0.359 0.447 0.496 0.725 0.499 0.218 0.469 0.244
##  [3,] 0.715 0.359 1.000 0.570 0.592 0.506 0.427 0.602 0.495 0.326
##  [4,] 0.645 0.447 0.570 1.000 0.785 0.798 0.646 0.419 0.442 0.655
##  [5,] 0.621 0.496 0.592 0.785 1.000 0.677 0.474 0.319 0.414 0.471
##  [6,] 0.587 0.725 0.506 0.798 0.677 1.000 0.539 0.370 0.378 0.559
##  [7,] 0.701 0.499 0.427 0.646 0.474 0.539 1.000 0.324 0.417 0.433
##  [8,] 0.437 0.218 0.602 0.419 0.319 0.370 0.324 1.000 0.450 0.295
##  [9,] 0.394 0.469 0.495 0.442 0.414 0.378 0.417 0.450 1.000 0.295
## [10,] 0.219 0.244 0.326 0.655 0.471 0.559 0.433 0.295 0.295 1.000

La función objetivo: Dado un vector lógico x y una matriz de correlación, calcular root cuadrada de la suma de las correlaciones al cuadrado.

mean_cor <- function(x, C) {
    tmp <- C[x, x][lower.tri(C[x, x])]
    sqrt(sum(tmp*tmp))
}

La llamada función de vecindad. Cambiará una solución dada cambiando aleatoriamente un activo.

nb <- neighbourfun(type = "logical", kmin = 5, kmax = 5)

Ejecutar el algoritmo.

x <- TAopt(mean_cor,
           list(x0 = rep(c(TRUE, FALSE), 5),
                neighbour = nb,
                nI = 200),
           C = C)$xbest

La solución.

which(x)
## [1]  1  2  8  9 10

C[x, x]
##        [,1]  [,2]  [,3]  [,4]  [,5]
## [1,] 1.000 0.390 0.437 0.394 0.219
## [2,] 0.390 1.000 0.218 0.469 0.244
## [3,] 0.437 0.218 1.000 0.450 0.295
## [4,] 0.394 0.469 0.450 1.000 0.295
## [5,] 0.219 0.244 0.295 0.295 1.000

Más información sobre el algoritmo en este tutorial en SSRN . (Revelación: soy el encargado de mantener los paquetes NMOF y neighbours que he utilizado en el ejemplo).

Answer 2

En efecto, se trata de un problema de programación entera convexo y cuadrático. La mayoría de ellos son NP-duros, por lo que no hay que romperse la cabeza para encontrar el óptimo de forma eficiente. Dicho esto, hoy en día estos problemas pueden resolverse de forma eficiente, aproximada pero con gran precisión con solucionadores convexos (por ejemplo Mosek ). Por mi propia experiencia, esto podría funcionar hasta tamaños de miles de activos, digamos, con subcarteras seleccionadas de tamaños en los cientos o menos en el hardware minorista estándar.

Pero también hay soluciones heurísticas muy sencillas. Son muy fáciles de implementar, funcionan para casi cualquier tamaño de $n$ o $k$ y puede darle una solución "suficientemente buena".

Algunas ideas para la heurística:

• Prueba y error: Sólo hay que tomar muestras al azar $k$ fuera del $n$ activos. Calcule la varianza total, repita hasta que pierda la paciencia, retenga lo mejor.
• Codiciosos de abajo hacia arriba: Empezar con el activo de menor varianza, encontrar el siguiente entre los restantes $n-1$ que le da la menor varianza para el par, seleccione el tercero de los restantes $n-2$ y así sucesivamente.
• Greedy top-down: igual que bottom-up, pero ahora se deja caer un activo en cada paso.
• Relajación: Eliminar la restricción de que los pesos sean cero-uno y sólo encontrar la mínima varianza pottfolio. Mantenga la $k$ activos con mayor peso. Creo que esto es lo que @Kermittfrog tenía en mente.

Estoy seguro de que hay más posibilidades (el algoritmo de @Enrico Schumann, algoritmos genéticos/evolutivos , recocido simulado , ...).

Vea también esto pregunta relacionada con la mía en MSE.