Cartera de mínima varianza y mínimo tracking error como programa cónico de segundo orden

Question

La optimización cuadrática (varianza mínima) $$ w^{T} \Sigma w \rightarrow \text{min}, $$ donde $w$ es el vector de ponderaciones de la cartera y $\Sigma$ es la matriz de covarianza de los rendimientos de los activos, es un problema bien estudiado. En la práctica tenemos que definir ciertas restricciones. Se trata de restricciones lineales y continuas fáciles (como $\sum_{i=1}^n w_i = 1$ o restricciones de giro) o restricciones binarias difíciles (si se compra un activo que con al menos $x\%$ una restricción de cardinalidad, etc.).

Configurar $\hat{w} = w_{Pf} - w_{BM}$ como el vector de ponderaciones activas de la cartera en relación con un índice de referencia, la fórmula anterior describe la minimización del error de seguimiento (al cuadrado).

Las difíciles restricciones binarias conducen a la programación entera mixta (PIM). Los solucionadores comerciales la resuelven con métodos como rama y límite que consumen mucho tiempo para problemas grandes (por ejemplo, más de 1000 activos).

He oído hablar de un enfoque para formular tales problemas como programas cónicos de segundo orden (SOCP) y que estos problemas suelen resolverse de forma más eficiente.

Tengo mucha experiencia con branche y bound y me gustaría cambiar a SOCP. ¿Conoces alguna buena referencia de SOCP y optimización de carteras/TE con restricciones duras del mundo real (especialmente con variables binarias)? ¿Tenéis alguna experiencia sobre si el cambio merece la pena?

PD: Supongamos que $\Sigma$ está bien estimada y esa varianza tiene sentido. Sé que esto es discutible...

EDITAR: Este artículo Aplicaciones de la programación cónica de segundo orden describe la formulación de un programa cuadrático con restricciones cuadráticas como SOCP. También se le echará un vistazo aquí .

EDITAR 2: Para formular todos los detalles. Tengo el programa cuadrático mixto-inter (formulo el caso TE): $$ w^{T} \Sigma w + w^T c \rightarrow \text{min}, $$ con $0 \le w_i \le u$ para $i = 1,\ldots, N$ con $N \approx 1000$ y un vecor constante $c$ . Las restricciones son de la forma $$ w_i \ge b_i*l \text{ for } i = 1,\ldots,N \\ \sum b_i \le K \\ b_i \in \{0,1\} \text{ for } i = 1,\ldots,N $$ con un pequeño real $l \in (0,1)$ y algún número entero grande $K$ . Además tengo muchas limitaciones continuas $$ A w \le b. $$ Si soy totalmente preciso, entonces hay variables continuas adicionales que aparecen sólo en las restricciones (estos modelos se vuelcan).

Si sigo el enlace anterior, esto puede formularse como SOCP mixto con $$ t \rightarrow \text{min}. $$ y todas las restricciones anteriores y una adicional: $$ \| \Sigma^{1/2} w + \Sigma^{-1/2}c \| \le t. $$

¿Existe la posibilidad de que el problema SOCP mixto-integro tal y como se ha formulado anteriormente pueda resolverse de forma más eficiente que el programa cuadrático mixto-integro (con restricciones lineales y binarias pero no cuadráticas)?

Answer 1

Sin las restricciones discretas, el problema de mínimo error de seguimiento/varianza es un programa cuadrático. Si se restringe el error de seguimiento, se tiene un problema convexo con restricciones cuadráticas que se resuelve como un SOCP por los solucionadores comerciales modernos. El SOCP no aborda restricciones discretas como la cardinalidad de los activos o los niveles mínimos de inversión. El SOCP se ocupa de las restricciones convexas continuas. Estas restricciones hacen que la región factible no sea convexa. Por ejemplo, una cartera con un 50% de A y un 50% de B tiene sólo 2 activos, y una cartera con un 50% de B y un 50% de C tiene dos activos, pero cualquier combinación convexa de esas dos carteras tendrá 3 activos.

Lineal vs. SOCP y continuo vs. mixto-integro son conceptos ortogonales. Los solucionadores mixtos enteros suelen requerir árboles de búsqueda. El lineal vs. SOCP determina qué problema se resuelve en cada nodo del árbol de búsqueda. Con los solucionadores comerciales cplex, y Gurobi puedes tener lineal continuo, lineal mixto-integro, cuadrático/SOCP continuo y cuadrático/SOCP mixto-integro. Hay un video de Gurobi en SOCP que tiene un aparte sobre la inutilidad de intentar hacer nombres para todas las combinaciones.

Es posible que un buen solucionador comercial resuelva de forma fiable problemas como el que describes con 1000's de activos en un tiempo razonable (de segundos a unos minutos), que combinan una heurística sofisticada y rama-y-corte algoritmos. El rendimiento real que se observa depende en gran medida de cómo se formulen las restricciones y de la calidad del solucionador. Hay muchas formas de mejorar una formulación. Por ejemplo, las restricciones de cardinalidad suelen modelarse con variables indicadoras $$ y_i = \left\{\begin{array}{ll} 1 & \mbox{if $w_i > 0$} \\ 0 & \mbox{otherwise} \end{array}\right. $$

que se hace cumplir con las restricciones \begin{eqnarray} w_i &\le y_i &\hspace{1in} \forall i \in \{1, \ldots, n\} \\ \sum_{i = 1}^n y_i &\le k & \end{eqnarray} donde $k$ es el límite de cardinalidad. La restricción $w_i \le y_i$ es muy débil, sin embargo. Si conoce un límite superior a priori de la $w_i$ , digamos que $u_i$ se puede añadir la restricción $$w_i \le u_i y_i$$ al modelo. Si $u_i$ es mucho menor que $1$ entonces la relajación continua en los nodos será más ajustada y ayudará a podar el árbol de ramificación y a guiar la heurística. Se puede obtener un límite superior en el $w_i$ ya sea a partir de una restricción explícita (límite duro en el peso de cualquier activo), o de derivarlo del problema.j

Si realmente está tratando de minimizar explícitamente $w^{T} \Sigma w$ para 1000's de activos, eso significa $\Sigma$ tiene más de 1.000.000 de entradas y ha estimado explícitamente la covarianza de cada par de activos. Esto es difícil o imposible de hacer de forma fiable e ineficiente desde el punto de vista del cálculo. Sería mejor hacer una modelo de factores donde los rendimientos del activo $i$ vendría dado por $r_i = \epsilon_i + \sum_j \beta_{ij} r_j$ . Donde $j$ indexa los factores, y $\sigma_i$ sería la varianza de $\epsilon_i$ . Si $\Sigma^f$ fuera la varianza/covarianza de los rendimientos de los factores, entonces se tendría un objetivo $$ \mbox{minimize} f^T \Sigma^f f + \sum_i \sigma_i^2 w_i^2 $$ Con limitaciones adicionales $$ \sum_i \beta_{ij} w_i = f_j \hspace{0.5in} \forall j $$ La relajación continua sería mucho menor y, por tanto, los subproblemas de los nodos se resolverían mucho más rápido. El $\sigma_i$ podría utilizarse para calcular los límites superiores de $w_i$ también, ya que es la varianza que no puede ser cubierta por otros activos.