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:
- 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.
- 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.
Handle Rank and Cardinality Constraints
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
The solving procedure (Chapter 4.4 of Dattorro2005 (P308)) is first assuming \(W\) is a zero matrix and then solve sub-problem 1 to get \(X^{*}\). \(X^{*}\) is used in sub-problem 2 to solve for latex W$. Then the objective function in sub-problem 1 can be updated with the new \(W\); \(X\) is calculated again. Repeat. The procedure stops when \(Tr(WX)=0\).
Sub-problem 2 actually has a closed form solution, so there is no need to iteratively solve sub-problem 2. As pointed out in Chapter 4.4 of Dattorro2005 (P308), the solution to sub-problem 2 is not unique. And, solving the problem using a closed form solution is not always the fastest, i.e. it may take fewer iterations to solve sub-problems 1 and 2 than by directly solving sub-problem 2. However, in our experiments when closed form solution is used, the total iteration number is not big.
The close form solution to sub-problem 2 can be computed as follow: suppose the diagonal decomposition is \(X^{*}=Q^{T}\Lambda Q\), and let \(U=Q[1:n;2:n]\), then the solution to sub-problem 2 is \(W^{*}=UU^{T}\).
2.2 Cardinality Constraint
Using a very similar procedure described in section 2.1, the cardinal constraint can be transformed into an optimization problem which has a closed form solution (Chapter 4.5, Dattorro2005 (P344)). For example, consider a simple SDP problem with a cardinality constraint (note that this problem is not related to Problem 2 in section 1, and we assume \(X = xx^{T}\).):
\(find_{X\in S^{n}}X\)
\(s.t.\; Tr(AX)=b\)
\(X\geq0\)
\(card(X)\leq k^{2}\)
(original problem)
The above problem is equivalent to the following two problems:
\(\min_{X\in S^{n}}Tr(DX)\)
\(s.t. \; Tr(AX)=b\)
\(X\geq0\)
(sub-problem 1)
\(\min_{D\in n\times n\; diagonal\;matrix}Tr(DX^{*})\)
\(s.t.\;0\leq D\leq I\)
\(Tr(D)=n-k\)
In sub-problem 1 and 2, \(D\) is a diagonal matrix.
sub-problem 2
The solving procedure is same as that of the rank constraint. First we assume \(D\) is a zero matrix and calculate \(X^{*}\) from sub-problem 1. Then diagonal matrix \(D\) can be calculated by solving sub-problem 2 with updated \(X^{*}\). The procedure repeats until when \(Tr(DX)=0\).
As in rank constraint, the solution to sub-problem 2 is not unique. A closed form solution exists, but it is not guaranteed to be the fastest. The closed form solution: \(D\) is a diagonal matrix and \(D_{i,i}=1\) if \(X^{*}_{i,i}\) is smaller than the \((n-k )th\) smallest value of\(\{X_{1,1}^{*},X_{2,2}^{*},\cdots,X_{n,n}^{*}\}\), otherwise \(D_{i,i}=0\).
3. Solution to Problem 2
To solve Problem 2 in section 2, two new variables \(W\) and \(D\) are added to the problem. \(W\) is added to restrict the rank of \(Y\) and \(D\) is added to restrict the cardinality of \(Y\). Although two new variable matrices are added, from section 2 we can see that the computation burden does not increase much, because \(W\) and \(D\) have close form solutions.
Solving Problem 2 is equivalent to solving the following three problems:
\(\max_{Y\in S^{n}}Tr(AY)-w_{1}Tr(WY)-w_{2}Tr(DY)\)
\(s.t. \; Tr(BY)=1\)
\(Y\geq0\)
(Problem 3.1)
\(\min_{W\in S^{n}}Tr(WY^{*})\)
\(s.t.\; 0\leq W\leq I\)
\(Tr(W)=n-1\)
(Problem, 3.2)
\(\min_{D\in n\times n\; diagonal\;matrix}Tr(DY^{*})\)
\(s.t.\;0\leq D\leq I\)
\(Tr(D)=n-k\)
(Problem 3.3)
In Problem 3.1, \(w_{1}\) and \(w_{2}\) are penalties imposed on the rank and cardinality constraints.
The solving procedure is as follow:
- Solve Problem 3.1 assuming \(W\) and \(D\) are zero matrices. Denote the solution as \(Y^{*}\).
- Solve Problem 3.2 using \(Y^{*}\) from step 1. Denote the solution as \(W^{*}\).
- Solve Problem 3.3 using \(Y^{*}\) from step 1. Denote the solution as \(D^{*}\).
- Check \(Tr(W^{*}Y^{*})\) and \(Tr(D^{*}Y^{*})\) if they are small enough. If yes, the computation finishes, \(Y^{*}\) is the final solution. Otherwise, go to step 1 and solve Problem 3.1 updating latex W=W^{*}$ and \(D=D^{*}\). Repeat steps 1 – 4.
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
- [d’Aspremont2008] d’Aspremont, A., “Identifying Small Mean Reverting Portfolios”, 2008.
- [Dattorro2005] Dattorro, Jon, “Section 4. Semidefinite programming”, Convex Optimization and Euclidean Distance Geometry, Meboo Publishing. 2005, v2013.03.30.
