An Efficient Optimization Approach for a Cardinality-Constrained Index Tracking Problem

Fengmin Xu, Zhaosong Lu, Zongben Xu

Abstract

In the practical business environment, portfolio managers often face requirements that limit the number of constituents in their tracking portfolio. A natural index tracking model minimizes tracking error while enforcing an upper bound on the number of assets. This paper proposes an efficient nonmonotone projected gradient (NPG) method for solving this cardinality-constrained index tracking problem. At each iteration, the method solves several projected gradient subproblems, each of which is shown to have a closed-form solution computable in linear time. Under suitable assumptions, any accumulation point of the sequence generated by the NPG method is a local minimizer. Empirical tests comparing the NPG method with hybrid evolutionary and hybrid half thresholding algorithms demonstrate that our approach produces sparse portfolios with smaller out-of-sample tracking errors, higher consistency, and significantly faster computation times.

Introduction

Index tracking is a popular passive investment strategy that aims to replicate the performance of a market index, such as the S&P 500 or the Russell 3000. While a full replication strategy involves purchasing all assets in the index, this is often impractical due to high transaction costs, management fees, and the illiquidity of smaller constituents. Consequently, portfolio managers seek to select a small subset of assets—a "cardinality constraint"—that can effectively mimic the index's returns.

Mathematically, this is a cardinality-constrained optimization problem. Because selecting $r$ assets out of $n$ possibilities is a combinatorial challenge, the problem is NP-hard. Traditional approaches, such as evolutionary algorithms or continuous relaxations (like $L_1$ regularization), often struggle with either computational speed or the precision of the sparsity constraint. This paper introduces a Nonmonotone Projected Gradient (NPG) method designed to overcome these limitations.

Methodology

The NPG Framework

The proposed Nonmonotone Projected Gradient (NPG) method improves upon standard gradient descent through two primary innovations:

  1. Nonmonotone Line Search: Unlike standard descent methods that require the objective function to decrease at every step, the NPG method allows for occasional increases. This flexibility helps the algorithm navigate the complex, non-convex landscape of cardinality-constrained problems, avoiding premature convergence to poor local optima.
  2. Efficient Projection Subproblems: The core of the NPG method involves a projection step that maps a point back into the feasible region defined by the constraints (weights summing to 1, no short-selling, and the cardinality limit). The authors prove that this subproblem can be reduced to a root-finding problem for a piecewise linear function, allowing it to be solved in linear time ($O(n)$).

Theoretical Guarantees

The paper establishes that the NPG method is theoretically sound. Under standard assumptions for these types of optimization problems, the sequence of solutions generated by the algorithm is guaranteed to converge to a local minimizer. This provides a level of mathematical rigor often missing from purely heuristic evolutionary approaches.

Experimental Results

The NPG method was evaluated against two established benchmarks: a Hybrid Evolutionary Algorithm (MIP) and a Hybrid Half Thresholding (HHT) algorithm. Testing was conducted on a variety of datasets, ranging from small indices like the Hang Seng (31 assets) to large-scale indices like the Russell 3000 (2,151 assets).

Computational Speed

The most striking result is the efficiency of the NPG method. On the Russell 3000 dataset, the NPG method reached a solution in approximately 0.34 seconds. In contrast, the Hybrid Evolutionary Algorithm required nearly 2,000 seconds (over 33 minutes) to solve the same problem. This speed makes the NPG method viable for large-scale, real-time financial applications.

Tracking Accuracy and Consistency

Beyond speed, the NPG method demonstrated superior predictive power:

  • Out-of-Sample Performance: In over 90% of the test cases, the NPG method achieved a lower out-of-sample tracking error than the competing algorithms.
  • Generalization: The "gap" between in-sample (training) and out-of-sample (testing) performance was significantly smaller for NPG. This suggests that the method is less prone to overfitting historical data and produces more robust portfolios for real-world trading.

Conclusion

By leveraging the mathematical structure of the cardinality-constrained index tracking problem, the NPG method provides a powerful tool for portfolio managers. It offers a unique combination of theoretical convergence guarantees, extreme computational efficiency, and high out-of-sample accuracy. While the method finds local rather than global optima—a standard trade-off for NP-hard problems—its performance on large-scale indices like the Russell 3000 suggests it is a highly effective approach for modern passive investment management.

Summary updated

Abstract

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 and the hybrid half thresholding algorithm \cite{L1/2} 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.
BibTeX
@article{xu2016efficient,
  author = {Fengmin Xu and Zhaosong Lu and Zongben Xu},
  title = {{An Efficient Optimization Approach for a Cardinality-Constrained Index Tracking Problem}},
  journal = {Optim. Methods Softw.},
  year = {2016},
  doi = {10.1080/10556788.2015.1062891},
}
Figure