  # Identifying Small Mean Reverting Portfolios, d’Aspremont, 2008

You are here:
• Identifying Small Mean Reverting Portfolios, d’Aspremont, 2008

### The Eigenvalue Problem, Section 3.2, d’Aspremont2008

The original problem in section 3.2, d’Aspremont2008 is to find the maximum $$\lambda$$ so that:

$$\det(\lambda B-A)=0$$

In d’Aspremont2008 the author transforms the above problem into the following problem, with an additional cardinality constraint.

$$\lambda_{max}(A,B)=\max_{x\in\mathbb{R}^{n}}\frac{x^{T}Ax}{x^{T}Bx}$$

$$s.t. \quad card(x)\leq k$$

$$||x||_{2}=1$$

This problem is equivalent to:

$$\max_{X\in S^{n}}\frac{Tr(AX)}{Tr(BX)}$$

$$s.t. \quad card(X) \leq k^{2}$$

$$Tr(X)=1$$

$$X\geq 0$$

$$rank(X)=1$$

where $$X=xx^{T}$$.

### Problem 1

In d’Aspremont2008, the author points out that the cardinality constraint can be relaxed to $$1^{T}|X|1\leq k^{2}$$. This new constraint is not in the SDP standard form, and thus requires transformation before using an SDP solver. Even so, this relaxation has two drawbacks:

1. To transform $$1^{T}|X|1\leq k^{2}$$ into the standard form, two new $$n$$ by $$n$$ variable matrices are introduced. Let $$X=U-V$$, where $$U_{i,j}\geq0$$ and $$V_{i,j}\geq0$$. This transformation avoids the absolute sign on $$X$$ but the new constraints $$U_{i,j}\geq0$$ and $$V_{i,j}\geq0$$ can not be transformed to the standard form without adding at least $$n(n+1)$$ new constraints. If the dimension of $$X$$ is 100 by 100, this transformation will add ten thousand new constraints to the optimization problem.
2. The constraint $$1^{T}|X|1\leq k^{2}$$ is a relaxation of the cardinal constraint. In d’Aspremont2008 the author points out that due to this relaxation, the final solution $$X$$ may have a higher rank than one. It is thus possible that the cardinality of $$X$$ is bigger than $$k^{2}$$. Because an interior point algorithm maximizes the objective function by searching the interior of a feasible region, the probability that it returns a high rank solution is not low.

Due to these two drawbacks, we suggest to solve Problem 1 without relaxation and instead follow Dattorro2005. After using the same transformation in d’Aspremont2008 (equation 12), the problem we are trying to solve is:

$$\max_{Y\in S^{n}}Tr(AY)$$

$$s.t. \quad card(Y)\leq k^{2}$$

$$Tr(BY)$$

$$Y\geq0$$

$$rank(Y)=1$$

where $$Y=\frac{X}{Tr(BX)}$$.

### Problem 2

The difficulties in solving Problem 2 lie in the rank constraint and cardinality constraint. They are discussed in the next section.

### 2.1 Rank Constraint

According to Chapter 4.4 of Dattorro2005 (P308), the rank constraint is equivalent to an optimization problem. For example, consider the following rank-constrained problem (note that this problem is not related to Problem 2 in section 1.)

$$find_{X\in S^{n}}X$$

$$s.t.\quad Tr(AX)=b$$

$$X\geq0$$

$$rank(X)=1$$

(original problem)

This rank constrained problem is equivalent to the following two problems:

$$\min_{X\in S^{n}}Tr(WX)$$

$$s.t.\; Tr(AX)=b$$

$$X\geq0$$

(sub-problem 1)

$$\min_{W\in S^{n}}Tr(WX^{*})$$

$$s.t.\; 0\leq W\leq I$$

$$Tr(W)=n-1$$

where $$X^{*}$$ is the solution to sub-problem 1.

Sub-problem 2

### 4. Numerical Example

The original problem is to find the maximum $$\lambda$$ so that $$\det(\lambda B-A)=0$$, therefore with the help of an orthogonal matrix $$Q$$, we construct $$A$$ and $$B$$ as follow:

$$A=Q^{T}diag(20,8,4)Q$$

$$B=Q^{T}diag(2,3,5)Q$$

Because $$A$$ and $$B$$ are constructed by the same orthogonal matrix $$Q$$, the value of $$\lambda$$ should be $$10$$, $$8/3$$ and $$4/5$$.

The actual value of $$Q$$, $$A$$ and $$B$$ are:

$$Q=\left(\begin{array}{ccc}-0.33&0.59&0.74\\-0.59&-0.74&0.33\\-0.74&0.33&-0.59\end{array}\right)$$

$$A=\left(\begin{array}{ccc}7.89&4.07&2.13\\4.07&10.0&6.19\\2.13&6.19&14.1\end{array}\right)$$

$$B=\left(\begin{array}{ccc}3.98&0.29&-1.11\\ 0.29&2.87&-0.82\\-1.11&-0.82&3.16\end{array}\right)$$

The results when $$k=1$$, $$w_{1}=5$$, $$w_{2}=225$$ are:

$$Y=\left(\begin{array}{ccc} 0.000& 0.000& 0.010\\ 0.000&0.001&0.015\\ 0.010&0.015&0.331\end{array}\right)$$

$$rank(Y)=1$$

Recall in d’Aspremont2008 $$X=xx^{T}$$, and we assume $$Y=\frac{X}{Tr(BX)}$$. The cardinality of vector $$x$$ recovered from $$Y$$ is 1. Only the third entry of $$x$$ is nonzero.

### References

1. [d’Aspremont2008] d’Aspremont, A., “Identifying Small Mean Reverting Portfolios”, 2008.
2. [Dattorro2005] Dattorro, Jon, “Section 4. Semidefinite programming”, Convex Optimization and Euclidean Distance Geometry, Meboo Publishing. 2005, v2013.03.30.
###### 0 out of 5 stars
 5 Stars 0% 4 Stars 0% 3 Stars 0% 2 Stars 0% 1 Stars 0%
1. 