Mixed-integer programming approach for index tracking

Question

Suppose you currently own a portfolio of eight stocks. Using the Markowitz model, you computed the optimal mean/variance portfolio. The weights of these two portfolios are shown in the following table:

You would like to rebalance your portfolio in order to be closer to the M/V portfolio. To avoid excessively high transaction costs, you decide to rebalance only three stocks from your portfolio. Let $x_i$ denote the weight of stock $i$ in your rebalanced portfolio. The objective is to minimize the quantity:

$|x_1-0.02|+|x_2-0.05|+|x_3-0.25|+...+|x_8-0.12|$

which measures how closely the rebalanced portfolio matches the M/V portfolio. Now I want to formulate this problem as a mixed integer linear program but I am only familiar with index tracking problems based on characteristic similarities and when transaction costs are neglected, hence this problem is pretty confusing for me.

Progress: I have figured how to write the objective function in a linear form. $$min\sum_{i=1}^8 t_i$$ $$st \quad t_1\geq x_1-0.02$$ $$t_1\geq 0.02-x_1$$ $$...$$ $$t_8\geq x_8-0.12$$ $$t_8\geq 0.12-x_8$$ $$\sum_{i=1}^8x_i=1$$

What are the further constraints? I need new binary variables in order to impose the constraint that only three stocks are traded but I don't know how to write that.

I would appreciate any helps!

Answer 1

Hi: I came up with something but go over it carefully because it's a little different from what you were doing (but not much).

First, let $y_{i} = $ the portfolio weight bought or sold in stock $i$. So, if $y_{i}$ is greater than zero then it was purchased and if it is negative, then this means that it was sold.

Also, let $x_{i} = $ current differnce betwen portfolio weight and mv weight of stock $i$ which is known. So, for example $x_{1} = 0.12 - 0.02 = 0.10$.

Let $d_{i}$ be 0-1 variables that represent whether stock $i$ was traded. 0 indicates that it wasn't traded and 1 indicates that it was.

So, the formulation becomes:

minimize $\sum_{i=1}^{8} (x_{i} + y_{i})^2$ or minimize $\sum_{i=1}^{8} |x_{i} + y_{i}|$

subject to

$\sum_{i=1}^{8} d_{i} = 3$

$y_{1} \ge -x_{1} d_{1} = -0.10 d_{1}$

$y_{1} \le x_{1} d_{1} = +0.10 d_{1}$

$y_{2} \ge -x_{2} d_{2} = -0.10 d_{2}$

$y_{2} \le x_{2} d_{2} = 0.10 d_{2}$

$y_{3} \le -x_{3} d_{3} = 0.12 d_{3}$

$y_{3} \ge x_{3} d_{3} = -0.12 d_{3} $

$y_{4} \ge -x_{4} d_{4} = -0.04 d_{4}$

$y_{4} \le x_{4} d_{4} = 0.04 d_{4}$

$y_{5} \ge -x_{5} d_{5} = -0.02 d_{5} $

$y_{5} \le x_{5} d_{5} = 0.02 d_{5}$

$y_{6} \le -x_{6} d_{6} = -0.0 d_{6} $

$y_{6} \ge x_{6} d_{6} = 0.0 d_{6} $

$y_{7} \le -x_{7} d_{7} = +0.10 d_{7}$

$y_{7} \ge x_{7} d_{7} = -0.10 d_{7}$

$y_{8} \le -x_{8} d_{8} = +0.0.4 d_{8}$

$y_{8} \ge x_{8} d_{8} = -0.0.4 d_{8}$

EXPLANATION OF FORMULATION ABOVE.

objective function:

portfolio theory would say minimize the squared differences between final portfolio weight and mean variance optimal weight. If the variances were all the same but the variances are unknown so you could just as well minimize the absolute value of the differences. The two formulations won't give the same answer but since the variances aren't known, it's not obvious what the objective function should be.

constraints:

the first constraint gives the "only trade 3 stocks" constraint. When $d_{i} = 1$ that means the stock $i$ ( other than stock 6 which will never be traded since the pair constraints force $y_{6}$ to be zero regardless of the value of $d_{6}$ ) will be traded. When $d_{i} = 0$, this means that stock $i$ will not be traded.

The other constraints come in pairs ( note that the $y_{i}$ are not constrained so a positive number indicates buy amount and a negative number indicates sell amount ) in order to implement the trick to deal with the only trade 3 stocks constraint. So, looking at the constraints as pairs of constraints for each $i$, when $d_{i} = 1$, the second of the paired constraints won't come into play ( because the objective tries to minimize distance which is symmetric so there is no reason for y to cross zero if it doesn't need to due to symmetry). Fortunately, when $d_{i} = 0$, the pair results in $y_{i} then being constrained to be zero so it won't be traded. In this manner, the constraints enforce the rule to trade only 3 stocks.

implementation:

I didn't actually try to implement the formulation above but hopefully you use R because I wouldn't be surprised if there is some R package that allows one to interface to a mixed integer LP formulation software such as Cplex etc. Check out the cran optimization task view on cran for more information on optimization in R.

Wed, May 19, 2021

EDIT: I had a mistake in the objective function. I had to change the objective function to $x_{i} + y_{i}$ since, given how I have defined $x_{i}$ and $y_{i}$, that is the expression for the final difference between portfolio weight in stock $i$ and mean variance optional weight in stock $i$.

Note that I did not need to change the constraints but I reversed the order in each pair in order to emphasize that the first of the two comes into play when $d=1$. So, the first constraint that was originally written is now second in the pair and the second constraint that was originally written is now first. The second constraint is only active when the zero equality is enforced (when $d=0$ ).