Index tracking strategy is a passive nancial strategy aiming at replication of a given index or portfolio return. In this study, a solution for the problem of index tracking is regarded with account of cardinality constraint, i. e. with a restriction on the maximum amount of assets held in the portfolio. The article discusses di erent algorithms to solve this problem in l2-norm, speci cally, greedy algorithm, di erential evolution algorithm, and LASSO-type algorithm. For the empirical analysis we used public data relating to the three major market indices: Hang Seng (Hong Kong), S&P 100 (USA) and Nikkei 225 (Japan). For comparative analysis of greedy algorithm with LASSO-type algorithm and di erential evolution algorithm stochastic dominance principle was used. At that, the comparison of the approaches included in-sample data as well as out-of-sample data.
For any q > 0 and x = (x1; : : : ; xn)T 2 Rn, let kxkq := (Pin=1 jxijq)1=q and kxk0 = limq!0+ kxkq = (the number of non-zero elements of x). If q 1 then kxkq denotes lq-norm of x 2 Rn. Let n be the number of investable assets. Denote rti the return of asset i at time t, 1 i n, 1 t m, R = (rti) is the m n matrix. A portfolio is de ned to be a vector of weights, x = (x1; : : : ; xn)T 2 Rn. We do not allow the portfolio changes over time and do not take into account transaction costs. We will assume that 1. one unit of capital is available, i. e. xT 1n = 1, where 1n denotes the vector from Rn in which every component is equal to 1; 2. short selling is allowed, i. e. weights xi can be negative. ? The results were obtained within the framework of the state task of RFBR (grant 14-01-00140).
Let It be the index return at time t, 1 t m, and I = (I1; : : : ; It)T 2 Rm. In the traditional index tracking optimization, the objective is to nd a portfolio which has minimal tracking error variance, the sum of squared deviations between portfolio returns and market index returns (see e. g. [20]): 1 x = arg min m kI
Rxk22 s: t: xT 1n = 1:
(
It should be noted that the standard Markovitz model is a special case of
index tracking portfolio model (
Instead of squared deviations, the absolute error is also presented in [9, 13, 14, 18, 19, 21, 23, 28] and is used in practice.
In this paper we will examine three algorithms for solving the problem (
1 x = arg min m k
IT 1n
Rxk22 s. t. xT 1n = 1; kxk0
K;
(
Index tracking problem with cardinality constraint is NP-hard problem and it usually requires the development of heuristic algorithms such as genetic algorithms and di erential evolution algorithm [1,8{12,16]. These algorithms, though providing a su ciently accurate solution of the problem, are associated with signi cant time costs connected with algorithm operation. Good reviews can be found in [1, 5, 17]. Greedy algorithms also proved their e ectiveness [7, 25]. On the other hand, greedy algorithms does not necessarily yield an optimal solution.
In section 2 we describe three algorithms for solving the problem (
Therefore, our comparative analysis will be based on algorithms from three di erent classes of algorithms: GA is a trajectory method, DE-algorithm is a population-based method and LASSO-type algorithm is method with the cardinality constraint relaxation.
The greedy algorithm presented in this paper uses the adaptation of ideas
of [25]. In section 3, using a technique for comparative analysis based on both rst
order stochastic dominance and second order stochastic dominance principles,
we compare the performance of three di erent portfolios obtained by the three
algorithms for index tracking problem (
Algorithms for Minimization of Index Tracking Error in l2-norm with the Cardinality Constraint 2.1
Greedy algorithm for l2-norm minimization with regularization
Let N = f1; : : : ; ng be the index set of investable assets. Problem (
Rxk22 + kxk22 s: t: xT 1n = 1; kxk0
K;
(
Let Mk N be the set of indices corresponding to k non-zero elements of x.
Let ReMk be a submatrix of R with dimension (m jMkj). Then the problem (
ReMk xek22 +
kxek22 s: t: xeT 1jMkj = 1; xe 2 RjMkj:
Denote f (Mk) := kI ReMk xe k22 + kxe k22. The optimal solution of the
problem (
Ek) 1(ReMTk I
ek);
(
Let M0 = ? and k = 1. Set f (M0) to be su ciently large;
while k K do
8s 2 N nMk 1 calculate xeMk 1[fsg using (
s2NnMk 1
Set Mk = Mk 1 [ fs g and k = k + 1; end
Set xG = xeMK and MG = MK ; return xG and MG;
f (Mk 1 [ fsg) and set xeMk = xeMk 1[fs g; 2.2
Minimization of l1 penalized objective functions can have a sparsifying e ect
that has long been observed in research and practice. Minimizing l1 norm is now
a widely used technique for obtaining sparse solutions [4]. The paper [4] uses
LASSO-type approach when the problem (
Rxk2
; xT 1n = 1;
(
The number of assets in the portfolio with non-zero weights (i. e. cardinality
K) of the optimal solution of the problem (
Di erential evolution algorithm for l2-norm minimization A recent addition to the class of heuristics is the evolutionary method of di erential evolution (DE) proposed by [24].
In our work to solve the problem (
Let N be the number of portfolios in each population. The initial population P of portfolios xi = (xi0; : : : ; xin)T 2 Rn, i = 1; : : : ; N , is obtained as follows. First, we randomly generate N vectors yi from Rn. For each yi we set to zero n K elements yji of vector yi that are closest to zero (the cardinality of yi becomes K) and then we set xij = yji =(Pn s=1 ysi) to gain restriction xT 1n = 1.
Portfolios xi refer to the point of n-dimensional space which de nes the objective function m1 kI Rxk2 that we want to minimize. At each iteration, the algorithm produces a new generation of portfolios (population) randomly combined from portfolios of the previous generation. Portfolios of new generation is generated in a few steps. First, for each i = 1; : : : ; N we randomly select three di erent portfolios xa, xb, xc among the portfolios of the previous generation. Then, we calculate x~ij = xja + (F + z1)(xjb xjc + z2) where x~ij , xa, xb, xjc are j-th components of x~i, xa, xb, xc vectors respectively.
j j Parameter F is a positive real constant from the interval [0; 2], which manages the increasing in uence of the di erence xjb xjc + z2 in the result vector, z1 and z2 are either equal to zero with small probabilities (for example, 0.001 and 0.002, respectively), or they are normally distributed random variables with mean zero, and a small standard deviation (i. e. 0.002). Then we set to zero n K elements of x~i (the cardinality of x~i must be equal to K), and after it we set x~ij = x^ij =(Pn i
s=0 x~s) to ful l the budget constraint.
Parameters z1 and z2 are optional parameters of di erential evolution algorithm; they make \noise" in the calculation of the resulting vector which helps to avoid falling into local extremes.
Component x^ij of vector x^i replaces xij with probability and the portfolio x^i goes into the next generation if the following conditions are satis ed: kI
Rx^ik2 < kI
Rxik2:
(
Evolution of the population corresponds to the dynamics of a \swarm of midges" (i. e. random point clouds). The cloud is moving along the relief of optimized function, repeating landscape features. In the case of falling, it takes the shape of the ravine and the points distribution is such that the expectation of the di erence between two random vectors is directed along the long side of the ravine. This provides rapid movement along the narrow ravines. In similar conditions the gradient methods have vibrational dynamics \from wall to wall".
The pseudo-code for m1 kI Rxk2-minimization using di erential evolution algorithm is shown below. 3 3.1
In our empirical analysis we use publicly available data relating to three major market indices, that can be obtained from the OR-Library of [1, 2]. The three market indices are the Hang Seng (Hong Kong, n = 31), DAX 100 (Germany, n = 85) and the Nikkei 225 (Japan, n = 225) for m = 290 time periods each (weekly data), taken from [1]. The summary statistics of the daily log-returns of the indices are presented in Table 1. Table 1 shows that the return time series exhibit the typical patterns of nancial times series: mean values around zero, light asymmetry and fat tails.
The data used in this paper is given in the form of matrices of asset prices. We transformed the original data sets into matrices of asset returns. It is widely accepted to use of the price ratio in order to derive the rate of returns, instead of using absolute asset price relations.
The index tracking problem with cardinality constraint were implemented using Matlab software, as well as built-in and specially developed functions. All simulations were run in Matlab. The system runs under MS Windows 10 64-bit and in our computational work we used an AMD FX-8350 pc with a 4.00 GHz processor and 8.0 GB RAM.
Algorithm 2: Differential evolution algorithm in l2 begin
Generate N randomly distributed yi 2 Rn, i = 1; : : : ; N ; 8i, set yji = 0 for n K closest to 0 values of yji ; 8i, set initial population P as xij = yji =(Psn=1 ysi), j = 1; : : : ; n; set L to the number of iterations; while t L do for each xi, i = 1; : : : ; N , from P do
select 3 random vectors xa, xb, xc;
for each j of xij do
with probability 1: z1;j N (0; 1), else z1;j = 0;
with probability 2: z2;j N (0; 2), else z2;j = 0;
uj U (0; 1);
if uj < 1 then x~ij = xij;
else x~ij = xja + (F + z1;j)(xjb xjc + z2;j);
8x~i, set x~ij = 0 for n K closest to 0 elements;
8x~i 2 P , set x^i = x~i=Ps x~is;
if conditions (
Rxik2; Description of stochastic dominance principle. To compare the approaches examined in this study we used stochastic dominance principle enabling a choice to be made in favour of one or another method (portfolio) [15]. Its peculiarity lies in the fact that it does not require precise knowledge of the investor's utility function, it only has to be monotonous and not decreasing [22].
Before proceeding to the de nition of stochastic dominance, let us consider the concept of a dominant portfolio. The portfolio is considered to be dominant, i. e. preferred over other portfolio, if it has a higher level of return at the same level of risk or lower risk for the same expected return than another portfolio.
In this study, we will use stochastic dominance of rst and second order for the analysis of the resulting portfolios. A more detailed description can be found in the book [19].
F2(y)dy; x 2 [a; b]:
Let us denote by F1 and F2 distribution functions of random variables (portfolio returns) X1 and X2 accordingly. If on the interval [a; b] (random variable support) the inequality F1 F2 is satis ed, i. e. return distribution function of one portfolio does not exceed return distribution function of the other portfolio, we can say that there is stochastic dominance of the rst order of one portfolio over the other (or random variable X1 over X2), and denote X1 I X2.
However, the situation may not be unambiguous, i. e. return distribution functions of the rst and second portfolios may overlap. Therefore we can not say with certainty which of the portfolios is preferable for the investor. In this case the evaluation can be performed on the basis of stochastic dominance of the second order.
We say that this is the case of stochastic dominance of the second order of random variable X1 over X2 and use the notation X1 II X2, if Z x Z x
a a
Thus, the criterion of stochastic dominance of the second order is based not on the comparison of portfolio return distribution functions but on the integrals of these functions, i. e. areas under distribution functions. It can also be said that the rst portfolio is preferable to the second if the cumulative distribution function of its return never exceeds, and at least in one case is less than cumulative distribution function of the second portfolio.
As follows from the second-order dominance, dominance of the rst order of one portfolio over the other automatically assumes its stochastic dominance of the second order as well. Thus, the condition of the second-order stochastic dominance is a weaker condition.
In summary, we can note that in comparison with other methods of assessment stochastic dominance gives the investor a more general approach to the assessment of risky portfolios.
We determine the optimal model using a window of 100 observations (weeks) and leave it intact for further 10 out-of-sample trading weeks for testing purposes. Then, this (in-sample) window is shifted forward by 10 weeks, and a new portfolio of solution for index tracking problem is determined using a window of the new 100 observations, and then again it is left unchanged for further 10 out-of-sample weeks, and so on. Thus, portfolios are recalculated once every 10 weeks. It should be noted that the comparison of models for in-sample data was held on the last 10 observations (in-sample) of the 100-observations window. It was done so to ensure that in-sample and out-of-sample samples were of the same dimension.
To compare these approaches in terms of stochastic dominance, all in-sample and out-of-sample data were joined. As a result, two time series of returns had been received with respect to the index of 190 weeks in length, respectively for in-sample and out-of-sample data. Stochastic dominance principle was used for such time series.
Comparative analysis of greedy algorithm and LASSO-type algorithm. Table 2 shows comparative results of stochastic dominance for greedy algorithm and LASSO-type algorithm. It should be noted that stochastic dominance of the rst order was not observed for all samples. While stochastic dominance (of the second order) was observed only for 4 out of 6 out-of-sample data (S&P 100 and Nikkei 225 for both indicators ) in favour of greedy algorithm.
For clarity, Fig. 1(a) demonstrates the comparison of return distribution functions for portfolios built on greedy algorithm and LASSO-type algorithm for out-of-sample data Nikkei 225 ( = 0:25). The graph shows that the probability distribution functions overlap, i. e. stochastic dominance of the rst order is not possible. Fig. 1(b) represents the comparison of cumulative distribution functions for the same data. The graph shows that accumulated distribution function of greedy algorithm is always lower than accumulated distribution function of LASSO-type algorithm, i. e. we have stochastic dominance of the second order, XGreedy II XLASSO.
The following two gures 1(c) and 1(d) show an example for out-of-sample data Hang Seng ( = 0:25), when we can not claim the presence of stochastic dominance. Namely, both probability distribution functions and cumulative return distribution functions of the portfolios built using greedy algorithm and LASSO-type algorithm overlap.
Comparative analysis of greedy algorithm and di erential evolution algorithm. Table 3 represents comparative results of stochastic dominance for greedy algorithm and di erential evolution algorithm. It can be seen that stochastic dominance of the rst order was not observed in all samples. If we compare the algorithms in terms of stochastic dominance of the second order, we will see that preference is given to di erential evolution algorithm (in 1 out of 6 in-sample data, and in 3 out of 6 out-of-sample data the portfolio built on di erential evolution algorithm stochastically dominates over (the second order) portfolio built on greedy algorithm). While inverse stochastic dominance is observed only in 1 case for in-sample data, and in 1 case for out-of-sample data -2 -1 0 1 2 0.8 0.6 0.4 0.2 0 1 0.8 0.6 0.4 0.2 0 1 0.8 0.6 0.4 0.2 0 1 LASSO Greedy DE Greedy (b) (d) LASSO Greedy DE Greedy (a) (c) (e) -4 -3 -2 -1 0 1 2 (Nikkei 225 for K = 20). It is possible that di erential evolution algorithm in this case was worse due to insu cient number of operations, or populations, which would allow it to produce a more accurate solution.
By way of illustration, Fig. 1(e) demonstrates the comparison of cumulative return distribution functions of the portfolios built on greedy algorithm and di erential evolution algorithm for out-of-sample data Nikkei 225 (K = 5). The graph ahows that probability distribution functions overlap, i. e. there is no rstorder stochastic dominance. The following gure 1(f) shows comparison of accumulated distribution functions for the same data. The graph demonstrates that accumulated distribution function of greedy algorithm is always higher than accumulated distribution function of di erential evolution algorithm, i. e. we have stochastic dominance of the second order (XDE II XGreedy). 4
Summing up the results of comparison of greedy algorithm and LASSO-type algorithm, we should note that in most cases we can not give preference to one or the other portfolio. However, for 4 out of 12 data sets yet there was the secondorder stochastic dominance in favour of greedy algorithm. Also it is important to note that greedy algorithm is signi cantly easier to implement, its time costs are small and it easily copes with cardinality as compared to the LASSO-type algorithm.
As for greedy algorithm and di erential evolution algorithm comparison, it
should be said that the portfolios built on greedy algorithm and di erential
evolution algorithm are not signi cantly di erent in the selection of assets, and, as
a rule, without using short sales. Moreover, though the portfolios built on di
erential evolution algorithm as a whole stochastically dominate over (the
secondorder) portfolios built on greedy algorithm, greedy algorithms signi cantly
surpass di erential evolution algorithms in terms of ease of implementation and
algorithm execution time.
23. Sidorov, S., Faizliev, A., Khomchenko, A.: Algorithms for l1-norm minimisation
of index tracking error and their performance. Int. J. Mathematics in Operational
Research X(Y), XX{XX (2016)
24. Storn, R., Price, K.: Di erential evolution { a simple and e cient heuristic for
global optimization over continuous spaces. Journal of Global Optimization 11(
Royal Statistical Society (Series B) 58, 267{288 (1996)
27. Woodside-Oriakhi, M., Lucas, C., Beasley, J.E.: Heuristic algorithms for the
cardinality constrained e cient frontier. European Journal of Operational Research
213(