An efficient optimization approach for a cardinality-constrained index tracking problem

In the practical business environment, portfolio managers often face business-driven requirements that limit the number of constituents in their tracking portfolio. A natural index tracking model is thus to minimize a tracking error measure while enforcing an upper bound on the number of assets in the portfolio. In this paper we consider such a cardinality-constrained index tracking model. In particular, we propose an efficient nonmonotone projected gradient (NPG) method for solving this problem. At each iteration, this method usually solves several projected gradient subproblems. We show that each subproblem has a closed-form solution, which can be computed in linear time. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the NPG method is a local minimizer of the cardinality-constrained index tracking problem. We also conduct empirical tests to compare our method with the hybrid evolutionary algorithm [P.R. Torrubiano and S. Alberto. A hybrid optimization approach to index tracking. Ann Oper Res. 166(1) (2009), pp. 57-71] and the hybrid half thresholding algorithm [F. Xu, Z. Xu and H Xue. Sparse index tracking: an L_1/2 regularization based model and solution, Submitted, 2012] for index tracking. The computational results demonstrate that our approach generally produces sparse portfolios with smaller out-of-sample tracking error and higher consistency between in-sample and out-of-sample tracking errors. Moreover, our method outperforms the other two approaches in terms of speed.