¿Es difícil crear carteras aleatorias con restricciones?

Question

Creación de carteras aleatorias con ponderaciones $x_i$ puede considerarse como un muestreo de la superficie de un simplex dado por $$Ex = f$$ y $$Ax \le b$$ Dónde $E$ y $A$ son matrices de restricciones de igualdad y desigualdad, y $f$ y $b$ son soluciones para alguna cartera en la que quieras coincidir, $x_0$ . Ajustando las ecuaciones anteriores para reflejar esto nos da: $$Ex = f = Ex_0$$ y $$Ax \le b = Ax_0.$$

Las restricciones de igualdad son relativamente fáciles de satisfacer, la solución es simplemente $x = x_0 + Z r$ , donde $Zr$ está en el espacio nulo de $E$ y esto puede ser la base de un paseo aleatorio de Monte Carlo. Sin embargo, no hay una forma matemática directa de vincular las restricciones de desigualdad con las de igualdad. La solución parece ser comprobar si su paseo le lleva sobre el límite, y luego reflexionar sobre él, sin embargo, como el número de $x$ es muy grande, el número de caras a reflejar crece con $n$ y esto empieza a suponer un problema de tiempo de cálculo. ¿Hay alguna forma mejor de hacer este algoritmo, o simplemente es un problema difícil?

Editar: Aquí hay un ejemplo de código R con el paseo aleatorio y la reflexión sobre los límites, sólo manejando la restricción de desigualdad que todos $x$ debe ser positivo:

require(MASS)
getWeights <- function(Emat, x0, n, verbose = FALSE) {
    Z = Null(t(Emat))
    ret = matrix(0, nrow = length(x0), ncol = n + 1)
    ## Would it be better to use apply here?
    nc = ncol(Z)
    mn = mean(x0)
    ret[, 1] = x0 + Z %*% rnorm(nc, 0, mn)/sqrt(nc)
    k = 0
    if(verbose) cat("Created Vectors: ")
    if(verbose) cat(paste(k))

    for (i in 2:(n + 1)) {
        ret[, i] = ret[, i - 1] + Z %*% rnorm(nc, 0, mn)/sqrt(nc)
        m = k + 1;
        while(any(ret[, i] < 0)) {
            reflection = rep(0, ncol(Emat))
            reflection[which(ret[, i] < 0)] = ret[, i][which(ret[, i] < 0)]
            for (j in 1:ncol(Z)) {
                ret[, i] = ret[, i] - 2* Z[, j] * (reflection %*% Z[, j])/sqrt(Z[,
                  j] %*% Z[, j])
            }
            ##for(i in 1:nchar(paste(k)))  cat("\b")
            ##if(verbose) cat(paste(m))
            ##k = m
            ##m = k + 1
        }
        if(verbose) for(i in 1:nchar(paste(k)))  cat("\b")
        if(verbose) cat(paste(m))
        k = m
    }
    ret = ret[, 2:(n + 1)]
    if(verbose) cat("\n")
    return(ret)
}
Emat = matrix(1, ncol = 1000, nrow = 1)
x0 = rep(1/1000, 1000)
w = getWeights(Emat, x0, 1000, TRUE)

Como puedes ver este código simplemente va demasiado lento. (¿Crees que sería mejor intentar implementar este código más rápido, usando C y múltiples núcleos, o valdría más la pena cambiar el algoritmo?)

Answer 1

El enfoque de reflexión es costoso, ya que el $d$ -simplemente tiene $d$ caras máximas, todas las cuales tienen que ser comprobadas para la intersección en cada paso. Además, si el paseo aleatorio se adentra en una esquina, el número de movimientos que hay que descartar puede llegar a ser muy elevado. Dependiendo de la configuración de las restricciones, ésta podría ser la mejor solución.

Si he entendido bien su pregunta, la cuestión se reduce al muestreo de la intersección de la frontera de un simplex ( $E$ ) y el volumen de otro ( $A$ ) simultáneamente.

Sugerencias:

• Rechazo si las regiones admisibles para las dos condiciones no son demasiado diferentes, podría ser eficiente crear puntos dentro de $A$ para su inclusión en $E$ y rechazar el punto si no es así.
• Reiniciar Si la caminata aleatoria crea demasiados movimientos descartados, comience desde una nueva ubicación utilizando el método de rechazo anterior.
• Proyección : Crear un punto interior para $E$ y comprobar si el punto más cercano en $A$ todavía está dentro $E$ .
• Tamaño de paso adaptable: Se puede calcular la distancia desde el límite de $A$ y $E$ y elegir la mitad del tamaño del paso, por supuesto esto añadirá un sesgo al proceso de generación, esto podría ser un problema.

Algoritmo para un simplex: Hay un buen truco para la unidad simplex de Donald Rubin, que se discute en el informática sitio, para tomar muestras de la unidad simplex. El resultado se puede escalar después para que coincida con un simplex general:

• Crear $n-1$ valores aleatorios distribuidos uniformemente entre 0 y 1 y ordenarlos.
  [Ejemplo: 0,1, 0,3, 0,5, 0,55]
• Añade 0 y 1 a la lista.
  [Ejemplo: 0, 0,1, 0,3, 0,5, 0,55, 1]
• Utiliza las diferencias entre los valores, que sumarán 1.
  [Ejemplo: 0,1, 0,2, 0,2, 0,05, 0,45]

Editar : Estrictamente hablando, no es un problema difícil, ya que se puede resolver en tiempo polinómico; sin embargo, lo sería si se buscando pesos enteros .