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.